阿里巴巴手工活外发加工网,简述优化搜索引擎的方法,云南建设厅网站执业注册,麻将app软件开发正题
题目链接:https://www.luogu.com.cn/problem/P4332 题目大意
给出nnn个点的一棵有根三叉树#xff0c;保证每个点的儿子个数为333或者000#xff0c;每个叶子有一个权值000或111#xff0c;每个非叶子节点的权值是它儿子中权值较多的那个#xff0c;每次修改一个叶子…正题
题目链接:https://www.luogu.com.cn/problem/P4332 题目大意
给出nnn个点的一棵有根三叉树保证每个点的儿子个数为333或者000每个叶子有一个权值000或111每个非叶子节点的权值是它儿子中权值较多的那个每次修改一个叶子的权值求根节点的权值。
1≤n,q≤5×1051\leq n,q\leq 5\times 10^51≤n,q≤5×105 解题思路
修改一个节点会影响的权值显然是它到根节点路径上的一个前缀。
然后考虑什么样的节点会受到影响如果000改为111那么一路上原来恰好为两个000的节点就会被修改那么我们的思路是考虑找到这条路径上第一个111的个数不为111的节点。
而且考虑上修改的话十分的麻烦因为O(nlog2n)O(n\log^2 n)O(nlog2n)过不去所以不考虑树剖可以考虑一下LCTLCTLCT。
我们可以先联通修改点到根的节点然后在SplaySplaySplay上二分出第一个不为111的节点然后对于它和它的右子树暴力修改即可。
111改为000同理维护第一个不为222的节点即可。
时间复杂度O(nlogn)O(n\log n)O(nlogn) code
#includecstdio
#includecstring
#includealgorithm
#includevector
#includestack
using namespace std;
const int N2e610;
int n,m,ans,fa[N],v[N],w1[N],w2[N],lazy[N],t[N][2];
vectorint G[N];stackint s;
bool Nroot(int x)
{return fa[x](t[fa[x]][0]x||t[fa[x]][1]x);}
bool Direct(int x)
{return t[fa[x]][1]x;}
void PushUp(int x){if(w1[t[x][1]])w1[x]w1[t[x][1]];else if(v[x]!1)w1[x]x;else w1[x]w1[t[x][0]];if(w2[t[x][1]])w2[x]w2[t[x][1]];else if(v[x]!2)w2[x]x;else w2[x]w2[t[x][0]];return;
}
void PushR(int x,int w)
{v[x]^3;swap(w1[x],w2[x]);lazy[x]w;return;}
void PushDown(int x){if(!lazy[x])return;PushR(t[x][0],lazy[x]);PushR(t[x][1],lazy[x]);lazy[x]0;return;
}
void Rotate(int x){int yfa[x],zfa[y];int xsDirect(x),ysDirect(y);int wt[x][xs^1];if(Nroot(y))t[z][ys]x;t[x][xs^1]y;t[y][xs]w;if(w)fa[w]y;fa[y]x;fa[x]z;PushUp(y);PushUp(x);return;
}
void Splay(int x){int yx;s.push(x);while(Nroot(y))yfa[y],s.push(y);while(!s.empty())PushDown(s.top()),s.pop();while(Nroot(x)){yfa[x];if(!Nroot(y))Rotate(x);else if(Direct(x)Direct(y))Rotate(y),Rotate(x);else Rotate(x),Rotate(x);}return;
}
void Access(int x){for(int y0;x;yx,xfa[x])Splay(x),t[x][1]y,PushUp(x);return;
}
void Updata(int x){int op(v[x]^2);xfa[x];Access(x);Splay(x);if(op){if(w1[x]){xw1[x];Splay(x);PushR(t[x][1],1);PushUp(t[x][1]);v[x];PushUp(x);}else ans!ans,PushR(x,1),PushUp(x);}else{if(w2[x]){xw2[x];Splay(x);PushR(t[x][1],-1);PushUp(t[x][1]);v[x]--;PushUp(x);}else ans!ans,PushR(x,-1),PushUp(x);}return;
}
void dfs(int x){for(int i0;iG[x].size();i){int yG[x][i];dfs(y);v[x](v[y]1);}PushUp(x);return;
}
int main()
{scanf(%d,n);for(int i1;in;i){int x,y,z;scanf(%d%d%d,x,y,z);fa[x]fa[y]fa[z]i;G[i].push_back(x);G[i].push_back(y);G[i].push_back(z);}for(int in1;i3*n1;i)scanf(%d,v[i]),v[i]1;dfs(1);ansv[1]1;scanf(%d,m);while(m--){int x;scanf(%d,x);Updata(x);printf(%d\n,ans);}return 0;
}
