bzoj 3123 [Sdoi2013]森林
内容
Description
.jpg)
Input
第一行包含一个正整数testcase，表示当前测试数据的测试点编号。保证1≤testcase≤20。
第二行包含三个整数N，M，T，分别表示节点数、初始边数、操作数。第三行包含N个非负整数表示 N个节点上的权值。
接下来 M行，每行包含两个整数x和 y，表示初始的时候，点x和点y 之间有一条无向边, 接下来 T行，每行描述一个操作，格式为“Q x y k”或者“L x y ”，其含义见题目描述部分。
Output
对于每一个第一类操作，输出一个非负整数表示答案。
Sample Input
1
8 4 8
1 1 2 2 3 3 4 4
4 7
1 8
2 4
2 1
Q 8 7 3 Q 3 5 1
Q 10 0 0
L 5 4
L 3 2 L 0 7
Q 9 2 5 Q 6 1 6
Sample Output
2
2
1
4
2
题解
连边考虑启发式合并，算了一下复杂度挺暴力的O(n*log^2(n))，但是时限超长。。
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 100010;
int a[N], b[N];
int lower(int x) {
int l = 1, r = b[0], ans;
while (l <= r) {
int mid = l + r >> 1;
if (b[mid] >= x) ans = mid, r = mid - 1;
else l = mid + 1;
}
return ans;
}
int fa[N], siz[N];
int finds(int x) { return (fa[x] == x) ? x : fa[x] = finds(fa[x]); }
struct data {
int sum, l, r;
}pri[N * 200];
int n, m, root[N], x, y, z, tot;
void inserts(int pos, int &now, int l, int r) {
pri[++tot] = pri[now], now = tot, pri[now].sum++;
if (l == r) return;
int mid = l + r >> 1;
if (pos <= mid) inserts(pos, pri[now].l, l, mid);
else inserts(pos, pri[now].r, mid + 1, r);
}
int query(int l, int r, int x1, int y1, int x2, int y2, int z) {
if (l == r) return l;
int mid = l + r >> 1;
int tem = pri[pri[x1].l].sum + pri[pri[y1].l].sum - pri[pri[x2].l].sum - pri[pri[y2].l].sum;
if (tem >= z)
return query(l, mid, pri[x1].l, pri[y1].l, pri[x2].l, pri[y2].l, z);
else
return query(mid + 1, r, pri[x1].r, pri[y1].r, pri[x2].r, pri[y2].r, z - tem);
return 0;
}
struct edge {
int to, next;
}e[N * 2];
int st[N], cnt, vis[N], h[N], f[N][25];
void add(int x, int y) {
e[++cnt].next = st[x];
e[cnt].to = y, st[x] = cnt;
}
void dfs(int x, int pre) {
vis[x] = 1, h[x] = h[pre] + 1;
root[x] = root[pre];
inserts(a[x], root[x], 1, b[0]);
for (int i = 1; i < 20; ++i) {
if (h[x] - (1 << i) < 1) break;
f[x][i] = f[f[x][i - 1]][i - 1];
}
for (int i = st[x], f1, f2; i; i = e[i].next)
if (e[i].to != pre)
f1 = finds(x), f2 = finds(e[i].to),
fa[f2] = f1, siz[f1] += siz[f2],
f[e[i].to][0] = x, dfs(e[i].to, x);
}
int lca(int x, int y) {
if (h[x] < h[y]) swap(x, y);
int p = h[x] - h[y];
for (int i = 0; i < 20; ++i)
if ((p >> i) & 1) x = f[x][i];
if (x == y) return x;
for (int i = 19; i >= 0; --i)
if (f[x][i] != f[y][i])
x = f[x][i], y = f[y][i];
return f[x][0];
}
void rebuild(int x, int pre) {
h[x] = h[pre] + 1;
root[x] = root[pre];
inserts(a[x], root[x], 1, b[0]);
for (int i = 1; i < 20; ++i)
f[x][i] = f[f[x][i - 1]][i - 1];
for (int i = st[x]; i; i = e[i].next)
if (e[i].to != pre)
f[e[i].to][0] = x,
rebuild(e[i].to, x);
}
int q, T, k, las;
main() {
scanf("%d %d %d %d", &T, &n, &m, &q);
for (int i = 1; i <= n; ++i)
scanf("%d", &a[i]), b[i] = a[i];
sort(b + 1, b + 1 + n);
b[0] = unique(b + 1, b + n + 1) - b - 1;
for (int i = 1; i <= n; ++i) a[i] = lower(a[i]);
for (int i = 1; i <= m; ++i)
scanf("%d%d", &x, &y),
add(x, y), add(y, x);
for (int i = 1; i <= n; ++i)
fa[i] = i, siz[i] = 1;
for (int i = 1; i <= n; ++i)
if (!vis[i]) dfs(i, 0);
for (int i = 1; i <= q; ++i) {
char ch = getchar();
while (ch != 'L' && ch != 'Q') ch = getchar();
if (ch == 'Q') {
scanf("%d%d%d", &x, &y, &k);
x ^= las, y ^= las, k ^= las;
int l = lca(x, y), p = f[l][0];
las = query(1, b[0], root[x], root[y], root[l], root[p], k);
las = b[las], printf("%d\n", las);
} else {
scanf("%d%d", &x, &y);
x ^= las, y ^= las;
int f1 = finds(x), f2 = finds(y);
if (siz[f1] > siz[f2]) swap(x, y), swap(f1, f2);
f[x][0] = y, rebuild(x, y), add(x, y), add(y, x);
fa[f1] = f2, siz[f2] += siz[f1];
}
}
}