【BZOJ3720】Gty的妹子树（主席树+时间分块）

点此看题面

大致题意： 给你一棵有根树，让你支持三种操作：询问某子树中大于\(x\)的值的个数，把某一节点值改成\(x\)，添加一个父节点为\(u\)、权值为\(x\)的节点。

关于此题做法

此题做法真的是五花八门啊，主要做法貌似有四种：

平衡树套平衡树。似乎没有人写。
树分块。官方正解，实际上能被菊花图卡掉，但是没有构造数据卡。
时间分块。即按照操作的次数进行分块，这也是我的做法。
代码分块。即分类讨论。

下面，我们主要讲一讲如何用时间分块处理这题。

主席树的暴力做法

我们先来了解一下如何用主席树来暴力求解此题。

首先，我们\(dfs\)遍历一遍题目中给出的树，将其\(dfs\)序存储下来。

然后，我们用主席树对其进行维护，每次可以轻松求出小于\(k\)的数的个数。

对于修改操作，我们可以... ...直接重构一棵主席树... ...

不难发现，这种方法显然过于暴力，可以被轻松卡掉。

时间分块

不停地重构的确太费时间，那么我们能不能不重构呢？

显然不重构也不可以，依然容易被卡。

所以，我们就要考虑时间分块，即隔一段时间重构一次，从而保证复杂度。

如何处理修改操作

既然要隔时间重构，我们就要想一个办法来处理修改操作。

对于添加节点操作，我们可以记录一下它的祖先中深度最大的一个位于树中的节点\(g_i\)。

对于修改元素值操作，如果是没有加入树中的新节点，暴力修改即可。否则我们可以考虑用一个栈，将所有被修改过值的元素存储下来，并记录下其被修改后的值。

如何处理询问操作

对于询问操作，如果该节点不在树中，我们可以直接暴力求解。

否则，我们首先用主席树求出已经在树中的元素的答案。对于没有加入到树中的节点，我们只需判断\(g_i\)是否处于当前询问节点的子树中，就可以判断该节点是否会对答案造成贡献了。而对于既在栈中又在当前询问子树中的节点，我们考虑先减去其原先值的贡献，然后再计算新值的贡献。

关于重构

前面已经说了，隔一段时间，我们就要将这段时间内的修改操作全部更新到树上去，从而保证复杂度。

我们具体操作的事情有以下几件：

将栈中的元素值全部修改到原元素上，然后清空栈。
重求一遍\(dfs\)序。
更新主席树要用的离散化数组。
重构主席树。

这应该都还是比较容易实现的。

其实，重构的过程与初始化的过程完全可以放在同一个函数中！

这样一来，这道题就轻松解决了。

注意，这道题有比较多的细节，一不小心就会写炸！

具体实现见代码。

代码

#include<bits/stdc++.h>

#define ten(x) (((x)<<3)+((x)<<1))

#define N 100000

#define LogN 20

#define add(x,y) (e[++ee].nxt=lnk[x],e[lnk[x]=ee].to=y)

using namespace std;

int n,m,top=0,ee=0,g[N+5],Val[N+5],lnk[N+5],Stack[N+5],NewVal[N+5],InStack[N+5];

struct edge

{

    int to,nxt;

}e[N+5];

class FIO

{

    private:

        #define Fsize 100000

        #define tc() (A==B&&(B=(A=Fin)+fread(Fin,1,Fsize,stdin),A==B)?EOF:*A++)

        #define pc(ch) (FoutSize<Fsize?Fout[FoutSize++]=ch:(fwrite(Fout,1,Fsize,stdout),Fout[(FoutSize=0)++]=ch))

        int Top,FoutSize;char ch,*A,*B,Fin[Fsize],Fout[Fsize],Stack[Fsize];

    public:

        FIO() {A=B=Fin;}

        inline void read(int &x) {x=0;while(!isdigit(ch=tc()));while(x=ten(x)+(ch&15),isdigit(ch=tc()));}

        inline void write(int x) {if(!x) return (void)(pc('0'));while(x) Stack[++Top]=x%10+48,x/=10;while(Top) pc(Stack[Top--]);}

        inline void write_char(char x) {pc(x);}

        inline void clear() {fwrite(Fout,1,FoutSize,stdout);}

}F;

class Class_ChairmanTree//主席树

{

    private:

        int n,tot,Root[N+5];

        struct node

        {

            int Size,Son[2];

            inline void Clear() {Size=Son[0]=Son[1]=0;}

        }node[N*LogN+5];

        inline void Build(int l,int r,int &rt)

        {

            if(node[rt=++tot].Clear(),!(l^r)) return;

            register int mid=l+r>>1;

            Build(l,mid,node[rt].Son[0]),Build(mid+1,r,node[rt].Son[1]);

        }

        inline void ins(int l,int r,int &rt,int lst,int val)

        {

            if(node[rt=++tot]=node[lst],++node[rt].Size,!(l^r)) return;

            register int mid=l+r>>1;

            val<=mid?ins(l,mid,node[rt].Son[0],node[lst].Son[0],val):ins(mid+1,r,node[rt].Son[1],node[lst].Son[1],val);

        }

