【题解】Campus 树状数组 CF571D —Qiuly

建两个森林，每次合并两棵树的时候新建一个点作为两棵树的根的父亲，就像 $\rm{Kruskal}$ 重构树一样。

考虑修改操作和询问操作，对于每一个询问操作维护一个 $[l,r]$ $(1\leq l\leq r\leq m)$，表示该询问操作的有效时间，也就是说 $l=1$ 或者 $l-1$ 是一个 $4$ 操作，$r=m$ 或者 $r+1$ 是一个 $4$ 操作。

得到了每一个操作的 $[l,r]$ 后去遍历第一个森林，用树状数组以时间为下标维护一下就好。

如何得到 $[l,r]$ ？遍历一遍第二个森林即可。

第一个森林：

struct Tree1 {
    vector <int> son[N];
    vector <pair<int,int>> tag[N];
    int tot,fa[N],siz[N],vis[N];
    int find(int x) {return x==fa[x]?x:fa[x]=find(fa[x]);}
    inline void update(int x,int t) {x=find(x),tag[x].push_back(MKP(t,siz[x]));}
    inline void clear() {for(int i=1;i<=(tot=n);++i) fa[i]=i,siz[i]=1;}
    inline void merge(int x,int y) {
        x=find(x),y=find(y),fa[x]=fa[y]=++tot;
        son[tot].push_back(x),son[tot].push_back(y),
        fa[tot]=tot,siz[tot]=siz[x]+siz[y];
    }
    void dfs(int u) {
        vis[u]=true;
        for(auto t:tag[u]) bit.update(t.first,t.second);
        for(Node now:_Q[u]) Ans[now.id]=bit.query(now.l,now.r);
        for(auto v:son[u]) dfs(v);
        for(auto t:tag[u]) bit.update(t.first,-t.second);
    }
}T1;

第二个森林：

struct Tree2 {
    vector <int> que;
    vector <int> son[N];
    vector <int> tag[N];
    int tot,fa[N],vis[N];
    int find(int x) {return x==fa[x]?x:fa[x]=find(fa[x]);}
    inline void update(int x,int t) {tag[find(x)].push_back(t);}
    inline void clear() {for(int i=1;i<=(tot=n);++i) fa[i]=i;}
    inline void merge(int x,int y) {
        x=find(x),y=find(y),fa[x]=fa[y]=++tot;
        son[tot].push_back(x),son[tot].push_back(y),fa[tot]=tot;
    }
    void dfs(int u) {
        vis[u]=true;
        for(int i=tag[u].size()-1;~i;--i) que.push_back(tag[u][i]);
        int now=Q[u].size()-1,s=que.size();
        if(que.size()) {
            while(~now&&Q[u][now].first>que[0])
                _Q[u].push_back((Node){que[0],Q[u][now].first,Q[u][now].second}),--now;
            while(~now&&Q[u][now].first>que[s-1]) {
                /*这里写得很丑...... 不想改了，将就将就 (雾*/
                /*之前犯了个蠢，直接用指针然后扫一遍询问的复杂度是 O(m^2) 的*/
                /*于是每一个询问二分就好了*/
                int pos=Q[u][now].first,l=1,r=s-1,mid;
                while(l<=r) {
                    mid=(l+r)>>1;
                    if(que[mid]<pos&&pos<que[mid-1]) break;
                    if(pos<que[mid]) l=mid+1;
                    else if(pos>que[mid-1]) r=mid-1;
                }
                _Q[u].push_back((Node){que[mid],pos,Q[u][now].second}),--now;
            }
        }
        while(~now)
            _Q[u].push_back((Node){1,Q[u][now].first,Q[u][now].second}),--now;
        for(auto v:son[u]) dfs(v);
        for(auto t:tag[u]) que.pop_back();
    }
}T2;

注意 $_Q$ 就是用来存 $l,r$ 的，$Q$ 存的只是询问时间，当然都需要维护一个询问编号。