题目大意

Windows的同学建议看LOJ的题面

Solution

LCT

Tips：由于第9到第13个点（一条链）过于毒瘤，比一棵树的限制紧很多，所以一条链的要分开来写（暂时未写）。

UPD：然后特判一条链的情况，只要记录下已知链的左右端点。直接随机找到一个未知点，把这个到已知点的端点的那条未知链都标记为已知。询问次数复杂度为$O(n+\ln n)$，只有$\frac{144}{10000}$的错误率。

Code

#include "rts.h"
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cstdlib>
using namespace std;
int son,Next,pre,L,R,fa,a,flag,ans;
int isroot(int x)
{
int xx=fa[x];
return (son[xx]!=x&&son[xx]!=x);
}
void update(int x)
{
Next[x]=L[son[x]],pre[x]=R[son[x]];
if (son[x]) L[x]=L[son[x]];
else L[x]=x;
if (son[x]) R[x]=R[son[x]];
else R[x]=x;
}
void rotate(int x)
{
int y=fa[x],z=fa[y];
int l=(son[y]==x),r=l^1;
if (!isroot(y))
son[z][(son[z]==y)]=x;
fa[x]=z,fa[y]=x,fa[son[x][r]]=y;
son[y][l]=son[x][r],son[x][r]=y;
update(y);
update(x);
}
void splay(int x)
{
while (!isroot(x))
{
int y=fa[x];
if (!isroot(y))
{
int z=fa[y];
if ((son[y]==x)^(son[z]==y)) rotate(x);
else rotate(y);
}
rotate(x);
}
}
void access(int u)
{
for (int x=u,t=0;x;t=x,x=fa[x])
{
splay(x);
son[x]=t;
update(x);
}
}
int bs(int u,int po)
{
int xx=explore(u,po);
if (xx==Next[u]) return bs(son[u],po);
if (xx==pre[u]) return bs(son[u],po);
ans=u;
return xx;
}
int find(int u,int po)
{
while (!isroot(u)) u=fa[u];
int xx=bs(u,po);
if (!flag[xx])
{
flag[xx]=1;
fa[xx]=ans;
return xx;
}
return find(xx,po);
}
void play(int n, int T, int dataType)
{
srand(19260817);
for (int i=2;i<=n;i++) a[i-1]=i;
for (int i=1;i<=n;i++) L[i]=R[i]=i;
for (int i=1;i<=n*2;i++)
{
int u=rand()%(n-1)+1,v=rand()%(n-1)+1;
swap(a[u],a[v]);
}
memset(flag,0,sizeof(flag));
flag=1;
if (dataType==3)
{
int L=1,R=1;
for (int i=1;i<n;)
{
if (flag[a[i]])
{
i++;
continue;
}
int x=rand()%2;
if (!x)
{
int xx=explore(L,a[i]);
if (!flag[xx])
{
flag[xx]=1,L=xx;
while (xx!=a[i]) xx=explore(L,a[i]),flag[xx]=1,L=xx;
}
else
{
xx=explore(R,a[i]);
flag[xx]=1,R=xx;
while (xx!=a[i]) xx=explore(R,a[i]),flag[xx]=1,R=xx;
}
}
else
{
int xx=explore(R,a[i]);
if (!flag[xx])
{
flag[xx]=1,R=xx;
while (xx!=a[i]) xx=explore(R,a[i]),flag[xx]=1,R=xx;
}
else
{
xx=explore(L,a[i]);
flag[xx]=1,L=xx;
while (xx!=a[i]) xx=explore(L,a[i]),flag[xx]=1,L=xx;
}
}
}
return;
}
flag=1;
ans=1;int x=1;
for (int i=1;i<n;)
{
if (flag[a[i]])
{
x=1;
i++;
continue;
}
x=find(x,a[i]);
access(x);
}
}

4条评论

1. My husband and i were so happy when Raymond managed to deal with his investigations using the precious recommendations he discovered out of the web pages. It is now and again perplexing to just be giving for free instructions some other people could have been making money from. Therefore we fully grasp we need the writer to be grateful to because of that. Those illustrations you’ve made, the straightforward site menu, the relationships your site make it possible to instill – it’s got many sensational, and it is helping our son in addition to us feel that this idea is thrilling, and that is tremendously mandatory. Thanks for all!

2. 2楼

I precisely needed to thank you so much all over again. I’m not certain the things I would’ve gone through in the absence of the entire creative concepts discussed by you concerning that area of interest. It previously was a frightful matter for me, but understanding the very specialised strategy you resolved that took me to weep over contentment. I am just grateful for your information and trust you realize what a powerful job you were putting in training other individuals through the use of your web blog. Probably you have never met any of us.

3. I want to show my thanks to this writer just for rescuing me from this particular situation. As a result of checking throughout the search engines and obtaining advice which were not beneficial, I was thinking my entire life was well over. Being alive without the solutions to the issues you’ve sorted out by means of the report is a critical case, and the kind that would have in a wrong way affected my entire career if I hadn’t discovered the website. Your good knowledge and kindness in taking care of all areas was excellent. I am not sure what I would’ve done if I had not discovered such a point like this. I can at this time relish my future. Thanks a lot very much for the reliable and result oriented help. I won’t be reluctant to recommend the blog to anybody who should have guidance about this situation.

4. Thank you a lot for providing individuals with an exceptionally superb possiblity to read critical reviews from this website. It is always very enjoyable and full of a lot of fun for me and my office colleagues to search the blog the equivalent of three times per week to learn the fresh stuff you have got. And of course, I’m so always astounded for the terrific tips and hints you serve. Selected two points in this article are in truth the most effective I have had.