「ZJOI2016」大森林
神仙题...
很显然线段树搞不了
考虑离线操作
我们只搞一颗树，从位置1一直往后移动，然后维护它的形态试试
显然操作0,1都可以拆成差分的形式，就是加入和删除
因为保证了操作2的合法性，我们不妨先不计合法性把所有点加到树中
显然每个点要连到在这个点之前的离这个点时间上最近那个1操作的点上
然后可以发现移动时1操作相当于很多个点换根
我们可以对每个1操作建一个虚点，然后就可以很方便换根了
那么如何保证查询操作呢？
可以把每个1操作的虚点大小设成0(代表它父亲边的直接长度)，并按时间串起来。
这样，一个虚点的虚点儿子的子树的点其实也是它的子树了，查询的时候差dis[u]+dis[v]-dis[lca]*2就可以了
是不是以为这个0操作的区间限制就没有用了？
其实不是，注意到1操作的点可能还没出现...这时候就要把1操作删掉
Code:
#include <cstdio>
#include <cctype>
#include <algorithm>
using std::min;
using std::max;
const int N=3e5+10;
template <class T>
void read(T &x)
{
x=0;char c=getchar();
while(!isdigit(c)) c=getchar();
while(isdigit(c)) x=x*10+c-'0',c=getchar();
}
int ans[N],n,m,_n,_m,q,p[N],node,ti[N],tot,L[N],R[N];
struct koito_yuu
{
int pos,op,u,v;
koito_yuu(){}
koito_yuu(int Pos,int Op,int U,int V){pos=Pos,op=Op,u=U,v=V;}
bool friend operator <(koito_yuu a,koito_yuu b){return a.pos==b.pos?a.op<b.op:a.pos<b.pos;}
}yuu[N];
#define ls ch[now][0]
#define rs ch[now][1]
#define fa par[now]
int sum[N],ch[N][2],par[N],siz[N];
bool isroot(int now){return ch[fa][0]==now||ch[fa][1]==now;}
int identity(int now){return ch[fa][1]==now;}
void connect(int f,int now,int typ){ch[fa=f][typ]=now;}
void updata(int now){sum[now]=sum[ls]+sum[rs]+siz[now];}
void Rotate(int now)
{
int p=fa,typ=identity(now);
connect(p,ch[now][typ^1],typ);
if(isroot(p)) connect(par[p],now,identity(p));
else fa=par[p];
connect(now,p,typ^1);
updata(p),updata(now);
}
void splay(int now)
{
for(;isroot(now);Rotate(now))
if(isroot(fa))
Rotate(identity(now)^identity(fa)?now:fa);
}
int access(int now)
{
int las=0;
for(;now;las=now,now=fa) splay(now),rs=las,updata(now);
return las;
}
int LCA(int x,int y)
{
access(x);
return access(y);
}
void link(int x,int y)
{
access(x),splay(x);
par[x]=y;
}
void cat(int x)
{
access(x),splay(x);
par[ch[x][0]]=0;
ch[x][0]=0;
}
int qry(int x)
{
access(x),splay(x);
return sum[x];
}
int query(int x,int y)
{
int lca=LCA(x,y);
return qry(x)+qry(y)-(qry(lca)<<1);
}
int main()
{
read(n),read(m);
L[1]=1,R[1]=n,node=1,++tot;
for(int op,l,r,x,u,v,i=1;i<=m;i++)
{
read(op);
if(op==0) ++node,read(L[node]),read(R[node]),p[node]=i;
else if(op==1)
{
ti[++tot]=i;
link(tot,tot-1);
read(l),read(r),read(x);
l=max(L[x],l),r=min(R[x],r);
if(l>r) continue;
yuu[++q]=koito_yuu(l,-1,x,tot);
yuu[++q]=koito_yuu(r+1,0,x,tot);
}
else
{
read(x),read(u),read(v);
yuu[++q]=koito_yuu(x,++_n,u,v);
}
}
_m=tot;
for(int i=2;i<=node;i++)
{
int pos=std::upper_bound(ti+1,ti+1+_m,p[i])-ti-1;
siz[++tot]=1,sum[tot]=1;
link(tot,pos);
}
std::sort(yuu+1,yuu+1+q);
for(int j=1,i=1;i<=n;i++)
{
while(yuu[j].pos==i)
{
int u=yuu[j].u+_m-1,v=yuu[j].v;
if(u==_m) u=1;
if(yuu[j].op==-1)
{
cat(v);
link(v,u);
}
else if(yuu[j].op==0)
{
cat(v);
link(v,v-1);
}
else ans[yuu[j].op]=query(u,v==1?1:v+_m-1);
++j;
}
}
for(int i=1;i<=_n;i++) printf("%d\n",ans[i]);
return 0;
}
2019.3.11