UOJ#349. 【WC2018】即时战略

原文链接https://www.cnblogs.com/zhouzhendong/p/UOJ349.html

题解

被cqz D没了。我D cly 关你啥事（逃

首先链的情况直接rand就好了。

期望次数 $O(n+\log n)$ 。

然而我一开始写挂了。

---

开始扯淡

我用这个模数，就可以过原题数据：

('C'+'L'+'Y'+'A'+'K'+'I'+'O'+'I')

但是用以下两种都不行：

('G'+'L'+'Y'+'A'+'K'+'I'+'O'+'I')

('C'+'L'+'Y'+'A'+'K'+'I'+'O'+'I'+'N'+'O'+'I')

第一个说明叫cly外号会掉rp，因为他是大佬。

第二个说明cly是大佬不屑于AKNOI。

---

对于树的情况，容易想到的是一个和紫荆花之恋一样的替罪羊树维护点分树的做法。

但是显然GG了。

考虑我们将一个节点连到主体部分这个操作，类似于 LCT 中的 access 。于是我们发现直接写个 LCT 就没了。

写法有多种，但是考虑到常数因子，建议连接完之后一遍access上去。不要自顶向下一边access一边splay一边连边，这样常数大。

代码

#pragma GCC optimize("Ofast","inline")

#include <bits/stdc++.h>

#include "rts.h"

#define clr(x) memset(x,0,sizeof (x))

#define For(i,a,b) for (int i=a;i<=b;i++)

#define Fod(i,b,a) for (int i=b;i>=a;i--)

#define pb push_back

#define mp make_pair

#define fi first

#define se second

#define _SEED_ ('C'+'L'+'Y'+'A'+'K'+'I'+'O'+'I')

#define outval(x) printf(#x" = %d\n",x)

#define outvec(x) printf("vec "#x" = ");for (auto _v : x)printf("%d ",_v);puts("")

#define outtag(x) puts("----------"#x"----------")

#define outarr(a,L,R) printf(#a"[%d...%d] = ",L,R);\

						For(_v2,L,R)printf("%d ",a[_v2]);puts("");

using namespace std;

typedef long long LL;

const int N=300005;

#define Ask explore

namespace so0{

	int L=1,R=1,rv=0;

	int vis[N];

	vector <int> v;

	void main(int n){

		v.clear();

		For(i,2,n)

			v.pb(i);

		random_shuffle(v.begin(),v.end());

		while (!v.empty()){

			int x=v.back();

			v.pop_back();

			if (vis[x])

				continue;

			int y=Ask(L,x);

			if (y==rv){

				while (R!=x)

					R=Ask(R,x),vis[R]=1;

			}

			else {

				rv=L,L=y,vis[L]=1;

				while (L!=x)

					rv=L,L=Ask(L,x),vis[L]=1;

			}

		}

	}

}

namespace so1{

	int n;

	int vis[N];

	int father[N],hson[N];

	int son[N][2],fa[N];

	vector <int> v;

	#define ls son[x][0]

	#define rs son[x][1]

	bool isroot(int x){

		return son[fa[x]][0]!=x&&son[fa[x]][1]!=x;

	}

	int wson(int x){

		return son[fa[x]][1]==x;

	}

	void rotate(int x){

		int y=fa[x],z=fa[y],L=wson(x),R=L^1;

		if (!isroot(y))

			son[z][wson(y)]=x;

		fa[x]=z,fa[y]=x,fa[son[x][R]]=y;

		son[y][L]=son[x][R],son[x][R]=y;

	}

	void splay(int x){

		for (int y=fa[x];!isroot(x);rotate(x),y=fa[x])

			if (!isroot(y))

				rotate(wson(x)==wson(y)?y:x);

	}

	void access(int x){

		int t=0;

		while (x){

			splay(x);

			hson[x]=t;

			while (son[hson[x]][0])

				hson[x]=son[hson[x]][0];

			rs=t,t=x,x=fa[x];

		}

	}

	void Ins(int a){

		int x=1,y;

		while (fa[x])

			x=fa[x];

		while (x!=a){

			y=Ask(x,a);

			if (!vis[y])

				break;

			if (y==father[x])

				x=ls;

			else if (y==hson[x])

				x=rs;

			else {

				while (!isroot(y))

					y=fa[y];

				x=y;

			}

		}

		while (1){

			fa[y]=father[y]=x;

			vis[y]=1;

			x=y;

			if (x==a)

				break;

			y=Ask(x,a);

		}

		access(x);

	}

	#undef ls

	#undef rs

	void main(int n){

		so1::n=n;

		v.clear();

		vis[1]=1;

		For(i,2,n)

			v.pb(i);

		random_shuffle(v.begin(),v.end());

		clr(father),clr(hson);

		while (!v.empty()){

			int x=v.back();

			v.pop_back();

			if (!vis[x])

				Ins(x);

		}

	}

}

void play(int n,int T,int type){

	srand(_SEED_);

	if (type==3)

		so0::main(n);

	else

		so1::main(n);

}