网站开发网页,网站的域名,百度网页怎么制作,开发公司更换物业公司的请示正题
题目链接:https://darkbzoj.tk/problem/3729 题目大意
给出nnn个点的一棵树#xff0c;第iii个节点上有aia_iai个石子#xff0c;然后每次可以选择不超过LLL个石子移动到父节点处。要求支持操作
以一个节点的子树进行博弈是否有先手必胜修改一个节点的石子个数插入…正题
题目链接:https://darkbzoj.tk/problem/3729 题目大意
给出nnn个点的一棵树第iii个节点上有aia_iai个石子然后每次可以选择不超过LLL个石子移动到父节点处。要求支持操作
以一个节点的子树进行博弈是否有先手必胜修改一个节点的石子个数插入一个新的叶子
1≤n,m≤5×104,1≤L≤1091\leq n,m\leq 5\times 10^4,1\leq L\leq 10^91≤n,m≤5×104,1≤L≤109 解题思路
额首先是阶梯博弈和巴什博弈的缝合怪
巴什博弈结论是石头直接模上一个L1L1L1然后阶梯博弈要分奇偶深度
然后不带插入的话就是维护dfsdfsdfs序区间的奇数深度和偶数深度的异或和就好了但是要插入所以要一次改一堆dfsdfsdfs序所以要用SplaySplaySplay维护就好了。
时间复杂度O(mlogn)O(m\log n)O(mlogn) code
#includecstdio
#includecstring
#includealgorithm
using namespace std;
const int N2e510;
struct node{int to,next;
}a[N1];
int n,m,L,tot,ls[N],dep[N],v[2][N];
int t[N][2],fa[N],w[2][N],d[N],last;
bool Direct(int x)
{return t[fa[x]][1]x;}
void PushUp(int x){if(!x)return;w[0][x]v[0][x]^w[0][t[x][0]]^w[0][t[x][1]];w[1][x]v[1][x]^w[1][t[x][0]]^w[1][t[x][1]];d[x]min(dep[x],min(d[t[x][0]],d[t[x][1]]));return;
}
void Rotate(int x){int yfa[x],zfa[y];int xsDirect(x),ysDirect(y);int wt[x][xs^1];t[x][xs^1]y;t[y][xs]w;if(z)t[z][ys]x;if(w)fa[w]y;fa[y]x;fa[x]z;PushUp(y);PushUp(x);return;
}
void Splay(int x,int f){while(fa[x]!f){int yfa[x];if(fa[y]f)Rotate(x);else if(Direct(x)Direct(y))Rotate(y),Rotate(x);else Rotate(x),Rotate(x);}return;
}
int Find(int x,int k){if(d[t[x][0]]k)Find(t[x][0],k);if(dep[x]k)return x;return Find(t[x][1],k);
}
void addl(int x,int y){a[tot].toy;a[tot].nextls[x];ls[x]tot;return;
}
void dfs(int x,int F){t[last][1]x;fa[x]last;lastx;dep[x]dep[F]1;if(dep[x]1)swap(v[0][x],v[1][x]);for(int ils[x];i;ia[i].next){int ya[i].to;if(yF)continue;dfs(y,x);}return;
}
void Downdata(int x)
{PushUp(x);if(fa[x])Downdata(fa[x]);return;}
int main()
{freopen(1.in,r,stdin);freopen(1.out,w,stdout);scanf(%d%d,n,L);d[0]n1;for(int i1;in;i)scanf(%d,v[0][i]),v[0][i]%(L1);for(int i1;in;i){int x,y;scanf(%d%d,x,y);addl(x,y);addl(y,x);}lastN-1;d[N-1]dep[N-1]n1;dfs(1,0);t[last][1]N-2;fa[N-2]last;lastN-2;d[N-2]dep[N-2]n1;Downdata(last);int sum0;scanf(%d,m);for(int i1;im;i){int op,z,x,y;scanf(%d,op);if(op1){scanf(%d,x);x^sum;if(i106)i,i--;Splay(x,0);if(d[t[x][1]]dep[x]){if(w[(dep[x]1)^1][t[x][1]])puts(MeiZ),sum;else puts(GTY);}else{yFind(t[x][1],dep[x]);Splay(y,x);if(w[(dep[x]1)^1][t[y][0]])puts(MeiZ),sum;else puts(GTY);}}else if(op2){scanf(%d%d,x,y);x^sum;y^sum;Splay(x,0);v[dep[x]1][x]y%(L1);PushUp(x);}else if(op3){scanf(%d%d%d,x,y,z);z^sum;x^sum;y^sum;dep[y]dep[x]1;v[dep[y]1][y]z%(L1);PushUp(y);Splay(x,0);int kt[x][1];while(t[k][0])kt[k][0];Splay(k,x);fa[y]k;t[k][0]y;PushUp(k);PushUp(x);}}return 0;
}