        inline int qry(int l,int r,int rt1,int rt2,int val)

        {

            if(!(l^val)) return node[rt2].Size-node[rt1].Size;

            register int mid=l+r>>1;

            if(val<=mid) return qry(l,mid,node[rt1].Son[0],node[rt2].Son[0],val)+node[node[rt2].Son[1]].Size-node[node[rt1].Son[1]].Size;

            return qry(mid+1,r,node[rt1].Son[1],node[rt2].Son[1],val);

        }

    public:

        inline void Init(int len) {tot=0,Build(1,n=len,Root[0]);}

        inline void Insert(int v,int val) {ins(1,n,Root[v],Root[v-1],val);}

        inline int Query(int ql,int qr,int val) {return qry(1,n,Root[ql-1],Root[qr],val);}

}ChairmanTree;

class Class_DfnSolver//求DFS序

{

    public:

        int d,dfn[N+5],fac[N+5],Size[N+5];

    private:

        inline void dfs(int x,int lst)

        {

            register int i;

            for(Size[fac[dfn[x]=++d]=x]=1,i=lnk[x];i;i=e[i].nxt)

                if(e[i].to^lst) dfs(e[i].to,x),Size[x]+=Size[e[i].to];

        }

    public:

        inline void Init() {dfs(1,d=0);}

        inline bool Include(int x,int y) {return dfn[x]<=dfn[y]&&dfn[y]<dfn[x]+Size[x];}//求y是否在x的子树中

}DfnSolver;

class Discretization//离散化

{

    private:

        int num[N+5];

    public:

        int cnt;

        inline void Init(int len,int *data)

        {

            for(register int i=1;i<=len;++i) num[i]=data[i];

            sort(num+1,num+len+1),cnt=unique(num+1,num+len+1)-num-1;

        }

        inline int get_val(int x)

        {

            register int l=1,r=cnt,mid=l+r>>1;

            for(;l<=r;mid=l+r>>1) num[mid]<x?l=mid+1:r=mid-1;

            return l;

        }

        inline bool Include(int x) {return num[cnt]>=x;}

}D;

inline int BruteForce(int x,int val)//暴力求解未加入树中节点的答案

{

    register int i,res=Val[x]>=val;

    for(i=lnk[x];i;i=e[i].nxt) res+=BruteForce(e[i].to,val);//统计答案

    return res;

}

inline void ReBuild()//初始化&重构

{

    while(top) Val[Stack[top]]=NewVal[Stack[top]],InStack[Stack[top--]]=0;//将栈中的元素值全部修改到原元素上，然后清空栈

    DfnSolver.Init(),D.Init(n=m,Val),ChairmanTree.Init(D.cnt);//重求一遍dfs序,并更新主席树要用的离散化数组

    for(register int i=1;i<=n;++i) ChairmanTree.Insert(i,D.get_val(Val[DfnSolver.fac[i]]));//重构主席树

}

int main()

{

    register int i,Q,op,x,y,ans=0,time_tot=0,Size=sqrt(N*LogN);

    for(F.read(n),m=n,i=1;i<n;++i) F.read(x),F.read(y),add(x,y),add(y,x);

    for(i=1;i<=n;++i) F.read(Val[i]);

    for(ReBuild(),F.read(Q);Q;--Q)//初始化

    {

        F.read(op),F.read(x),F.read(y),x^=ans,y^=ans;//注意强制在线

        switch(op)

        {

            case 0:

                if(++y,x>n) {F.write(ans=BruteForce(x,y)),F.write_char('\n');break;}//对于未被加入树中的节点，暴力求解答案

                ans=D.Include(y)?ChairmanTree.Query(DfnSolver.dfn[x],DfnSolver.dfn[x]+DfnSolver.Size[x]-1,D.get_val(y)):0;//先求出树中节点的答案

                for(i=n+1;i<=m;++i) if(DfnSolver.Include(x,g[i])&&Val[i]>=y) ++ans;//对于没有加入到树中的节点，判断g[i]是否处于当前子树中

                for(i=1;i<=top;++i) if(DfnSolver.Include(x,Stack[i])) Val[Stack[i]]>=y&&--ans,NewVal[Stack[i]]>=y&&++ans;//对于既在栈中又在当前询问子树中的节点，先减去其原先值的贡献，然后再计算新值的贡献

                F.write(ans),F.write_char('\n');

            break;

            case 1:

                if(x>n) {Val[x]=y;break;}//对于未加入到树中的节点，直接修改

                if(!InStack[x]) InStack[Stack[++top]=x]=1;//如果不在栈中，将其加入栈中

                NewVal[x]=y;//存储下新的值

            break;

            case 2:

                Val[++m]=y,add(x,m),g[m]=x<=n?x:g[x];//加入一个节点，求出g[x]

            break;

        }

        if(op&&++time_tot>=Size) ReBuild(),time_tot=0;//当修改操作达到一定次数时重构

    }

    return F.clear(),0;

}

巴特西