【Codeforces 571D】Campus

Author Avatar
mrsrz 1月 09, 2020

Kruskal 重构树。

题目大意：

给定 $n$ 个宿舍和 $n$ 个政教处。第 $i$ 个政教处一开始管理第 $i$ 个宿舍。

有以下几种操作：

  1. 给定 $u,v$，将 $v$ 这个宿舍及其附属宿舍都归为 $u$ 这个宿舍的附属宿舍，以后 $v$ 及其附属宿舍不可能再成为其他宿舍的附属宿舍。
  2. 给定 $u,v$，将 $v$ 这个政教处及其附属政教处都归为 $u$ 这个政教处的附属政教处，以后 $v$ 及其附属政教处不可能再成为其他政教处的附属政教处。
  3. 给定 $u$，如果 $u$ 及其附属宿舍（保证 $u$ 不是另外一个宿舍的附属宿舍）一共有 $a$ 个，那么令 $u$ 及其附属宿舍中的人的个数都增加 $a$。
  4. 给定 $u$，清空 $u$ 及其附属政教处（保证 $u$ 不是另外一个政教处的附属政教处）管理的所有宿舍里的人。
  5. 给定 $u$，询问 $u$ 这个宿舍当前的人数。

题解：

离线处理，对宿舍及其政教处分别进行 Kruskal 重构。然后区间加转化为树上子树加。区间赋 $0$ 转化为树上子树赋 $0$。

但是由于是在两棵树上进行的操作，我们不能同时进行维护。

由于我们是单点查询，所以我们如果知道 $u$ 这个点最后一次被清空的时间 $t$，就可以分别算出 $t$ 时刻 $u$ 里的人数和当前时刻 $u$ 里的人数（不考虑赋 $0$ 操作），然后做差即为答案。

所以我们分别对两棵树进行维护。

对政教处我们维护每个点被赋 $0$ 的最晚时间，即区间覆盖单点查询。可以使用线段树。

然后可以查询得到每个点被查询时的最后清空时间。

对宿舍我们维护不考虑赋 $0$ 时每个点的人数，即区间加单点查询。可以使用树状数组。

查询一个点在某一时刻对应的重构树上的根，可以使用倍增或树剖的方式查询我倍增被卡空间树剖差点被卡空间。

总时间复杂度 $O(n+m\log n)$。

Code：

