hdu 4680（数据结构）

题目链接

比赛时一看这题操作这么多， 还有gcd三角形神马的以为是个神题， 后来发现这题其实挺基础的， 就是用并查集和平衡树同时维护若干集合， 合并时用启发式第二个删点操作是并查集中的经典操作， 做法就是找一个新的点替代原来的点类似http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=18692， 第一种查询找到最小次小元素然后进行斐波那契式的迭代， 每次查询后继元素， 第二种查询直接维护子树的gcd查询时从上向下搞一遍就可以了， 细节见代码。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cstdlib>

using namespace std;

inline int read() {//used to read 32bit positive integer
	char c = getchar();
	while (!isdigit(c)) c = getchar();
	int x = 0;
	while (isdigit(c)) {
		x = x * 10 + c - '0';
		c = getchar();
	}

	return x;
}

int gcd(int a, int b) {
	return b == 0 ? a : gcd(b, a % b);
}

const int N = 210005;
const int INF = (int)2e9;

int root[N], fa[N], W[N], now[N];
int r[N], v[N], ch[N][2], sz[N], maxv[N], minv[N], D[N];
int it, n, m, id;

void init() {
	minv[0] = INF;
	it = 1;
	id = n + 1;
	memset(root, 0, sizeof(root));
	for (int i = 1; i <= n; i++) now[i] = i, fa[i] = i;
}

int find(int u) {
	return fa[u] == u ? u : fa[u] = find(fa[u]);
}

#define lch ch[rt][0]
#define rch ch[rt][1]

inline void push_up(int rt) {
	sz[rt] = sz[lch] + sz[rch] + 1;
	maxv[rt] = max(maxv[lch], maxv[rch]);
	maxv[rt] = max(maxv[rt], v[rt]);
	minv[rt] = min(minv[lch], minv[rch]);
	minv[rt] = min(v[rt], minv[rt]);
	D[rt] = gcd(v[rt], D[lch]);
	D[rt] = gcd(D[rt], D[rch]);
}

inline int cmp(int rt, int x) {
	if (v[rt] == x) return -1;
	else if (x < v[rt])
		return 0;
	else
		return 1;
}

void rotate(int& rt, int d) {
        int t = ch[rt][d ^ 1];
        ch[rt][d ^ 1] = ch[t][d];
        ch[t][d] = rt;
        push_up(rt);
        push_up(t);
        rt = t;
}

void insert(int& rt, int x, bool flag) { //falg == 0 x is a number otherwise...
	if (!rt) {
		if (!flag) {
			rt = it++;
			v[rt] = x;
			r[rt] = rand();
			lch = rch = 0;
			sz[rt] = 1;
			D[rt] = x;
			maxv[rt] = minv[rt] = x;
		}
		else {
			rt = x;
			sz[rt] = 1;
			minv[rt] = v[rt];
			maxv[rt] = v[rt];
			D[rt] = v[rt];
			lch = rch = 0;
		}
	}
	else {
		int d = ((flag ? v[x] : x) < v[rt] ? 0 : 1);
		insert(ch[rt][d], x, flag);
		if (r[ch[rt][d]] > r[rt]) 
			rotate(rt, d ^ 1);
	}
	push_up(rt);
}

int kth(int rt, int k) {
	int  t = sz[lch] + 1;
	if (k == t)
		return v[rt];
	else if (k < t) 
		return kth(lch, k);
	else
		return kth(rch, k - t);
}

void remove(int& rt, int x) {
	int d = cmp(rt, x);
	if (d == -1) {
		if (lch && rch) {
			int d2 = r[lch] > r[rch] ? 0 : 1;
			rotate(rt, d2 ^ 1);
			remove(ch[rt][d2 ^ 1], x);
			push_up(rt);
		}
		else {
			rt = lch ? lch : rch;
		}
	}
	else {
		remove(ch[rt][d], x);
		push_up(rt);
	}
}

