CF571D Campus

IOI2020集训队作业

唔母,这个算是比较简单的一道题了,我也是能找到跟着自己的思路做的解法qwq

龙王桔梗赛高!

有一个长度为 nnn 的序列，初始全为 000。
有两类对下标的集合，初始时每一类各有 nnn 个集合，编号为 iii 的集合里有下标 iii。
一共有 mmm 个操作，操作有五种：
U x y 将第一类编号为 $y$ 的集合合并到编号为 $x$ 的集合里。
M x y 将第二类编号为 $y$ 的集合合并到编号为 $x$ 的集合里。
A x 将第一类编号为 $x$ 的集合中的所有下标在序列中对应的数加上 $x$ 的集合大小。
Z x 将第二类编号为 $x$ 的集合中的所有下标在序列中对应的数设为 $0$ 。
Q x 询问序列中下标为 $x$ 的位置上的数。
$n,m \le 5 \times 10^5$ 。

看到集合合并而且没有拆分,自然而然想到启发式合并

又因为我们是单点查询而且是合并下标,所以不需要高级数据结构吧...就用并查集

然后我们想先考虑第一类集合怎么做

只需要在根上打一个标记,然后两级河合并的时候直接把要接到另一个根上的那个根标记减去另一个根上的标记就好,这样我们把一个点到根路径上经过所有点求个前缀和就一定是答案了

好的,现在我们要兼容赋值操作/kk

一个不难的想法是利用时间戳,我们每个赋值操作毕竟赋的值是一样的,所以我们可以在根上放时间戳,然后从节点到根的路径求一个最大时间就是我们这个点被赋值的最近时间啦

然而这个东西还是不能够兼容之前的加法标记,因为每个点的具体时间不一样.....

等等,我们是不是可以出卖复杂度更暴力的解决一下?或者我们忘记了并查集的什么性质吗?按秩合并???

树高均摊log!

对了,有了这个操作也就意味我们第一个向上跳均摊log次,然后这nlogn次我们每次不用直接拿标记,而是把每次标记带着时间戳都记下来,然后直接在这些标记里面二分就好

时间复杂度很低,O(nlog^2n),二分虽然是满的但其他的不是啊

code:

#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
using namespace std;
#define ll long long
const int MAXN = 1e6 + 7;
int gs[MAXN], fs[MAXN], n, m;
int f[MAXN], g[MAXN], ft[MAXN], gt[MAXN];
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];
    //好像是启发式/kk也只能启发式了
    f[y] = x;
    t[y] = k;
    //两棵树都是启发式合并的过程
}
int cls[MAXN];
vector<pair<int, ll> > add[MAXN];
#define MP make_pair

int main() {
    scanf("%d%d", &n, &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;
        scanf("%d", &x);
        switch(opt[0]) {
        case 'U': scanf("%d", &y), merge(f, fs, ft, x, y, i); break;
        case 'M': scanf("%d", &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]]);
                //取max,找到最大的那个时间戳
                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;
}

果然数据结构还是很好懂的?/kk

夏晓光(loveJY)的博客

树高均摊log!

CF568C New Language