AOJ 2235 Graph Construction

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2235
クエリを平方分割する問題．平方分割した後にいらない頂点をつぶすのが超大変．
Union-Find treeでがんばってつぶす．
以前からあった辺が，今みている区間のなかで破壊されるとき，あらかじめ辺を追加しておくのを忘れたりした．
全ての場合を網羅するのはとても大変．

#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
#define fst first
#define snd second
#define IDX(a,v) distance((a).begin(),lower_bound((a).begin(),(a).end(),v))

typedef pair<int,int> P;
typedef pair<P,int> Pi;
typedef pair<P, P> PP;
const int MAXN=40000,MAXK=40000,ROOTK=200;
const int INF=1<<29;
int N,K,sqrtK;
int qtype[MAXK];
P qv[MAXK];
vector<PP> qc; // PP( P(追加時間,削除時間), P(頂点,頂点) )
vector<Pi> qd; // Pi( P(頂点,頂点), 削除時間 )

int UFtree[MAXN];
void init(){
	for(int i=0;i<N;i++){UFtree[i]=i;}
}
int find_root(int v){
	if(UFtree[v] == v) return v;
	return UFtree[v] = find_root(UFtree[v]);
}
void marge(int v, int u){
	int x, y;
	x = find_root(v);
	y = find_root(u);
	UFtree[x] = y;
}

int newG[2*ROOTK][2*ROOTK];
bool visited[2*ROOTK];
bool is_connect(int s, int g, int vn){
	visited[s] = true;
	if(s == g) return true;
	for(int i = 0; i < vn; i++){
		if(newG[s][i] && !visited[i] && is_connect(i, g, vn)){
			return true;
		}
	}
	return false;
}

int main(){
	scanf("%d%d",&N,&K);
	for(int i=0;i<K;i++){
		int t, u, v;
		scanf("%d%d%d", &t,&u,&v);
		qtype[i] = t;
		qv[i] = P(u,v);
		if(t == 1){
			//追加される辺
			qc.push_back(PP(P(i,INF),P(u,v)));
		}else if(t == 2){
			//削除される辺
			qd.push_back(Pi(P(u,v),i));
		}
	}
	//追加される辺の削除時刻をもとめる
	sort(qd.begin(), qd.end());
	bool used[qd.size()];
	fill(used, used + qd.size(), false);
	for(int i=0; i < qc.size();i++){
		P p = qc[i].snd;
		for(int k = IDX(qd, Pi(p,0)); k < qd.size() && qd[k].fst == p; k++){
			//既に追加するものとペアになっている削除する辺をとばす
			if(!used[k]){
				qc[i].fst.snd = qd[k].snd;
				used[k] = true;
				break;
			}
		}
	}
	//sqrtKを求める
	for(sqrtK=1; sqrtK * sqrtK < K; sqrtK++){ ; }
	//sqrtKずつクエリを処理
	for(int i=0; i<K; i+=sqrtK){
		//union find で関係ない頂点をつぶす
		init();
		for(int j=0; j<qc.size(); j++){
			if(qc[j].fst.fst < i && i+sqrtK <= qc[j].fst.snd){
				//辺qc[j].sndは常に存在するので2つの頂点をmarge
				int v = qc[j].snd.fst, u = qc[j].snd.snd;
				marge(v, u);
			}
		}
        //範囲内で出現する頂点番号を記録する また連結をきく質問があるかみる
		bool use[N], f = false;
		fill(use,use+N,false);
		for(int j = 0; j<sqrtK && i+j<K; j++){
			use[find_root(qv[i+j].fst)] = true;
			use[find_root(qv[i+j].snd)] = true;
			if(qtype[i+j] == 3) f = true;
		}
		if(!f) continue; //連結をきく質問がないなら計算する必要はない
		//頂点の番号を付け替える
		vector<int> newV;
		for(int j = 0; j < N; j++){
			if(j == UFtree[j] && use[j]) newV.push_back(j);
		}
		//関係する頂点数はO(sqrt(K))である
		//よってdfsをすれば計算量はO(sqrt(K))

		//グラフを初期化
		for(int v=0; v<newV.size(); v++)
			for(int u=0; u<newV.size(); u++) newG[v][u] = 0;
		//以前からある辺を追加しておく
		for(int j=0;j<qc.size();j++){
			if(qc[j].fst.fst < i && i <= qc[j].fst.snd && qc[j].fst.snd < i+sqrtK){
				int x = find_root(qc[j].snd.fst), y = find_root(qc[j].snd.snd);
				int v = IDX(newV, x), u = IDX(newV, y);
				if(0<=v&&v<newV.size() && 0<=u&&u<newV.size()){
					newG[v][u]++;
					newG[u][v]++;
				}
			}
		}

		//各クエリを処理
		for(int j=0; j<sqrtK && i+j<K; j++){
			//時刻i+jを考える
			int x = find_root(qv[i+j].fst), y = find_root(qv[i+j].snd); 
			int v = IDX(newV,x), u = IDX(newV,y);
			if(qtype[i+j] == 3){
				//連結であるかのチェック
				fill(visited, visited+newV.size(), false);
				if(is_connect(v, u, newV.size())){
					puts("YES");
				}else{
					puts("NO");
				}
			}else if(qtype[i+j] == 1){
				//辺の追加
				newG[v][u]++;
				newG[u][v]++;
			}else{
				//辺の削除
				newG[v][u]--;
				newG[u][v]--;
			}
		}
	}
}