一.[NOI2014]起床困难综合症
题目描述
网址：https://daniu.luogu.org/problemnew/show/2114
大意：
有一条链，链上每一个节点包含一个位运算f 与 一个值w ， 一个值V从链首出发。
每经过一个点u ，有： \(V = V (f)w\)，其中f = {&、|、^}中的一个。
现在限定初始值V在区间\([0,R]\)中，请选定一个值，使得最终结果最大。
题目解法
史上最简单的NOI题目，当时肯定一群大佬秒A。
显然对于二进制，每一位的运算之间没有影响。
所以对于每一位，假设其为0或1,但进去暴力跑一遍的到结果res[0]与res[1]。
最后从高位向低位贪心，此位只要不超过R的限制就选择res=1的数字即可。
实现代码
不存在的
二、LuoguP3613 睡觉困难综合征
题目描述
网址：https://daniu.luogu.org/problemnew/show/3613
大意：
类似与上面那道题，树上的每一个节点有一个位运算符与一个权值。
那么现在这颗树会有两种操作：
- [1] 修改\(x,y,z\)：把x节点运算符修改为y，权值为z
- [2] 查询\(x,y,z\): 查询把x到y这条路径作为上题中的链，初值V属于\([0,z]\)时的最大结果。
对于每一个询问操作，选择一个初值V，使其通过路径后的值最大。
(节点数，操作数)<=100000,时限0.5 sec。
题目解法
Luogu 的大牛们一改，这题就变的相当有难度了。
现在路径在不断变化，链也不断在变化，不可能向之前那样暴力走一遍路径了。
显然需要分离路径要用到\(LCT\)。 \(LCT\)维护什么呢?
正确的做法是维护正向与反向两条道路每一位都为0的结果与每一位都为1的结果。
例如一个节点x的左右儿子分别为a、b，那么就要维护a->x->b与b->x->a两条路径。
这样才能保证LCT反转时结果正确。
我们记\(oder[i]\)表示正向的移动结果，\(dder[i]\)为反向的移动结果。
那么每一个点，我们维护四个东西：\(oder[i][0]\),\(oder[i][1]\),\(dder[i][0]\),\(dder[i][1]\)。
考虑一下如何转移,以正向结果的转移为例。
假设我们已经的得到了f0,f1与g0,g1, 现在合并。那么转移为：
\[h0 = ( No(f0) And (g0))Or((f0) And (g1))\]
\[h1 = ( No(f1) And (g0))Or((f1) And (g1))\]
写得正常点就是 h0 = (~f0 & g0) | ( f0 & g1) ; h1 = (~f1 & g0) | (f1 & g1)
即本次走了结果为0则第二次走的为0。结果为1的类似。
查询也类似上面那题。
这里注意此题中Makeroot时一定要先转再打标记，防止查询时对应点还没有旋转。
实现代码
#include<bits/stdc++.h>#define ll unsigned long long#define RG register#define IL inline#define maxn 100100#define lr oder#define rl dder#define Read() gi()using namespace std;ll fa[maxn],rev[maxn],ch[maxn][2],stk[maxn]; ll N,M,K,ze;struct Value{ll f0,f1;}oder[maxn],dder[maxn],val[maxn],G;IL ll gi(){ RG ll date = 0, m = 1; RG char ch = 0; while(ch!='-'&&(ch<'0'||ch>'9'))ch = getchar(); if(ch == '-'){m = -1; ch = getchar();} while(ch>='0' && ch<='9') {date=date*10+ch-'0'; ch = getchar();} return date*m;}IL void Reverse(RG ll x){ swap(ch[x][0],ch[x][1]); swap(oder[x],dder[x]); rev[x]^=1;}IL void PushDown(RG ll x){ if(!rev[x])return; Reverse(ch[x][0]); Reverse(ch[x][1]); rev[x] = 0; return;}IL Value Merge(RG Value F,RG Value S){ G.f0 = (~F.f0 & S.f0) | (F.f0 & S.f1); G.f1 = (~F.f1 & S.f0) | (F.f1 & S.f1); return G;}IL void PushUp(RG ll x){ oder[x] = dder[x] = val[x]; if(ch[x][0])oder[x] = Merge(oder[ch[x][0]],oder[x]); if(ch[x][0])dder[x] = Merge(dder[x],dder[ch[x][0]]); if(ch[x][1])oder[x] = Merge(oder[x],oder[ch[x][1]]); if(ch[x][1])dder[x] = Merge(dder[ch[x][1]],dder[x]);}IL bool Son(RG ll x){return ch[fa[x]][1] == x; }IL bool Isroot(RG ll x){return ch[fa[x]][0]!=x && ch[fa[x]][1]!=x; }IL void Rot(RG ll x){ RG int y = fa[x],z = fa[y],c = Son(x); if(!Isroot(y))ch[z][Son(y)] = x; fa[x] = z; ch[y][c] = ch[x][!c]; fa[ch[y][c]] = y; ch[x][!c] = y; fa[y] = x; PushUp(y);}IL void Splay(RG ll x){ RG ll top = 0; stk[++top] = x; for(RG ll i = x; !Isroot(i); i = fa[i])stk[++top] = fa[i]; while(top)PushDown(stk[top--]); for(RG ll y = fa[x]; !Isroot(x); Rot(x),y = fa[x]) if(!Isroot(y))Son(x) ^ Son(y) ? Rot(x) : Rot(y); PushUp(x);}IL void Access(RG ll x){ for(RG ll y = 0; x; y=x,x=fa[x])Splay(x),ch[x][1]=y,PushUp(x); }IL void Makeroot(RG ll x){Access(x); Splay(x); Reverse(x); }IL void Link(RG ll x,RG ll y){ Makeroot(x); fa[x]=y; }IL void Split(RG ll x,RG ll y){ Makeroot(x); Access(y); Splay(y); }IL ll Query(RG ll x,RG ll y,RG ll z){ Split(x,y); RG ll ans = 0,u = 1,num = 0; for(RG int i = 63; i >=0; i --){ if(oder[y].f0&(u<<i)){ans |= (u<<i);continue;} else if((oder[y].f1&(u<<i))) { if(num|(u<<i))<=z){ans |= (u<<i); num|=(u<<i);} } }return ans;}IL void Update(RG ll x,RG ll y,RG ll z){ Makeroot(x); if(y == 1)val[x] = (Value){ze,z}; if(y == 2)val[x] = (Value){z,~ze}; if(y == 3)val[x] = (Value){z,~z}; PushUp(x);}int main(){ N = gi(); M = gi(); K = gi(); RG ll t = 1; ze = 0; for(RG ll i = 1; i <= N; i ++){ RG ll kd = gi(),dt = gi(); if(kd == 1)val[i] = (Value){ze,dt}; if(kd == 2)val[i] = (Value){dt,~ze}; if(kd == 3)val[i] = (Value){dt,~dt}; } for(RG ll i = 1; i <= N-1; i ++){ RG ll xx = gi(),yy = gi(); Link(xx,yy); } while(M--) { RG ll op = gi(),x = gi(),y = gi(),z = gi(); if(op == 1)printf("%llu\n",Query(x,y,z)); if(op == 2)Update(x,y,z); }return 0;} 
