5
5
2016
1

跳表鬼畜用法 实验@Easy问题

[线段树]Easy问题(重庆2006省选)
时间:1 秒  内存:64 MB  

题目描述

有一个n个元素的数组,每个元素初始均为0。有m条指令,要么让其中一段连续序列数字反转--0变1,1变0(操作1),要么询问某个元素的值(操作2)。 例如当n=20时,10条指令如下:

操作  回答     操作后的数组

1 1 10 N/A   11111111110000000000

2 6   1    11111111110000000000

2 12  0     11111111110000000000

1 5 12 N/A   11110000001100000000

2 6   0    11110000001100000000

2 15  0     11110000001100000000

1 6 16 N/A   11110111110011110000

1 11 17 N/A   11110111111100001000

2 12   1    11110111111100001000

2 6   1       11110111111100001000

输入

输入第一行包含两个整数n,m,表示数组的长度和指令的条数。以下m行,每行的第一个数t表示操作的种类。若t=1,则接下来有两个数L,R(L<=R),表示区间[L,R]的每个数均反转;若t=2,则接下来只有一个数I,表示询问的下标。

输出

输出中有多行.每个操作2输出一行(非0即1),表示每个操作2的回答。

样例输入

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

其它信息

50%的数据满足:1<=n<=1000, 1<=m<=10000。
100%的数据满足:1<=n<=100000, 1<=m<=500000。

听@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论文 李骥扬《线段跳表——跳表的一个拓展》

Category: 程序 | Tags: 跳表 | Read Count: 280

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter

Host by is-Programmer.com | Power by Chito 1.3.3 beta | Theme: Aeros 2.0 by TheBuckmaker.com