【洛谷P2137】Gty的妹子树

mrsrz 11月 29, 2019

线段树合并，操作分块

题目大意：

给定一棵有根树，点带点权。有三个操作：

给定 $u,x$，询问子树 $u$ 中点权大于 $x$ 的点的个数。
给定 $u,x$，把点 $u$ 的点权改为 $x$。
给定 $u,x$，新加一个点，点权为 $x$，父亲为 $u$。

强制在线。

题解：

操作分块。

对于每段操作，我们把点分为两种：原来的点和新加入的点。

查询的时候，如果 $u$ 是原来的点，那么先直接查询原来的点构成的树的子树中的答案，然后再暴力枚举新加入的点然后判断。如果 $u$ 是新加入的点，则暴力搜索这整棵子树求答案。

查询子树信息可以使用可持久化线段树合并。

考虑对点权的修改对答案的影响。如果修改的是新加入的点的点权，则直接改就好了。

如果修改的是原来的点的点权，那么线段树合并处求得的答案就不正确了。我们存下来哪些点被修改过了，然后查询的时候，枚举这些被修改的点，分别看一下修改前和修改后的权值，调整贡献即可。

当新加入的点和存下来的被修改的点的数量达到一定值时重构整棵树并重新线段树合并即可。

时间复杂度 $O(n\sqrt{n\log n})$。

Code：

#include<iostream>
#include<cstring>
using namespace std;
const int N=6e4+5,lim=(1u<<31)-1,M=N*65,siz=1024;
int head[N],cnt,n,nod,m,a[N],nn,fa[N],ans,prd[N],na[N],in[N],idx,out[N];
struct edge{
    int to,nxt;
}e[N<<1];
int ls[M],rs[M],sz[M],rt[N];
int stc[N],tc;
inline void addedge(int u,int v){
    e[++cnt]=(edge){v,head[u]},head[u]=cnt;
    e[++cnt]=(edge){u,head[v]},head[v]=cnt;
}
void add(int&o,int l,int r,const int&pos){
    if(!o)o=++nod,ls[o]=rs[o]=sz[o]=0;
    ++sz[o];
    if(l<r){
        const int mid=(unsigned)(l+r)>>1;
        if(pos<=mid)add(ls[o],l,mid,pos);else add(rs[o],mid+1,r,pos);
    }
}
int query(int o,int l,int r,const int&k){
    if(!o)return 0;
    if(k<l)return sz[o];
    if(l==r||k>=r)return 0;
    const int mid=(unsigned)(l+r)>>1;
    if(k<mid)return query(ls[o],l,mid,k)+sz[rs[o]];
    return query(rs[o],mid+1,r,k);
}
int merge(int ld,int rd,int l,int r){
    if(!ld||!rd)return ld|rd;
    int ret=++nod;ls[ret]=rs[ret]=sz[ret]=0;
    if(l==r){
        sz[ret]=sz[ld]+sz[rd];
        return ret;
    }
    const int mid=(unsigned)(l+r)>>1;
    ls[ret]=merge(ls[ld],ls[rd],l,mid);
    rs[ret]=merge(rs[ld],rs[rd],mid+1,r);
    sz[ret]=sz[ls[ret]]+sz[rs[ret]];
    return ret;
}
void dfs(int now,int pre){
    in[now]=++idx;
    rt[now]=0;
    add(rt[now],0,lim,a[now]);
    for(int i=head[now];i;i=e[i].nxt)if(e[i].to!=pre)
        fa[e[i].to]=now,dfs(e[i].to,now),rt[now]=merge(rt[now],rt[e[i].to],0,lim);
    out[now]=idx;
}
void dfs2(int u,int pre,const int&k){
    ans+=a[u]>k;
    for(int i=head[u];i;i=e[i].nxt)
        if(e[i].to!=pre)dfs2(e[i].to,u,k);
}
void build(){
    nod=idx=0;
    dfs(1,0);
}
inline bool check(int u,int x){return in[u]<=in[x]&&in[x]<=out[u];}
int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n;nn=n;
    memset(na,-1,sizeof na);
    for(int i=1,u,v;i<n;++i){
        cin>>u>>v;
        addedge(u,v);
    }
    for(int i=1;i<=n;++i)cin>>a[i];
    build();
    for(cin>>m;m--;){
        int op,u,x;
        cin>>op>>u>>x;
        u^=ans,x^=ans;
        switch(op){
            case 0:
                ans=0;
                if(u<=n){
                    ans=query(rt[u],0,lim,x);
                    for(int i=n+1;i<=nn;++i)
                        if(check(u,prd[i])&&a[i]>x)++ans;
                    for(int i=1;i<=tc;++i)
                        if(check(u,stc[i]))
                            ans+=(na[stc[i]]>x?1:0)-(a[stc[i]]>x?1:0);
                }else dfs2(u,fa[u],x);
                cout<<ans<<'\n';
                break;
            case 1:
                if(u<=n){
                    if(!~na[u])stc[++tc]=u;
                    na[u]=x;
                }else a[u]=x;
                break;
            case 2:
                a[++nn]=x,fa[nn]=u,prd[nn]=u<=n?u:prd[u];
                addedge(nn,u);
        }
        if(nn-n+tc>=siz){
            for(int i=tc;i;--i)a[stc[i]]=na[stc[i]],na[stc[i]]=-1;
            tc=0;
            n=nn;
            build();
        }
    }
    return 0;
}