[CGOI-3] 灵气

· · 题解

题面

模拟赛时当暴力写的，结果 AC 了。

向大佬请教后发现复杂度竟是 O(n\log n)！

该做法离线。好想也好写，不需要分类讨论。

思路

将题目中加/删点操作的集合记作 S。

记 f_x(i) 表示 i 时刻 S 中可以到达 x 的所有点的点权和。

对每一个点 x 维护长为 q 的序列 f_x，初始全为 0。

将所有加/删点操作离线下来。若一个点 x 在 l 时刻加入，r+1 时刻删除，则将 f_x 的 [l,r] 区间加 a_x。另外，第 q 次操作后还在 S 中的点认为在 q+1 时刻删除。

拓扑排序。删掉一条边 u\rightarrow v 时，因为能到达 u 的点一定能到达 v，所以将 f_u 向 f_v 对应位置相加。一个点被加入队列时，所有能到达它的点都直接或间接向它贡献完成了。整个拓扑排序结束后，所有 f 都正确了。

在 t 时刻查询 x，即为查询 \max_{i\in [1,t]}f_x(i)。

考虑采用数据结构维护 f，需要支持的操作有：区间加，合并，前缀 \max。线段树即可。

复杂度

常见的线段树合并因为将 x 向 y 合并后，x 不再参与合并，相当于删掉一个点，所以合并复杂度不超过总结点数，为 O(n\log n)。典例是在内向树上按拓扑序合并。

本题没有这样的性质。

假如存在 x\rightarrow y,\ x\rightarrow z 这两条边，x 向 y 合并后，还会再向 z 合并。乍一看好像很寄，但可以发现这样合并的复杂度不劣于 x\rightarrow y,\ y\rightarrow z。

重复对出度大于 1 的点执行这个操作，最终所有点出度 \le 1，得到一棵内向树。而内向树上合并的复杂度为 O(n\log n)。于是该做法的复杂度也是 O(n\log n)。

实现细节

完结。

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+7;
int n,q,rt[N],que[N],indeg[N],a[N],t[N],ans[N];
vector<int> G[N];
vector<pair<int,int>> Q[N];
namespace SGT
{
    int tot;
    struct node{int ls,rs,ans,tag;}tr[N*80];
    #define ls(p) tr[p].ls
    #define rs(p) tr[p].rs
    inline void pushup(int p){tr[p].ans=tr[p].tag+max(tr[ls(p)].ans,tr[rs(p)].ans);}
    void add(int &p,int L,int R,int x,int l=1,int r=q)
    {
        if(!p) p=++tot;
        if(L<=l&&r<=R) return tr[p].ans+=x,tr[p].tag+=x,void();
        int mid=(l+r)>>1;
        if(L<=mid) add(ls(p),L,R,x,l,mid);
        if(R>mid)  add(rs(p),L,R,x,mid+1,r);
        pushup(p);
    }
    void merge(int &p,int q)
    {
        if(!p||!q) return p|=q,void();
        int o=++tot;tr[o]=tr[p],p=o;
        merge(ls(p),ls(q));
        merge(rs(p),rs(q));
        tr[p].tag+=tr[q].tag;
        pushup(p);
    }
    int query(int p,int L,int R,int l=1,int r=q)
    {
        if(!p) return 0;
        if(L<=l&&r<=R) return tr[p].ans;
        int mid=(l+r)>>1,res=0;
        if(L<=mid) res=query(ls(p),L,R,l,mid);
        if(R>mid)  res=max(res,query(rs(p),L,R,mid+1,r));
        return res+tr[p].tag;
    }
}
int main()
{
    ios::sync_with_stdio(0),cin.tie(0);
    int i,x,y,op,qcnt=0,hd,tl,u;
    cin>>n>>q;
    for(i=1;i<=n;++i) cin>>a[i];
    for(i=1;i<n;++i)
    {
        cin>>x>>y;
        G[x].push_back(y),++indeg[y];
    }
    for(i=1;i<=q;++i)
    {
        cin>>op>>x;
        if(op==1) t[x]=i;
        else if(op==2) SGT::add(rt[x],t[x],i-1,a[x]),t[x]=0;
        else Q[x].emplace_back(i,++qcnt);
    }
    for(i=1;i<=n;++i)if(t[i]!=0) SGT::add(rt[i],t[i],q,a[i]);
    //topo
    hd=1,tl=0;
    for(i=1;i<=n;++i)if(indeg[i]==0) que[++tl]=i;
    while(hd<=tl)
    {
        u=que[hd++];
        for(int v:G[u])
        {
            SGT::merge(rt[v],rt[u]);
            if(!--indeg[v]) que[++tl]=v;
        }
        for(auto p:Q[u]) ans[p.second]=SGT::query(rt[u],1,p.first);
    }
    for(i=1;i<=qcnt;++i) cout<<ans[i]<<'\n';
    return 0;
}