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

题解时间

对于 $ 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();

}

巴特西

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

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

题解时间

最新文章

热门文章