5
5
2016
3

跳表鬼畜用法 实验@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: 812
Avatar_small
Indianbanknetbanking 说:
2022年8月07日 15:52

Indian Bank has more than 100 million customers spread all across the world and widely situated mostly throughout India which makes it among few of top banks in our nation. It also has nearly 20,000+ offline branches across Indian which makes their customer service and their facilities much performing that brings the value to the present and the new customers who open their accounts with the bank. Indianbanknetbanking I can see that there are many people who find themselves questioning how can I register for Indian bank net banking, and this becomes necessary at one point who do not yet do online banking, because it has become quite necessary with the world advancing with the tech.

Avatar_small
NCERT Biology Sample 说:
2022年9月29日 14:23

Biology is the study of the life of flora and fauna. Biology talks about organisms and how they react to certain toxins when you mix things up. Biology has a long history which showed impacted people in negative and positive ways. Biology is the study of the life of flora and fauna. NCERT Biology Sample Paper Class 9 Biology talks about organisms and how they react to certain toxins when you mix things up. Biology has a long history which showed impacted people in negative and positive ways.Biology is one of the interesting studies with practical experiments which helps the students in understanding better way.


登录 *


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