loj2341「WC2018」即时战略(随机化，LCT/动态点分治)

loj

Luogu

题解时间

对于 $ datatype = 3 $ 的数据，explore操作次数只有 $ n+log n $ 。

毫无疑问无论什么时候已经探索的区域都是一条链。

每当要探索出一个新点，不是在左侧就是在右侧。

最劣情况下调用次数为 $ 2n $ 。

只要随机打乱探索顺序，额外浪费的次数类似于上升子序列长度，期望 $ logn $ ，可以解决。

而对于其余数据，依然随机打乱探索顺序，

每次对于目标点，要点在于找到距离该点最近的已知点。

可以用动态点分治严格 $ nlogn $ 或LCT均摊 $ nlogn $ 。

#include<bits/stdc++.h>
// #include"rts.h"
int explore(int,int);
using namespace std;
typedef long long lint;
const int N=300011;
int n;
bool vis[N];int lst[N];
namespace task1
{
int fa[N],son[N][2];
int isroot(int x){return son[fa[x]][0]!=x&&son[fa[x]][1]!=x;}
void rot(int x)
{
	int y=fa[x],z=fa[y],xis=son[y][1]==x,yis=son[z][1]==y;
	if(!isroot(y)) son[z][yis]=x;
	fa[x]=z,fa[y]=x,fa[son[x][xis^1]]=y;
	son[y][xis]=son[x][xis^1],son[x][xis^1]=y;
}
void splay(int x)
{
	while(!isroot(x))
	{
		int y=fa[x],z=fa[y],xis=son[y][1]==x,yis=son[z][1]==y;
		if(!isroot(y)) rot(xis^yis?x:y);rot(x);
	}
}
void access(int x){for(int lst=0;x;lst=x,x=fa[x]) splay(x),son[x][1]=lst;}
int anc(int x){while(!isroot(x)) x=fa[x];return x;}
int pre(int x){x=son[x][0];while(son[x][1]) x=son[x][1];return x;}
int nxt(int x){x=son[x][1];while(son[x][0]) x=son[x][0];return x;}
void find(int ep)
{
	int x=anc(1);
	while(x!=ep)
	{
		int y=explore(x,ep);if(!vis[y]) vis[y]=1,fa[y]=x,x=y;
		else if(y==pre(x)) x=son[x][0];
		else if(y==nxt(x)) x=son[x][1];
		else x=anc(y);
	}access(x);
}
void play(){for(int i=2;i<=n;i++)if(!vis[lst[i]]) find(lst[i]);}
}
namespace task2
{
void access(int &x,int ep){while(x!=ep) vis[x=explore(x,ep)]=1;}
void play()
{
	for(int i=2,l=1,r=1,x=0;i<=n;i++)if(!vis[lst[i]])
		access(vis[x=explore(r,lst[i])]?l:(vis[x]=1,r=x),lst[i]);
}
}
void play(int n,int lim,int type)
{
	::n=n;srand(time(NULL));vis[1]=1;
	for(int i=2;i<=n;i++) lst[i]=i;random_shuffle(lst+2,lst+1+n);
	if(type!=3) task1::play();else task2::play();
}