【BZOJ4811】睡觉困难综合征

题面

给你一个有n个点的树，每个点的包括一个位运算opt和一个权值x，位运算有&,l,^三种，分别用1,2,3表示。每次询问包含三个数x,y,z,初始选定一个数v。然后v依次经过从x到y的所有节点，每经过一个点i，v就变成v optixi，所以他想问你，最后到y时，希望得到的值尽可能大，求最大值？给定的初始值v必须是在[0,z]之间。每次修改包含三个数x,y,z，意思是把x点的操作修改为y，数值改为z。
0 <= n , m <= 100000 , k <= 64

分析

应该先做起床困难综合征！！！

同理我们用p0和p1来表示全0和全1经过这个点过后的值。刚好unsigned long long就能开下。

考虑线段树上这么合并呢？？

形象一点儿，合并其实就是再走过这一段。只不过从左往右走和从右往左走不同，要分别维护。

ans.p0=l.p0&r.p1 or (~l.p0&r.p0)  0出发的点的穿过l变成1再穿过r的结果  或者0出发的点穿过l变成0再穿过r的结果

1也同理，然后记得反着来一遍（先穿r再穿l）

然后坑点就是unsigned long long，最后那个类似起床困难综合征的贪心求答案的时候1一定要强制转成ull

代码

  1. #include<bits/stdc++.h>  
  2. using namespace std;  
  3. #define N 100010  
  4. #define lc (p<<1)  
  5. #define rc (p<<1|1)  
  6. #define mid (t[p].l+t[p].r>>1)  
  7. #define ull unsigned long long  
  8. int n,m,k,P,idx,cnt;  
  9. int d[N],f[N],id[N],rk[N],top[N],siz[N],son[N],first[N];  
  10. ull op[N][2];  
  11. struct email  
  12. {  
  13.     int u,v;  
  14.     int nxt;  
  15. }e[N*4];  
  16. struct tree  
  17. {  
  18.     int l,r;  
  19. }t[N*4];  
  20. struct px  
  21. {  
  22.     ull p1,p0;  
  23. }tl[N*4],tr[N*4];  
  24.   
  25. template<class T>  
  26. void read(T &x)  
  27. {  
  28.     x = 0;  
  29.     static char c = getchar();  
  30.     while(c < '0' || c > '9') c = getchar();  
  31.     while(c >= '0' && c <= '9')  
  32.     x = x * 10 + c - '0', c = getchar();  
  33. }  
  34.   
  35. inline px pushup(px l, px r)  
  36. {  
  37.     px ret;  
  38.     ret.p0=(l.p0&r.p1)|((~l.p0)&r.p0);  
  39.     ret.p1=(l.p1&r.p1)|((~l.p1)&r.p0);  
  40.     return ret;  
  41. }  
  42.   
  43. inline px change(ull op,ull w)  
  44. {  
  45.     px ans;  
  46.     if(op==1)ans.p0=0&w,ans.p1=(-1)&w;  
  47.     if(op==2)ans.p0=0|w,ans.p1=(-1)|w;  
  48.     if(op==3)ans.p0=0^w,ans.p1=(-1)^w;  
  49.     return ans;  
  50. }  
  51.   
  52. inline void build(int p,int l,int r)  
  53. {  
  54.     t[p].l=l,t[p].r=r;  
  55.     if(l==r)  
  56.     {  
  57.         tl[p]=tr[p]=change(op[rk[l]][0],op[rk[l]][1]);  
  58.         return ;  
  59.     }  
  60.     int bm=l+r>>1;  
  61.     build(lc,l,bm);build(rc,bm+1,r);  
  62.     tl[p]=pushup(tl[lc],tl[rc]);tr[p]=pushup(tr[rc],tr[lc]);  
  63. }  
  64.   
  65. inline void update(int p,int x,ull op,ull w)  
  66. {  
  67.     if(t[p].l==t[p].r){tl[p]=tr[p]=change(op,w);return;}  
  68.     if(x<=mid)update(lc,x,op,w);  
  69.     else update(rc,x,op,w);  
  70.     tl[p]=pushup(tl[lc],tl[rc]);tr[p]=pushup(tr[rc],tr[lc]);  
  71. }  
  72.   
  73. px query(int p,int ql,int qr,int fg)  
  74. {  
  75.     if (ql<=t[p].l&&qr>=t[p].r)  
  76.         if (fg) return tr[p];  
  77.         else return tl[p];  
  78.     if (qr<=mid) return query(lc,ql,qr,fg);  
  79.     else if (ql>mid) return query(rc,ql,qr,fg);  
  80.     else return pushup(query(lc+fg,ql,qr,fg),query(rc-fg,ql,qr,fg));  
  81. }  
  82.   
  83.   
  84.   
  85. inline void add(int u,int v)  
  86. {  
  87.     e[++cnt].nxt=first[u];first[u]=cnt;  
  88.     e[cnt].u=u;e[cnt].v=v;  
  89. }  
  90. inline void dfs1(int u,int fa,int dep)  
  91. {  
  92.     siz[u]=1;f[u]=fa;d[u]=dep;  
  93.     for(int i=first[u];i;i=e[i].nxt)  
  94.     {  
  95.         int v=e[i].v;  
  96.         if(v==fa)continue;  
  97.         dfs1(v,u,dep+1);  
  98.         siz[u]+=siz[v];  
  99.         if(siz[v]>siz[son[u]]||son[u]==0)  
  100.             son[u]=v;  
  101.     }  
  102. }  
  103. inline void dfs2(int u,int t)  
  104. {  
  105.     top[u]=t;id[u]=++idx;rk[idx]=u;  
  106.     if(son[u]==0)return ;  
  107.     dfs2(son[u],t);  
  108.     for(int i=first[u];i;i=e[i].nxt)  
  109.     {  
  110.         int v=e[i].v;  
  111.         if(v!=f[u]&&v!=son[u])  
  112.             dfs2(v,v);  
  113.     }  
  114. }  
  115.   
  116. px asktree(int x,int y)  
  117. {  
  118.     int fx=top[x],fy=top[y];  
  119.     px ans1=change(3,0),ans2=change(3,0);  
  120.     while(fx!=fy)  
  121.     {  
  122.         if(d[fx]>=d[fy])  
  123.         {  
  124.             ans1=pushup(ans1,query(1,id[fx],id[x],1));  
  125.             x=f[fx];fx=top[x];  
  126.         }  
  127.         else  
  128.         {  
  129.             ans2=pushup(query(1,id[fy],id[y],0),ans2);  
  130.             y=f[fy];fy=top[y];  
  131.         }  
  132.     }  
  133.     if(d[x]>=d[y])  
  134.         return pushup(pushup(ans1,query(1,id[y],id[x],1)),ans2);  
  135.     else  
  136.         return pushup(pushup(ans1,query(1,id[x],id[y],0)),ans2);  
  137. }  
  138.   
  139. void find(int x,int y,ull z)  
  140. {  
  141.     px ans=asktree(x,y);ull state=0,ret=0;  
  142.     for(int i=P;i;i--)  
  143.         if(ans.p0&((ull)1<<i-1))ret+=(ull)1<<i-1;  
  144.         else if((ans.p1&((ull)1<<i-1)&&((ull)1<<i-1)+state<=z))  
  145.                 ret+=(ull)1<<i-1,state+=(ull)1<<i-1;  
  146.     printf("%llu ",ret);  
  147. }  
  148.   
  149. int main()  
  150. {  
  151.     read(n);read(m);read(P);  
  152.     for(int i=1;i<=n;i++)read(op[i][0]),read(op[i][1]);  
  153.     for(int i=1;i<n;i++)  
  154.     {  
  155.         int u,v;  
  156.         read(u),read(v);  
  157.         add(u,v);add(v,u);  
  158.     }  
  159.     dfs1(1,1,1);dfs2(1,1);build(1,1,n);  
  160.     while(m--)  
  161.     {  
  162.         int flag,x,y;ull z;  
  163.         read(flag);read(x);read(y);read(z);  
  164.         if(flag==2)update(1,id[x],y,z);  
  165.         else find(x,y,z);  
  166.     }  
  167.     return 0;  
  168. }  

闲聊

此题调的时候出锅了，炸了一次

然后在debug下发现是query炸了 从头到尾看了query好几遍也不知道为啥炸了 好了重构了 query

重构了就没炸了 2333 所以有闲心的朋友可以找找不同 是哪里炸了TAT 反正最后看出来了。。其实很明显 【可能我瞎

还有我强调那个unsinged long long 是因为被教做人了

有一组数据

答案是 18446744073709551615 然而我输出的 18446744073709551614

唉TAT

调这题单循T T 这首歌【没错颜文字歌名

放了27次。。还好调了不是太久 27*3.5=94.5 min

感谢收看我的闲聊（fei hua）

【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/NSD-email0820/p/9844113.html