如何建一个公司网站,网站模板是怎么制作,自己的网站怎么编辑,泰安房产查询系统正题
题目链接:https://www.luogu.com.cn/problem/CF1137F 题目大意
给出nnn个点的一棵树#xff0c;第iii个点权值为iii。
一棵树的删除序列定义为每次删除编号最小的叶子并将其加入序列末尾。
要求支持
修改一个点的权值为一个比目前所有权值都要大的一个值询问一个点在…正题
题目链接:https://www.luogu.com.cn/problem/CF1137F 题目大意
给出nnn个点的一棵树第iii个点权值为iii。
一棵树的删除序列定义为每次删除编号最小的叶子并将其加入序列末尾。
要求支持
修改一个点的权值为一个比目前所有权值都要大的一个值询问一个点在删除序列的位置询问两个点在删除序列的先后顺序
1≤n,q≤2×1051\leq n,q\leq 2\times 10^51≤n,q≤2×105 解题思路
假设我们已经确定的先后顺序目前最大的权值为yyy号点然后修改一个点xxx时相当于把y∼xy\sim xy∼x的路径上所有点依次放在序列末尾。
相当于我们要支持提出一条树链可以考虑用LCTLCTLCT实现。
以权值最大的点为根我们对于每一条树链splay附上同一个颜色那么一个点的答案就是颜色编号比它小的点数所在树链上深度比它小的点数1。
然后修改就相当于连接换根换颜色。颜色方面可以用树状数组维护前缀和然后再AccessAccessAccess的时候进行修改换根也是可以用LCTLCTLCT做到的。
时间复杂度O(nlog2n)O(n\log^2 n)O(nlog2n) code
#includecstdio
#includecstring
#includealgorithm
#includestack
#define lowbit(x) (x-x)
using namespace std;
const int N2e510;
struct node{int to,next;
}a[N1];
int n,q,cnt,tot,ls[N],col[N];
struct BinaryInTree{int t[N1],n;void Change(int x,int val){while(xn){t[x]val;xlowbit(x);}return;}int Ask(int x){int ans0;while(x){anst[x];x-lowbit(x);}return ans;}
}B;
struct LCT{int fa[N],t[N][2],siz[N];bool r[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){siz[x]siz[t[x][0]]siz[t[x][1]]1;return;}void Rev(int x){r[x]^1;swap(t[x][0],t[x][1]);return;}void PushDown(int x){if(t[x][0])col[t[x][0]]col[x];if(t[x][1])col[t[x][1]]col[x];if(!r[x])return;Rev(t[x][0]);Rev(t[x][1]);r[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[y][xs]w;t[x][xs^1]y;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)){int 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]0;PushUp(x);B.Change(col[x],-siz[x]);B.Change(cnt,siz[x]);t[x][1]y;PushUp(x);}return;}void MakeRoot(int x){cnt;Access(x);Splay(x);col[x]cnt;Rev(x);return;}int Ask(int x){Splay(x);return siz[t[x][1]]1B.Ask(col[x]-1);}
}T;
void addl(int x,int y){a[tot].toy;a[tot].nextls[x];ls[x]tot;return;
}
void dfs(int x){col[x]x;for(int ils[x];i;ia[i].next){int ya[i].to;if(yT.fa[x])continue;T.fa[y]x;dfs(y);if(col[y]col[x]){col[x]col[y];T.t[x][1]y;}}B.Change(col[x],1);T.PushUp(x);
}
int main()
{scanf(%d%d,n,q);for(int i1;in;i){int x,y;scanf(%d%d,x,y);addl(x,y);addl(y,x);}B.nnq;cntn;dfs(n);for(int i1;iq;i){char op[6];int x,y;scanf(%s%d,op,x);if(op[0]u)T.MakeRoot(x);else if(op[0]w)printf(%d\n,T.Ask(x));else if(op[0]c){scanf(%d,y);int lT.Ask(x),rT.Ask(y);if(lr)printf(%d\n,x);else printf(%d\n,y);}}return 0;
}
