虚拟网站建设步骤,东营网站排名,青岛网络推广选哪家,旅游网站 源码 织梦正题
题目链接:https://www.luogu.com.cn/problem/P3348 题目大意
有nnn棵树开始只有一个编号为111的节点且为标记点。mmm次操作要求支持
在l∼rl\sim rl∼r的树中的标记点下面加入一个新的编号的节点将l∼rl\sim rl∼r的树上的标记点改为xxx#xff08;如果没有节点xxx就不…正题
题目链接:https://www.luogu.com.cn/problem/P3348 题目大意
有nnn棵树开始只有一个编号为111的节点且为标记点。mmm次操作要求支持
在l∼rl\sim rl∼r的树中的标记点下面加入一个新的编号的节点将l∼rl\sim rl∼r的树上的标记点改为xxx如果没有节点xxx就不操作询问第xxx棵树上uuu点到vvv点的距离
1≤n≤105,1≤m≤2×1051\leq n\leq 10^5,1\leq m\leq 2\times 10^51≤n≤105,1≤m≤2×105 保证询问合法 解题思路
保证询问合法的话我们其实第一个操作理解为对所有树都操作就可以了。主要是第二个操作在线区间LCTLCTLCT看起来就很不可做所以考虑离线。
对于一个操作1lrx1\ l\ r\ x1 l r x它会对l−1l-1l−1和lll的树造成的影响是再往后直到下一个111操作之间所有的节点都会被接到不同的点下面。但是显然暴力改接是不行的我们可以考虑对于两个111操作之间的000操作建立一个虚点下面链接的所有这个区间新建的点然后每次就改接一个虚点就好了。
然后需要注意的一些细节因为根是固定的不能用splitsplitsplit会破坏父子关系好像在makeroot(1)makeroot(1)makeroot(1)回去可以但是据说很慢所以要差分求到根节点的路径长度。还要求lcalcalcaLCTLCTLCT上求lcalcalca的话就accessaccessaccess了xxx再到yyy最后SplaySplaySplay的那个yyy就是lcalcalca了。
还有因为如果没有节点xxx就不操作所以我们需要记录一下每个点拥有的树的区间然后取一个交集就好了。
时间复杂度O(nlogn)O(n\log n)O(nlogn) code
#includecstdio
#includecstring
#includealgorithm
using namespace std;
const int N2e510;
struct node{int x,l,r,id;
}q[N],c[N];
int n,m,num,cnt,ct,qt;
int L[N],R[N],ans[N],at[N];
struct LCT{int fa[N],t[N][2],siz[N],v[N];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]]v[x];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){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;}int Access(int x){int y0,pxx;for(;x;yx,xfa[x])Splay(x),t[x][1]y,PushUp(x);Splay(px);return y;}void Link(int x,int y){Splay(x);fa[x]y;return;}void Cut(int x){Access(x);fa[t[x][0]]0;t[x][0]0;PushUp(x);return;}
}T;
bool cmp(node x,node y)
{return x.xy.x;}
int main()
{scanf(%d%d,n,m);L[1]cntat[1]1;R[1]n;T.Link(2,1);cnt2;int last2,num1,aux2;for(int i1;im;i){int op,l,r,x;scanf(%d%d%d,op,l,r);if(op0){num;at[num]cnt;T.v[cnt]T.siz[cnt]1;T.Link(cnt,aux);L[num]l;R[num]r;}else if(op1){scanf(%d,x);lmax(l,L[x]);rmin(r,R[x]);if(lr)continue;cnt;T.Link(cnt,aux);c[ct](node){l,cnt,at[x]};c[ct](node){r1,cnt,aux,0};auxcnt;}else{scanf(%d,x);q[qt](node){l,at[r],at[x],qt};}}sort(q1,q1qt,cmp);sort(c1,c1ct,cmp);for(int i1,z1;iqt;i){int sum0;while(zctc[z].xq[i].x)T.Cut(c[z].l),T.Link(c[z].l,c[z].r),z;T.Access(q[i].l);sumT.siz[q[i].l];int lcaT.Access(q[i].r);sumT.siz[q[i].r];T.Access(lca);sum-2*T.siz[lca];ans[q[i].id]sum;}for(int i1;iqt;i)printf(%d\n,ans[i]);return 0;
}
