Cptraser/ 十月 27, 2018/ 2018.10/ 0 comments

BZOJ3720 Gty的妹子树

题面传送门

大码力题,打的心累。
看过题面以后,你就可以开始长征了。

首先是没有加点和修改的情况,单纯的查询可以用DFS序+主席树+离散化实现。
但如果加上修改和加点的话……
我们就对其分块!
对修改和加点分块,每经过一块就重构一次主席树。
然后枚举这块里的修改和加点:

  • 对于修改,如果是修改原树上的点,要增减修改之后对主席树统计出来答案的影响
  • 对于加点和修改新点的修改,对其最后的值增加贡献

取块大小为O(\sqrt {Mlog_2M})时最优。

Code:

#include <cmath>
#include <cstdio>
#include <cctype>
#include <algorithm>
#define V 40005
using namespace std;


char tc(){static char tr[1000000],*A=tr,*B=tr;return A==B&&(B=(A=tr)+fread(tr,1,1000000,stdin),A==B)?EOF:*A++;}
void read(int &x){char c;for(;!isdigit(c=tc()););for(x=c-48;isdigit(c=tc());x=(x<<1)+(x<<3)+c-48);}

int N,M,Size,tim,fc,Ans,opt,u,x,y,Now,id[V<<1];
int head[V<<1],to[V<<2],nxt[V<<2],Cot,Cnt,Cntpro;
#define Add(x,y) (nxt[++Cot]=head[x],to[Cot]=y,head[x]=Cot)

struct Lts{
    int x,id;
    bool operator<(const Lts&P)const{
        return x<P.x;
    }
}R[V<<1];//离散化数组

struct Tree{int L,R,x,dx,odl,odlpre;}D[V<<1];
int Sum[V*20],Ls[V*20],Rs[V*20],Rt[V<<1],Tp,Fa[V<<1];

void Ad(int &Node,int L,int R,int P){
    Sum[++Tp]=Sum[Node],Ls[Tp]=Ls[Node],Rs[Tp]=Rs[Node],Node=Tp;
    Sum[Node]++;
    if(L>=R)return ;
    int Mid=(L+R)>>1;
    if(Mid>=P)Ad(Ls[Node],L,Mid,P);
    else Ad(Rs[Node],Mid+1,R,P);
}

int Query(int x,int y,int L,int R,int Ql,int Qr){
    if(L>=Ql&&R<=Qr)return Sum[y]-Sum[x];
    int Mid=(L+R)>>1,Ans=0;
    if(Mid>=Ql)Ans+=Query(Ls[x],Ls[y],L,Mid,Ql,Qr);
    if(Mid<Qr) Ans+=Query(Rs[x],Rs[y],Mid+1,R,Ql,Qr);
    return Ans;
}

void Build(int Node,int fa){
    id[Node]=++fc;
    D[Node].L=fc,Fa[Node]=fa;
    Ad(Rt[fc]=Rt[fc-1],1,Now,D[Node].x);
    for(int i=head[Node];i;i=nxt[i])if(fa^to[i])Build(to[i],Node);
    D[Node].R=fc;
}//重构主席树

struct Node{int x[V],odl[V],odlpre[V],Top;}U1,U2;
void Rebuild(void){
    for(int i=1;i<=Cnt;i++)R[i].x=D[i].dx=D[i].odl,R[i].id=i;
    sort(R+1,R+Cnt+1);
    Cntpro=Cnt,Now=0,U1.Top=U2.Top=0;
    for(int i=1;i<=Cnt;i++){
        if(R[i].x^R[i-1].x)Now++;
        D[R[i].id].x=Now;
    }fc=Tp=0,Build(1,0);
}

int dfs(int x,int v){
    int tot=D[x].odl>v;
    for(int i=head[x];i;i=nxt[i])tot+=dfs(to[i],v);
    return tot;
}

int Query(int u,int x){
    if(!D[u].x)return dfs(u,x);
    int l=1,r=Cntpro,dist=-1;
    while(l<=r){
        int Mid=(l+r)>>1;
        if(R[Mid].x>x)dist=Mid,r=Mid-1;
        else l=Mid+1;
    }//二分
    int tot=0;
    if(~dist)tot+=Query(Rt[D[u].L-1],Rt[D[u].R],1,Now,D[R[dist].id].x,Now);
    for(int i=1;i<=U1.Top;i++)if(id[U1.x[i]]>=D[u].L&&id[U1.x[i]]<=D[u].R&&D[U1.x[i]].x){
        if(U1.odlpre[i]<=x&&U1.odl[i]>x)tot++;
        if(U1.odlpre[i]>x&&U1.odl[i]<=x)tot--;
    }//增减修改的贡献
    for(int i=1;i<=U2.Top;i++)
        if(id[Fa[U2.x[i]]]>=D[u].L&&id[Fa[U2.x[i]]]<=D[u].R&&D[U2.x[i]].odl>x)tot++;
    return tot;
}

void Change(int u,int x){
    U1.x[++U1.Top]=u;
    D[u].odlpre=D[u].odl,D[u].odl=x;
    U1.odlpre[U1.Top]=D[u].odlpre,U1.odl[U1.Top]=D[u].odl;
}//需要记录修改前后的值

void Joinin(int u,int x){
    U2.x[++U2.Top]=++Cnt;
    R[Cnt].x=x,R[Cnt].id=Cnt,D[Cnt].dx=D[Cnt].odlpre=D[Cnt].odl=x;
    Fa[Cnt]=!D[u].x?Fa[u]:u,Add(u,Cnt);//记得加边
}

int main()
{
    read(N),R[0].x=-1;
    for(int i=1;i<N;i++)read(x),read(y),Add(x,y),Add(y,x);
    for(int i=1;i<=N;i++)
        read(x),R[++Cnt].x=D[i].dx=D[i].odlpre=D[i].odl=x,R[Cnt].id=i;
    Rebuild();
    for(read(M),Size=sqrt(M*log2(M))+0.5,tim=Size;M;M--){
        if(!tim)Rebuild(),tim=Size;//分块重构
        read(opt),read(u),read(x),u^=Ans,x^=Ans;
        if(opt==0)printf("%d\n",Ans=Query(u,x));
        if(opt==1)Change(u,x),tim--;
        if(opt==2)Joinin(u,x),tim--;
    }
}
Share this Post

Leave a Comment

电子邮件地址不会被公开。 必填项已用*标注

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>
*
*