#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
using namespace std;
typedef long long LL;
const int N=5e5+3;
LL ans[N];
int n,m;
LL B[N*2];
inline void ADD(int i,int x){for(;i<=2*n;i+=i&-i)B[i]+=x;}
inline LL ASK(int i){LL x=0;for(;i;i&=i-1)x+=B[i];return x;}
namespace sgt{
    int d[N<<2];
    void modify(int l,int r,int o,const int&L,const int&R,const int&tm){
        if(L<=l&&r<=R)d[o]=tm;else{
            const int mid=l+r>>1;
            if(L<=mid)modify(l,mid,o<<1,L,R,tm);
            if(mid<R)modify(mid+1,r,o<<1|1,L,R,tm);
        }
    }
    int query(int l,int r,int o,const int&pos){
        if(l==r)return d[o];
        const int mid=l+r>>1;
        return max(d[o],(pos<=mid)?query(l,mid,o<<1,pos):query(mid+1,r,o<<1|1,pos));
    }
}
struct Kruskal_Rebuild_Tree{
    int Fa[N*2],fa[N*2],m,n,head[N*2],top[N*2],cnt,w[N*2],dfn[N*2],idx,out[N*2],sz[N*2],dep[N*2],siz[N*2],son[N*2];
    vector<int>vw[N*2],vid[N*2];
    struct Edge{
        int u,v,t;
    }E[N];
    inline void addedge(int u,int v,int t){E[++m]=(Edge){u,v,t};}
    struct edge{
        int to,nxt;
    }e[N*2];
    void init(int nn){
        w[0]=1919810;
        n=nn;
        for(int i=1;i<=n;++i)fa[i]=i,sz[i]=1;
    }
    inline int find(int x){while(x!=fa[x])x=fa[x]=fa[fa[x]];return x;}
    inline int jump(int u,int k){
        while(w[Fa[top[u]]]<=k)u=Fa[top[u]];
        const vector<int>&vc=vw[top[u]];
        return vid[top[u]][lower_bound(vc.begin(),vc.end(),k,greater<int>())-vc.begin()];
    }
    void dfs(int now){
        siz[now]=1;
        for(int i=head[now];i;i=e[i].nxt){
            Fa[e[i].to]=now;
            dfs(e[i].to);
            sz[now]+=sz[e[i].to];
            siz[now]+=siz[e[i].to];
            if(!son[now]||siz[e[i].to]>siz[son[now]])son[now]=e[i].to;
        }
    }
    void dfs2(int now){
        dfn[now]=++idx;
        vw[top[now]].push_back(w[now]);
        vid[top[now]].push_back(now);
        if(son[now])top[son[now]]=top[now],dfs2(son[now]);
        for(int i=head[now];i;i=e[i].nxt)if(e[i].to!=son[now])dfs2(top[e[i].to]=e[i].to);
        out[now]=idx;
    }
    void work(){
        for(int i=1;i<=m;++i){
            int u=find(E[i].u),v=find(E[i].v);
            if(u!=v){
                ++n;
                fa[u]=fa[v]=fa[n]=n;
                w[n]=E[i].t;
                e[++cnt]=(edge){u,head[n]},head[n]=cnt;
                e[++cnt]=(edge){v,head[n]},head[n]=cnt;
            }
        }
        for(int i=n;i;--i)
        if(find(i)==i)dfs(i),dfs2(top[i]=i);
    }
}G,P;
struct MQ{
    int u,t;
}add[N],cq[N];
struct qwq{
    int u,t,id;
};
vector<qwq>vec[N];
int tA,tC;
int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n>>m;
    G.init(n),P.init(n);
    memset(ans,-1,sizeof ans);
    for(int i=1;i<=m;++i){
        char op[3];
        cin>>op;
        switch(*op){
            case'U':{
                int u,v;
                cin>>u>>v;
                G.addedge(u,v,i);
                break;
            }
            case'M':{
                int u,v;
                cin>>u>>v;
                P.addedge(u,v,i);
                break;
            }
            case'A':{
                int u;
                cin>>u;
                add[++tA]=(MQ){u,i};
                break;
            }
            case'Z':{
                int u;
                cin>>u;
                cq[++tC]=(MQ){u,i};
                break;
            }
            case'Q':{
                int u;
                cin>>u;
                cq[++tC]=(MQ){-u,i};
                ans[i]=0;
                break;
            }
        }
    }
    G.work();
    P.work();
    for(int i=1;i<=tC;++i){
        int u=cq[i].u,tim=cq[i].t;
        if(u>0){
            int x=P.jump(u,tim);
            sgt::modify(1,2*n,1,P.dfn[x],P.out[x],tim);
        }else{
            u=-u;
            int l=sgt::query(1,2*n,1,P.dfn[u]);
            vec[l].push_back((qwq){u,-1,tim});
            vec[tim].push_back((qwq){u,1,tim});
        }
    }
    for(int i=1,it=1;i<=m;++i){
        while(it<=tA&&add[it].t<=i){
            int x=G.jump(add[it].u,add[it].t);
            ADD(G.dfn[x],G.sz[x]);
            ADD(G.out[x]+1,-G.sz[x]);
            ++it;
        }
        for(int p=0;p<vec[i].size();++p){
            int u=vec[i][p].u,t=vec[i][p].t,id=vec[i][p].id;
            ans[id]+=ASK(G.dfn[u])*t;
        }
    }
    for(int i=1;i<=m;++i)
    if(ans[i]!=-1)cout<<ans[i]<<'\n';
    return 0;
}
Powered by Hexo
Theme - Material