Description

Solution

链的情况是 \(O(n+log)\) 的,要分开讨论

由于链的情况已知的点一定是一段连续的,维护两个端点不断往两边扩展即可

树的情况是 \(O(n*log)\) 的

要支持快速查找到一个点所在的位置,我们可以用点分治做一下,找到这个点属于哪一个儿子所在的块,递归找下去就可以了

由于需要存一个儿子所在的块,需要用到 \(map\) ,复杂度是 \(O(n*log^2)\) 的,并且要定期重构.

另一种是用 \(LCT\) , \(access\) 均摊复杂度的做法

两种做法操作次数是 \(O(n*log)\) 的

#include "rts.h"#include
    
     using namespace std;const int N=300010;int id[N],ch[N][2],fa[N],L[N],R[N];bool vis[N];inline bool isrt(int x){return ch[fa[x]][0]!=x&&ch[fa[x]][1]!=x;}inline void upd(int x){    L[x]=R[x]=x;    if(ch[x][0])L[x]=L[ch[x][0]];    if(ch[x][1])R[x]=R[ch[x][1]];}inline void rotate(int x){    int y=fa[x];bool t=ch[y][1]==x;    ch[y][t]=ch[x][!t];fa[ch[y][t]]=y;    ch[x][!t]=y;fa[x]=fa[y];    if(!isrt(y))ch[fa[y]][ch[fa[y]][1]==y]=x;    fa[y]=x;upd(y);upd(x);}inline void splay(int x){    while(!isrt(x)){        int y=fa[x],p=fa[y];        if(isrt(y))rotate(x);        else if((ch[p][0]==y)==(ch[y][0]==x))rotate(y),rotate(x);        else rotate(x),rotate(x);    }}inline void access(int x){    int y=0;    while(x)splay(x),ch[x][1]=y,upd(x),x=fa[y=x];}inline int getroot(int x){while(!isrt(x))x=fa[x];return x;}inline void ins(int x){    int s=getroot(1),t;    while(!vis[x]){        t=explore(s,x);        if(t==L[ch[s][1]])s=ch[s][1];        else if(t==R[ch[s][0]])s=ch[s][0];        else if(vis[t])s=getroot(t);        else fa[t]=s,vis[s=t]=1;    }    access(x);}void play(int n, int T, int dataType){    srand(time(NULL));    for(int i=2;i<=n;i++)id[i]=i;    for(int i=1;i<=5;i++)random_shuffle(id+2,id+n+1);    if(dataType==3){        int l=1,r=explore(1,id[2]);        vis[r]=1;        for(int i=2;i<=n;i++){            int x=id[i];            if(vis[x])continue;            int t=explore(l,x);            if(vis[t]){while(r!=x)vis[r=explore(r,x)]=1;}            else{                vis[t]=1;                while(l!=x)vis[l=explore(l,x)]=1;            }        }        return ;    }    for(int i=1;i<=n;i++)L[i]=R[i]=i;    for(int i=2;i<=n;i++)if(!vis[id[i]])ins(id[i]);}