自动搬运

查看原文

来自洛谷，原作者为

	jrxxx **

搬运于2025-08-24 22:44:06，当前版本为作者最后更新于2023-02-04 16:58:01，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题面

模拟赛时当暴力写的，结果 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)$。

实现细节

• 因为存在复用，所以线段树合并时一定要新建版本再修改。我写的是标记永久化，如果 $\rm{pushdown}$ 的话也要注意这个问题。

• $\max(a_i+b_i)\not = \max a_i+\max b_i$，所以处理两个线段树上都有的节点时，$\rm{tag}$ 相加，但是 $\rm{ans}$ 不能直接相加，要等儿子处理完再 $\rm{pushup}$。

完结。

#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;
}