Description：

Solution：

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include "rts.h"

#include<cctype>

#include<cstring>

using namespace std;

int n;

int lim;

#define MAXN 300010

struct node

{

  int c[2],fa;

  int ls,rs;

}t[MAXN];

bool isroot(int k){return (t[t[k].fa].c[0] != k && t[t[k].fa].c[1] != k);}

void connect(int k,int f,int p){t[k].fa = f;t[f].c[p] = k;return;}

int id(int k){return (t[t[k].fa].c[0] == k ? 0 : 1);}

void maintain(int rt)

{

  if(t[rt].c[0])t[rt].ls = t[t[rt].c[0]].ls;

  else t[rt].ls = rt;

  if(t[rt].c[1])t[rt].rs = t[t[rt].c[1]].rs;

  else t[rt].rs = rt;

  return;

}

void rotate(int x)

{

  int y = t[x].fa,z = t[y].fa,fx = id(x),fy = id(y);

  if(!isroot(y))t[z].c[fy] = x;

  t[x].fa = z;

  connect(t[x].c[fx ^ 1],y,fx);

  connect(y,x,fx ^ 1);

  maintain(y);maintain(x);

  return;

}

void splay(int x)

{

  while(!isroot(x))

  {

    int y = t[x].fa;

    if(isroot(y)){rotate(x);break;}

    if(id(x) == id(y)){rotate(y);rotate(x);}

    else{rotate(x);rotate(x);}

  }

  return;

}

void access(int k){for(int i = 0;k;i = k,k = t[k].fa){splay(k);t[k].c[1] = i;maintain(k);}return;}

bool valid[MAXN];

void calc(int k)

{

  int cur = 1;splay(1);

  while(true)

  {

    int v = explore(cur,k);

    if(v == t[t[cur].c[1]].ls)cur = t[cur].c[1];

    else if(v == t[t[cur].c[0]].rs)cur = t[cur].c[0];

    else

    {

      if(valid[v])

      {

	splay(cur);

	cur = v;

	splay(v);

      }

      else

      {

	t[v].fa = cur;

	cur = v;

	valid[v] = true;

	if(v == k)break;

      }

    }

  }

  valid[k] = true;

  access(k);

  return;

}

int v[MAXN];

void play(int N,int T,int datatype)

{

  n = N;lim = T;

  srand(12345678);

  valid[1] = true;

  for(int i = 2;i <= n;++i)v[++v[0]] = i;

  random_shuffle(v + 1,v + 1 + v[0]);

  if(datatype == 3)

  {

    int lef = 1,rig = 1;

    int cur = 0;

    for(int i = 1;i <= v[0];++i)

    {

      int k = v[i];

      if(valid[k])continue;

      while(true)

      {

	if(cur == 0)

	{

	  int x = explore(lef,k);

	  if(valid[x])

	  {

	    x = explore(rig,k);

	    valid[x] = true;

	    rig = x;

	    cur ^= 1;

	  }

	  else

	  {

	    valid[x] = true;

	    lef = x;

	  }

	  if(x == k)break;

	}

	else

	{

	  int x = explore(rig,k);

	  if(valid[x])

	  {

	    x = explore(lef,k);

	    valid[x] = true;

	    lef = x;

	    cur ^= 1;

	  }

	  else

	  {

	    valid[x] = true;

	    rig = x;

	  }

	  if(x == k)break;

	}

      }

    }

  }

  else

  {

    t[1].ls = t[1].rs = 1;

    for(int i = 1;i <= v[0];++i)if(!valid[v[i]])calc(v[i]);

  }

  return;

}