/*
int pred(int rt, int x) {
	if (!rt) return INF;
	else if (x > v[rt]) {
		int res = pred(rch, x);
		if (res == INF) return v[rt];
		return res;
	}
	else
		return pred(lch, x);
}*/

int pred(int rt, int x) {
	if (!rt) return INF;
	if (x == v[rt]) return x;
	else if (x > v[rt]) {
		int res = pred(rch, x);
		if (res == INF) return v[rt];
		return res;
	}
	else
		return pred(lch, x);
}

/*
int succ(int rt, int x) {
	if (!rt) return INF;
	else if (x < v[rt]) {
		int res = succ(lch, x);
		if (res == INF) return v[rt];
		return res;
	}
	else
		return succ(rch, x);	
}*/

int succ(int rt, int x) {
	if (!rt) return INF;
	if (x == v[rt]) return x;
	else if (x < v[rt]) {
		int res = succ(lch, x);
		if (res == INF) return v[rt];
		return res;
	}
	else
		return succ(rch, x);
}

int ans;

void query(int rt, int l, int r) {
	if (!rt || maxv[rt] < l || minv[rt] > r) return;
	if (l <= minv[rt] && maxv[rt] <= r) {
		ans = gcd(ans, D[rt]);
		return;
	}
	if (v[rt] >= l && v[rt] <= r)
		ans = gcd(ans, v[rt]);
	if (l < v[rt])
		query(lch, l, r);
	if (r > v[rt])
		query(rch, l, r);
}

void mergeto(int ot, int& rt) {
	if (!ot) return;
	mergeto(ch[ot][0], rt);
	mergeto(ch[ot][1], rt);
	//ch[ot][0] = ch[ot][1] = 0;

	insert(rt, ot, 1);
}

void connect(int u, int v) {
	int fu = find(u), fv = find(v);
	if (fu != fv) {
		if (sz[root[fu]] > sz[root[fv]])
			fa[fv] = fu, mergeto(root[fv], root[fu]);
		else
			fa[fu] = fv, mergeto(root[fu], root[fv]);
	}
}

int main() {
	int u, v, l, r, x, typ, test, a, b, c;
	test = read();
	for (int cas = 1; cas <= test; cas++) {
		printf("Case #%d:\n", cas);
		n = read(), m = read();
		init();
		for (int i = 1; i <= n; i++) {
			W[i] = read();
			insert(root[i], W[i], 0);
		}
		for (int i = 0; i < m; i++) {
			typ = read(), u = read();
			if (typ == 1) {
				v = read();
				connect(now[u], now[v]);
				//cout << sz[roo t[4]] << endl;
				//cout << kth(root[4], 1) << endl;
			}
			else if (typ == 2) {
				v = read();
				int fu = find(now[u]);
				int fv = find(now[v]);
				if (fu == fv) continue;
				remove(root[fu], W[now[u]]);
				int tmp = W[now[u]];
				now[u] = id++;
				W[now[u]] = tmp;
				insert(root[fv], W[now[u]], 0);
				fa[now[u]] = fv;
			}
			else if (typ == 3) {
				v = read();
				int fu = find(now[u]);
				remove(root[fu], W[now[u]]);
				W[now[u]] = v;
				insert(root[fu], W[now[u]], 0);
			}
			else if (typ == 4) {
				int fu = find(now[u]);
				if (sz[root[fu]] <= 2)
					printf("%d\n", sz[root[fu]]);
				else {
					a = kth(root[fu], 1);
					b = kth(root[fu], 2);
					int res = 2;
					while (1) {
						c = a + b;
						int t = succ(root[fu], c);
						if (t == INF) break;
						a = b, b = t;
						res++;
					}
					printf("%d\n", res);
				}
			}
			else {
				l = read(), r = read();
				int fu = find(now[u]);
				ans = 0;
				query(root[fu], l, r);
				if (ans)
					printf("%d\n", ans);
				else
					puts("-1");
			}
		}
	}
	return 0;
}