javaee论坛

普通会员

225648

帖子

98

回复

112

积分

楼主
发表于 2019-10-30 17:44:29 | 查看: 637 | 回复: 1

这篇博客主要是因为洛谷有毒瘤造了毒瘤数据卡树剖,所以只有全局平衡二叉树能过(而且代码还比树剖短。。。)并不想写题解,可以自己去洛谷题解区看。

update:

洛谷提交记录rank1是一个LCT?全局平衡二叉树没有LCT快?这什么鬼数据?

代码:

#include<bits/stdc++.h>#definelllonglong#definereregister#definegcget_char#definecsconstnamespaceIO{csintRlen=1<<22|1;charbuf[Rlen],*p1,*p2;inlinecharget_char(){return(p1==p2)&&(p2=(p1=buf)+fread(buf,1,Rlen,stdin),p1==p2)?EOF:*p1++;}inlinecharpeek(){return(p1==p2)&&(p2=(p1=buf)+fread(buf,1,Rlen,stdin),p1==p2)?EOF:*p1;}inlinecharget_alpha(){while(!isalpha(peek()))++p1;return*p1++;}template<typenameT>inlineTget(){charc;while(!isdigit(c=gc()));Tnum=c^48;while(isdigit(c=gc()))num=(num+(num<<2)<<1)+(c^48);returnnum;}inlineintgetint(){returnget<int>();}}usingnamespaceIO;usingstd::cerr;usingstd::cout;csintmod=1e4+7;inlineintadd(inta,intb){return(a+=b)>=mod?a-mod:a;}inlineintdec(inta,intb){return(a-=b)<0?a+mod:a;}inlineintmul(inta,intb){staticllr;r=(ll)a*b;returnr>=mod?r%mod:r;}inlineintpower(inta,intb,intres=1){for(;b;b>>=1,a=mul(a,a))(b&1)&&(res=mul(res,a));returnres;}inlinevoidInc(int&a,intb){(a+=b)>=mod&&(a-=mod);}inlinevoidDec(int&a,intb){(a-=b)<0&&(a+=mod);}inlinevoidMul(int&a,intb){a=mul(a,b);}intinv[mod];inlinevoidinit_inv(){inv[0]=inv[1]=1;for(intrei=2;i<mod;++i)inv[i]=mul(inv[mod%i],mod-mod/i);}structtag{intx,y;tag():x(1),y(0){}voidoperator=(intv){v?(x=v,y=0):(x=y=1);}voidoperator*=(intv){v?x=mul(x,v):++y;}voidoperator/=(intv){v?x=mul(x,inv[v]):--y;}operatorint(){returny?0:x;}};csintN=3e4+7,M=129;intn,S,invS,Q;structatom{inta[M],b[M],c[M],d[M];atom(){}voidoperator=(csatom&n){memcpy(a,n.a,sizeof(int)*S);memcpy(b,n.b,sizeof(int)*S);memcpy(c,n.c,sizeof(int)*S);memcpy(d,n.d,sizeof(int)*S);}};inlinevoidmerge(atom&C,csatom&A,csatom&B){for(intrei=0;i<S;++i){C.d[i]=add(add(A.d[i],B.d[i]),mul(A.c[i],B.b[i]));C.c[i]=add(mul(B.a[i],A.c[i]),B.c[i]);C.b[i]=add(mul(A.a[i],B.b[i]),A.b[i]);C.a[i]=mul(A.a[i],B.a[i]);}}inlinevoidFWT(int*A){for(intrei=1;i<S;i<<=1)for(intrej=0;j<S;j+=i<<1)for(intrek=0;k<i;++k){intx=A[j|k],y=A[i|j|k];A[j|k]=add(x,y),A[i|j|k]=dec(x,y);}}inlinevoidIFWT(int*A){FWT(A);for(intrei=0;i<S;++i)Mul(A[i],invS);}intnxt[N<<1],to[N<<1],last[N],ecnt;inlinevoidaddedge(intu,intv){nxt[++ecnt]=last[u],last[u]=ecnt,to[ecnt]=v;nxt[++ecnt]=last[v],last[v]=ecnt,to[ecnt]=u;}intsiz[N],son[N];voidpre_dfs(intu,intp){siz[u]=1;for(intree=last[u],v=to[e];e;v=to[e=nxt[e]])if(v!=p){pre_dfs(v,u),siz[u]+=siz[v];if(siz[v]>siz[son[u]])son[u]=v;}}intval[N],fw[M][M],ans[M];namespaceGBT{intrt;intson[N][2],fa[N],lsiz[N];intst[N],top;atomw[N],a[N];tagLF[N][M];intLH[N][M];inlinevoidinit_node(intu){int*w=fw[val[u]];atom&a=GBT::w[u];for(intrei=0;i<S;++i){a.a[i]=mul(LF[u][i],w[i]);a.d[i]=add(a.a[i],LH[u][i]);}memcpy(a.b,a.a,sizeof(int)*S);memcpy(a.c,a.a,sizeof(int)*S);}inlinevoidpushup(intu){merge(a[u],a[son[u][0]],w[u]);merge(a[u],a[u],a[son[u][1]]);}inlinevoidins(intu,intv){int*t1=a[v].c,*t2=a[v].d;for(intrei=0;i<S;++i){LF[u][i]*=add(t1[i],1);Inc(LH[u][i],t2[i]);}}inlinevoiddel(intu,intv){int*t1=a[v].c,*t2=a[v].d;for(intrei=0;i<S;++i){LF[u][i]/=add(t1[i],1);Dec(LH[u][i],t2[i]);}}inlineintsubbuild(intl,intr){if(l==r){pushup(st[l]);returnst[l];}if(l>r)return0;inttot=0;for(intrei=l;i<=r;++i)tot+=lsiz[st[i]];for(intrei=l,now=lsiz[st[i]];i<=r;now+=lsiz[st[++i]])if(now*2>=tot){son[st[i]][0]=subbuild(l,i-1),son[st[i]][1]=subbuild(i+1,r);fa[son[st[i]][0]]=fa[son[st[i]][1]]=st[i];pushup(st[i]);returnst[i];}cerr<<"error1\n";abort();}inlineintbuild(intu){for(intrep=u;p;p=::son[p])lsiz[p]=siz[p]-siz[::son[p]];for(intrep=u;p;p=::son[p])for(intree=last[p],v=to[e];e;v=to[e=nxt[e]])if(!lsiz[v]){v=build(v);fa[v]=p;ins(p,v);}top=0;for(intrep=u;p;p=::son[p])st[++top]=p,init_node(p);std::reverse(st+1,st+top+1);returnsubbuild(1,top);}boolgot;inlinevoidget_ans(){//cerr<<"get_ans\n";if(got)return;got=true;memcpy(ans,a[rt].d,sizeof(int)*S);IFWT(ans);}inlineboolisroot(intu){returnson[fa[u]][1]!=u&&son[fa[u]][0]!=u;}inlinevoidmodify(){got=false;intu=getint();val[u]=getint();init_node(u);while(u){if(isroot(u)&&fa[u]){del(fa[u],u);pushup(u);ins(fa[u],u);init_node(fa[u]);}elsepushup(u);u=fa[u];}}inlinevoidinit(){for(intrei=1;i<=n;++i)for(intrej=0;j<S;++j)LF[i][j]=1;std::fill(w->a,w->a+S,1);std::fill(a->a,a->a+S,1);rt=build(1);}}signedmain(){#ifdefzxyoifreopen("cut.in","r",stdin);#endifinit_inv();n=getint(),invS=inv[S=getint()];for(intrei=1;i<=n;++i)val[i]=getint();for(intrei=1;i<n;++i)addedge(getint(),getint());for(intrei=0;i<M;++i)fw[i][i]=1,FWT(fw[i]);pre_dfs(1,0);GBT::init();Q=getint();while(Q--){switch(get_alpha()){case'Q':GBT::get_ans();cout<<ans[getint()]<<"\n";break;case'C':GBT::modify();}}return0;}

普通会员

0

帖子

98

回复

105

积分
沙发
发表于 2019-12-09 22:03:44

还是很厉害的

您需要登录后才可以回帖 登录 | 立即注册

触屏版| 电脑版

技术支持 历史网 V2.0 © 2016-2017