题解 CF571D 【Campus】

· · 题解

CF571D Campus

blog内获得更佳体验

一翻题解, 都是建虚点的离线做法, 这里提供一个更好想也更好写的在线做法(雾

一看涉及到合并, 就想到了并查集, 但有一些加啊, 赋值啊, 所以不可路径压缩, 那就按秩合并呗

按秩合并就是通过合并时把较小的联通块叫较大的连通块爸爸莱保证严格log的时间复杂度, 同时, 一个连通块的高度也是log的

按秩合并的好处就是它的内部形态不会变, 如果打标记回比较方便

回到本题, 建立两颗按秩合并的并查集f，g， f每个点维护一个vector<pair<t, add>>表示在t时间内加了add的三操作标记，这里是前缀和的形式，方便后面二分查找时间t以后的add值之和

较为困难的五操作

之前维护的那么多都是为五操作服务的（废话

树高是log的， 所以可以从一个点暴力向上跳，先去跳g，找出x点最近一次清零的时刻t，注意一个细节：如果x的父亲和x相连时刻比标记的时间大，则标记对x是无效的， 这点对add标记同理

然后跳f，在从x到根的每个点上二分查找大于清零时间和相连时间的标记和， 最后加起来就是答案

时间复杂度\Theta(nlog^2n)，二分在随机情况下跑不满，事实上跑的挺快的

const int N = 500500;
int gs[N], fs[N], n, m;
int f[N], g[N], ft[N], gt[N];
char opt[5];

int find(int *f, int x) { while (x ^ f[x]) x = f[x]; return x; }
inline void merge(int *f, int *siz, int *t, int x, int y, int k) {
    x = find(f, x), y = find(f, y);
    if (siz[x] < siz[y]) swap(x, y);
    siz[x] += siz[y], f[y] = x, t[y] = k;
}

int cls[N];
vector<pair<int, ll> > add[N];
#define MP make_pair

int main() {
    read(n), read(m);
    for (int i = 1;i <= n; i++) fs[f[i] = g[i] = i] = gs[i] = 1, add[i].push_back(MP(-1, 0));
    for (int i = 1;i <= m; i++) {
        scanf ("%s", opt); int x, y; read(x);
        switch (opt[0]) {
            case 'U' : read(y), merge(f, fs, ft, x, y, i); break;
            case 'M' : read(y), merge(g, gs, gt, x, y, i); break;
            case 'A' : { int k = find(f, x); add[k].push_back(MP(i, fs[k] + add[k].back().second)); break; }
            case 'Z' : { int k = find(g, x); cls[k] = i; break; }
            case 'Q' : {
                int fx = x, tag = cls[x];
                while (g[fx] != fx) {
                    if (cls[g[fx]] > gt[fx]) tag = max(tag, cls[g[fx]]);
                    fx = g[fx];
                }
                fx = x;  int l = lower_bound(add[x].begin(), add[x].end(), MP(tag, 0ll)) - add[x].begin();
                ll ans = add[x].back().second - add[x][l-1].second;
                while (f[fx] != fx) {
                    int tf = f[fx];
                    l = lower_bound(add[tf].begin(), add[tf].end(), MP(max(tag, ft[fx]), 0ll)) - add[tf].begin();
                    ans += add[tf].back().second - add[tf][l-1].second; fx = f[fx];
                }
                printf ("%lld\n", ans);
            }
        }
    }
    return 0;
}