程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> uvalive 4730王國kingdom（並查集+線段樹）

uvalive 4730王國kingdom（並查集+線段樹）

編輯：C++入門知識

uvalive 4730王國kingdom（並查集+線段樹）

題意：有T組測試數據，每組數據的N表示有N個城市，接下來的N行裡每行給出每個城市的坐標(0<=x,y<=1000000)，然後有M(1

思路：線段樹加並查集

#include  
#include  
#include  
#include  
#include  
#include  
#include  
#include  
#include  
#include 
#include
#include 
#include
#define eps 1e-6 
#define LL long long  
using namespace std;  

const int maxn = 100000 + 100;
const int maxl = 1000000 + 10;
const int INF = 0x3f3f3f3f;
int pa[maxn], low[maxn], high[maxn], pos[maxn], node[maxn];
int sumv1[2*maxl], addv1[2*maxl];  //有多少州
int sumv2[2*maxl], addv2[2*maxl]; 
int n, m;
//pa保存父親結點，low，high保存該連通分量的上下邊界，node保存連通分量中的結點個數 
int find(int x) {
	if(x != pa[x]) return pa[x] = find(pa[x]);
	return x;
}
 
void maintain1(int o, int L, int R) {
	int lc = o*2, rc = o*2+1;
	sumv1[o] = 0;
	if(R > L) {   //考慮左右子樹 
		sumv1[o] = sumv1[lc] + sumv1[rc];
	}
	sumv1[o] += addv1[o] * (R-L+1);//考慮add操作 
} 
void update1(int o, int L, int R, int v, int yl, int yr) {
	int lc = o*2, rc = o*2+1;
	if(yl <= L && yr >= R) {   //遞歸邊界 
		addv1[o] += v;		//累加邊界的add值 
	} else {
		int M = L + (R-L)/2;
		if(yl <= M) update1(lc, L, M, v, yl, yr);
		if(yr > M) update1(rc, M+1, R, v, yl, yr);
	}
	maintain1(o, L, R);		//遞歸結束前重新計算本節點的附加信息 
} 
int query1(int o, int L, int R, int add, int yl, int yr) {
	if(yl <= L && yr >= R) {
		return sumv1[o] + add*(R-L+1);
	} else {
		int ans = 0;
		int M = L + (R-L)/2;
		if(yl <= M) ans += query1(o*2, L, M, add + addv1[o], yl, yr);
		if(yr > M)  ans += query1(o*2+1, M+1, R, add + addv1[o], yl, yr);
		return ans;
	}
} 

void maintain2(int o, int L, int R) {
	int lc = o*2, rc = o*2+1;
	sumv2[o] = 0;
	if(R > L) {   //考慮左右子樹 
		sumv2[o] = sumv2[lc] + sumv2[rc];
	}
	sumv2[o] += addv2[o] * (R-L+1);//考慮add操作 
} 
void update2(int o, int L, int R, int v, int yl, int yr) {
	int lc = o*2, rc = o*2+1;
	if(yl <= L && yr >= R) {   //遞歸邊界 
		addv2[o] += v;		//累加邊界的add值 
	} else {
		int M = L + (R-L)/2;
		if(yl <= M) update2(lc, L, M, v, yl, yr);
		if(yr > M) update2(rc, M+1, R, v, yl, yr);
	}
	maintain2(o, L, R);		//遞歸結束前重新計算本節點的附加信息 
} 
int query2(int o, int L, int R, int add, int yl, int yr) {
	if(yl <= L && yr >= R) {
		return sumv2[o] + add*(R-L+1);
	} else {
		int ans = 0;
		int M = L + (R-L)/2;
		if(yl <= M) ans += query2(o*2, L, M, add + addv2[o], yl, yr);
		if(yr > M)  ans += query2(o*2+1, M+1, R, add + addv2[o], yl, yr);
		return ans;
	}
} 

void init() {
	memset(addv1, 0 ,sizeof(addv1)); memset(addv2, 0, sizeof(addv2));
	memset(sumv1, 0, sizeof(sumv1)); memset(sumv2, 0, sizeof(sumv2));
	cin >> n; 
	for(int i = 0; i < n; i++) {
		int tmp; cin >> tmp >> pos[i];
	}
	for(int i = 0; i < n; i++) {
		pa[i] = i;
		node[i] = 1;
		high[i] = low[i] = pos[i];
	}
	cin >> m;
}

void solve() {
	char cmd[5];
	int a, b;
	float c;
	while(m--) {
		cin >> cmd;
		if(cmd[0] == 'r') {
			cin >> a >> b;
			if(find(a) != find(b)) {
				if(high[pa[a]] != low[pa[a]]) {
					update1(1, 1, 1000000, -1, low[pa[a]]+1, high[pa[a]]);
					update2(1, 1, 1000000, -node[pa[a]], low[pa[a]]+1, high[pa[a]]);
				}
				if(high[pa[b]] != low[pa[b]]) {
					update1(1, 1, 1000000, -1, low[pa[b]]+1, high[pa[b]]);
					update2(1, 1, 1000000, -node[pa[b]], low[pa[b]]+1, high[pa[b]]);
				}
				node[pa[a]] += node[pa[b]]; 
				low[pa[a]] = min(low[pa[a]], low[pa[b]]);
				high[pa[a]] = max(high[pa[a]], high[pa[b]]);
				pa[pa[b]] = pa[a];
				if(high[pa[a]] != low[pa[a]]) {
					update1(1, 1, 1000000, 1, low[pa[a]]+1, high[pa[a]]);
					update2(1, 1, 1000000, node[pa[a]], low[pa[a]]+1, high[pa[a]]);
				}
			} 
		} else {
			cin >> c;
			cout << query1(1, 1, 1000000, 0, (int)(c+1), (int)(c+1)) << " ";
			cout << query2(1, 1, 1000000, 0, (int)(c+1), (int)(c+1)) << endl;
		//	cout << (int)(c+1) << endl;
		}
	}
}

int main() {
//	freopen("input.txt", "r", stdin);	
	int t; cin >> t;
	while(t--) {
		init();
		solve();
	}
	return 0;
}