洛谷P3613 睡觉困难综合征

传送门

题解

人生第一道由乃……

做这题之前应该先去把这一题给切掉->这里

我的题解->这里

然后先膜一波zsy大佬和flashhu大佬

大体思路就是先吧全0和全1的都跑答案，然后按位贪心

我一开始想到的是每一次split，然后直接一个一个跑

后来发现时间复杂度肯定爆炸……

看了看网上其他的，发现说的都不怎么清楚……结果硬是理解了好久才明白……

先考虑一下LCT维护什么

定义$f0$为全0走过一条路径之后的答案，$f1$表示全1走过一条路径之后的答案

LCT需要维护的是splay中以x为根的子树里，从前往后遍历（即中序遍历）的$f0$和$f1$以及从后往前（即与前面完全相反的顺序）的$f0$和$f1$

比如有一棵splay，x是其中一个点，它在splay中有两个儿子，左儿子y和右儿子z，那么从前往后遍历就是路径y->x->z，从后往前就是路径z->x->y

然后思考，如果已经有了两个区间，该如何合并他们

假如说我们有两段计算出答案的区间，分别对应f0,f1和g0,g1。我们设合并后的答案是h0,h1，那么有如下式子：

$h0=(~f0&g0)+(f0&g1)$

$h1=(~f1&g0)+(f1&g1)$

为啥？

全0走到最后的话，先考虑两种情况

全0走到中间等于1的那几位，走后一半的答案等同于全1走后一半的这几位的答案

全0走到中间等于0的那几位，走后一半的答案等同于全0走后一半的这几位的答案

只需要把这两个答案加起来即可

（ps：这里默认f为前一半的答案，g为后一半的答案）

全1走到最后同理

然后就是几个细节

1.pushdown的时候因为有翻转标记，从前往后走和从后往前走的答案也要交换

2.按位贪心用1做位运算的时候，记得把1设成unsigned long long（简单来说就是设一个ull变量让它等于1）（我就是因为一开始直接用1做位运算结果死都调不出来……）

 // luogu-judger-enable-o2

 //minamoto

 #include<iostream>

 #include<cstdio>

 #define ll unsigned long long

 using std::swap;

 using std::cout;

 using std::endl;

 #define getc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)

 char buf[<<],*p1=buf,*p2=buf;

 inline ll read(){

     #define num ch-'0'

     char ch;bool flag=;ll res;

     while(!isdigit(ch=getc()))

     (ch=='-')&&(flag=true);

     for(res=num;isdigit(ch=getc());res=res*+num);

     (flag)&&(res=-res);

     #undef num

     return res;

 }

 char obuf[<<],*o=obuf;

 void print(ll x){

     if(x>) print(x/);

     *o++=x%+;

 }

 const int N=;

 struct node{

     ll f0,f1;

     inline node operator +(const node &b)const

     {

         node a;

         a.f0=(~f0&b.f0)|(f0&b.f1);

         a.f1=(~f1&b.f0)|(f1&b.f1);

         return a;

     }

 }f[N],l[N],r[N];

 int fa[N],ch[N][],s[N],rev[N],top,tot;

 int ver[N<<],head[N],Next[N<<];

 inline void add(int u,int v){

     ver[++tot]=v,Next[tot]=head[u],head[u]=tot;

     ver[++tot]=u,Next[tot]=head[v],head[v]=tot;

 }

 inline bool isroot(int x){return ch[fa[x]][]!=x&&ch[fa[x]][]!=x;}

 #define ls ch[x][0]

 #define rs ch[x][1]

 inline void pushup(int x){

     l[x]=r[x]=f[x];

     if(ls) l[x]=l[ls]+l[x],r[x]=r[x]+r[ls];

     if(rs) l[x]=l[x]+l[rs],r[x]=r[rs]+r[x];

 }

 inline void pushr(int x){

     swap(ls,rs),swap(l[x],r[x]),rev[x]^=;

 }

 inline void pushdown(int x){

     if(rev[x]&&x){

         pushr(ls),pushr(rs),rev[x]=;

     }

 }

 void rotate(int x){

     int y=fa[x],z=fa[y],d=ch[y][]==x;

     if(!isroot(y)) ch[z][ch[z][]==y]=x;

     fa[x]=z,fa[y]=x,fa[ch[x][d^]]=y,ch[y][d]=ch[x][d^],ch[x][d^]=y,pushup(y);

 }

 void splay(int x){

     s[top=]=x;for(int i=x;!isroot(i);i=fa[i]) s[++top]=fa[i];

     while(top) pushdown(s[top--]);

     for(int y=fa[x],z=fa[y];!isroot(x);y=fa[x],z=fa[y]){

         if(!isroot(y))

         ((ch[y][]==x)^(ch[z][]==y))?rotate(x):rotate(y);

         rotate(x);

     }

     pushup(x);

 }

 void access(int x){

     for(int y=;x;x=fa[y=x]){

         splay(x),rs=y,pushup(x);

     }

 }

 void makeroot(int x){

     access(x),splay(x),pushr(x);

 }

 void split(int x,int y){

     makeroot(x),access(y),splay(y);

 }

 void dfs(int u){

     for(int i=head[u];i;i=Next[i]){

         int v=ver[i];

         if(v==fa[u]) continue;

         fa[v]=u,dfs(v);

     }

     pushup(u);

 }

 int main(){

     //freopen("testdata.in","r",stdin);

     int n=read(),m=read(),k=read();

     for(int i=;i<=n;++i){

         int x=read();ll y=read();

         switch(x){

             case :f[i]=(node){,y};break;

             case :f[i]=(node){y,~};break;

             case :f[i]=(node){y,~y};break;

         }

     }

     for(int i=;i<n;++i){

         int u=read(),v=read();add(u,v);

     }

     dfs();

     while(m--){

         int opt=read(),x=read(),y=read();ll z=read();

         if(opt&){

             split(x,y);ll ans=,e=;

             for(int i=k-;i>=;--i){

                 if(l[y].f0&(e<<i)) ans|=e<<i;

                 else if((l[y].f1&(e<<i))&&z>=(e<<i)) ans|=e<<i,z^=e<<i;

             }

             print(ans),*o++='\n';

         }

         else{

             switch(y){

                 case :f[x]=(node){,z};break;

                 case :f[x]=(node){z,~};break;

                 case :f[x]=(node){z,~z};break;

             }

             splay(x);

         }

     }

     fwrite(obuf,o-obuf,,stdout);

     return ;

 }

巴特西

洛谷P3613 睡觉困难综合征

最新文章

热门文章