P8959 Sol

一只绝帆 · 2024-02-04 16:41:46 · 题解

考虑离线，对每个点求出一个时间轴，询问就是查询 [1,i] 的时间轴上的最大值，考虑我们不能真的开出那么多空间，所以使用可持久化线段树合并。

具体来说，本题采用以下流程：

• 首先对每个点建立线段树，类似于线段树分治将这个点的出现区间全部加上 a_x（在这个点自己的动态开点线段树上）。

• 然后随便一个根开始 \text{dfs}，先递归指向 x 的儿子（因为这些儿子会影响到其他的儿子），递归完成后将儿子的线段树合并到自己身上。

• 再递归 x 指向的儿子，递归前将 x 的线段树合并到儿子身上。

• 所有递归结束后在 x 处统计所有询问的答案。

关于线段树合并为什么要可持久化，一个点的线段树要多次给儿子们复用，而普通的线段树合并会将原树变成新树的一部分，破坏了原结构。

关于复杂度的证明，可以理解为当且仅当两个点的路径上有 \le 1 个交汇点，=0 个分叉点，这两个点的线段树才会发生 1 次合并，所以并不会有两棵原始树发生了多次合并，而我们知道一直合并的复杂度是跟节点个数成正比的，所以复杂度 \Theta(n\log n)。

关于区间修改的线段树合并，并不是所有区间修改的线段树都能合并，需要看叶子节点的合并和标记的合并是否吻合，本题就是相当于把两棵“区间加区间 \max”的线段树给“加”起来，所以直接使用标记永久化合并即可，叶子处和非叶子处都要将标记相加。

Code：

// Problem: P8959 「CGOI-3」灵气
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P8959
// Memory Limit: 512 MB
// Time Limit: 1000 ms

#include<bits/stdc++.h>
#define l(d) ls[d]
#define r(d) rs[d]
#define mid (L+R>>1)
#define vec basic_string
#define F(i,a,b) for(int i=a,i##end=b;i<=i##end;i++)
using namespace std;
#define gc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
char *p1,*p2,buf[1<<21];
int read() {
    int s=0,w=0;char ch=gc();
    while(ch<'0'||ch>'9') w|=(ch=='-'),ch=gc();
    while(ch>='0'&&ch<='9') s=(s<<3)+(s<<1)+(ch^48),ch=gc();
    return w?-s:s;
} const int N=2e5+5,C=3e7+5;
vec<int> G[N],Q[N],uG[N];
int mx[C],tg[C],snt,l(C),r(C),rt[N],a[N],n,m,vis[N],st[N],ans[N];
#define up(d) (mx[d]=tg[d]+max(mx[l(d)],mx[r(d)]))
void mo(int l,int r,int x,int L,int R,int &d) {
    !d&&(d=++snt);if(R<l||r<L) return;if(l<=L&&R<=r) return tg[d]+=x,mx[d]+=x,void();
    mo(l,r,x,L,mid,l(d));mo(l,r,x,mid+1,R,r(d));up(d);
}
int q(int l,int r,int L,int R,int d,int t=0) {
    if(R<l||r<L) return 0;if(l<=L&&R<=r) return mx[d]+t;
    return max(q(l,r,L,mid,l(d),t+tg[d]),q(l,r,mid+1,R,r(d),t+tg[d]));
}
int cpy(int d) {int x=++snt;l(x)=l(d);r(x)=r(d);mx[x]=mx[d];tg[x]=tg[d];return x;}
void mer(int L,int R,int &x,int y) {
    if(!x||!y) return x=cpy(x|y),void();
    x=cpy(x);if(L^R) mer(L,mid,l(x),l(y)),mer(mid+1,R,r(x),r(y));
    tg[x]+=tg[y];up(x);
}
void d(int x,int fa=0) {
    for(int v:uG[x]) if(v^fa) d(v,x),mer(1,m,rt[x],rt[v]);
    for(int v:G[x]) if(v^fa) mer(1,m,rt[v],rt[x]),d(v,x);
    for(int i:Q[x]) ans[i]=q(1,i,1,m,rt[x]);
}
int main() {
    n=read();m=read();
    F(i,1,n) a[i]=read();
    F(i,2,n) {
        int x=read(),y=read();
        G[x]+=y;uG[y]+=x;
    }
    F(i,1,m) {
        int op=read(),x=read();
        if(op==1) {
            st[x]=i;
        } else if(op==2) {
            mo(st[x],i-1,a[x],1,m,rt[x]);st[x]=0;
        } else Q[x]+=i,Q[0]+=i;
    } F(x,1,n) if(st[x]) mo(st[x],m,a[x],1,m,rt[x]);
    d(1);for(int i:Q[0]) printf("%d\n",ans[i]);
    return 0;
}