Mars_Cat

20 10
1 1 10
2 6
2 12
1 5 12
2 6
2 15
1 6 16
1 11 17
2 12
2 6

1
0
0
0
1
1

听@Scarlet 跳表不能区间好好玩耍？

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>

using namespace std;

const int maxl=25;
const int INF=0x7fffffff;

struct node
{
	struct Info
	{
		node* n;
		bool v;
	}F[maxl+5];
	int n;
	int l;
};
typedef node* P;
struct list
{
	P s,t;
	int lev;
}skip;

int n,m,t,v;
int x,y,tmp,q;
P Pnt,xx;

inline void read(int &x)
{
	int f=1;char ch=getchar();
	for(;ch<'0'||ch>'9';ch=getchar())if(ch=='-')f=-1;
	for(x=0;ch>='0'&& ch<='9';ch=getchar())x=x*10+ch-'0';
	x*=f;
}
inline int Rand(){int x=1;while((rand()&1)&&(x<maxl))++x;return x;}
inline void swap(int &x,int &y){long long tt=x;x=y;y=tt;return;}
inline void FirstRun()
{
	skip.lev=1;
	skip.s=new node; skip.t=new node; skip.s->n=-INF; skip.t->n=INF;
	for(int i=1;i<=maxl+1;++i){skip.s->F[i].n=skip.t; skip.s->F[i].v=0;}
}
inline bool Find(int x)
{
	Pnt=skip.s;
	for(int i=skip.lev;i;--i)
	{
		while(Pnt->F[i].n->n < x)Pnt=Pnt->F[i].n;
		if(Pnt->F[i].n->n==x)
		{
			Pnt=Pnt->F[i].n;
			return true;
		}
	}
	return false;
}
inline void Push(int x)
{
	int levv=Rand();
	P now=skip.s;
	Pnt=new node;
	Pnt->n=x; Pnt->l=levv;
	for(int i=skip.lev;i;--i)
	{
		while(now->F[i].n->n < x)now=now->F[i].n;
		if(levv>=i)
		{
			Pnt->F[i].n=now->F[i].n;
			Pnt->F[i].v=now->F[i].v;
			now->F[i].n=Pnt;
		}
	}
	if(levv>skip.lev)
	{
		for(int i=skip.lev+1;i<=levv;++i)
		{
			skip.s->F[i].n=Pnt;
			Pnt->F[i].n=skip.t;
			Pnt->F[i].v=false;
		}
		skip.lev=levv;
	}
}
inline void Add(P x,int y)
{
	int l=x->l;
	for(;;)
	{
		while((x->l > l) && (x->F[l+1].n->n <= y))++l;
		while(x->F[l].n->n > y)--l;
		x->F[l].v ^= 1;
		x=x->F[l].n;
		if(x->n == y)return;
	}
}
inline void Ask(int x)
{
	P now=skip.s;
	bool ans=0;
	for(int i=skip.lev;i;--i)
	{
		while(now->F[i].n->n <= x)now=now->F[i].n;
		ans^=now->F[i].v;
	}
	printf("%d\n",ans);
}
int main()
{
	FirstRun();
	srand(time(NULL)); tmp=0;
	read(n);read(m);
	while(m--)
	{
		read(q);
		if(q==1)
		{
			read(x); read(y); y+=1;
			if(!Find(x))Push(x); xx=Pnt; if(!Find(y))Push(y);
			Add(xx,y);
		}
		else
		{
			read(x);
			Ask(x);
		}
	}
	return 0;
}

恩。确实可以用跳表螺杆的。虽然速度略慢。但他似乎在数据较大的时候显得更厉害。。
同时为这个算法感到悲哀。两次进入国家集训队论文却无人使用。QAQ

参考资料：
  国家集训队2005论文 魏冉《让算法的效率“跳起来”！——浅谈“跳跃表”的相关操作及其应用》
  国家集训队2009论文 李骥扬《线段跳表——跳表的一个拓展》