splay BZOJ1500 NOI2005 維護數列

傳說中的splay神題，其實個人感覺還行，算是上個時代的資料結構神題吧，現在都流行各種分治，各種神轉化+樸素線段樹，或者動态XXX函數式XXX

做法個人感覺已經說爛了，論文中說的很細

每個節點維護size，father，child【2】（兩個孩子）

标記要維護的是same,SameVal,res,MaxL,MaxR,MaxM,sum

分别是是否修改為一樣的值，修改的值，是否翻轉，這個區間從左邊開始的最大連續值，從右邊開始的最大值，整個區間的最長子序列，還有這個序列的和

然後就是維護了

注意down（向下傳标記）的時候先傳same再傳res

如果有same的話就不用傳res了，這個不難了解吧

剩下的個人感覺沒什麼說的必要了

都是splay維護區間問題的經典問題

如果沒寫過splay維護區間問題的話

想入門看這裡

哦對有個小插曲，個人的代碼在bzoj挂了。。。原因不知道。。。

但是代碼在BSOJ上AC了，時間是3s多一點

我自己問bzoj管理者要的資料本地的測試中也過了

個人感覺代碼應該沒問題

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#define MAX 2850003
#define rep(x,y,z) for(int x=y;x<=z;x++)
#define inf 0x7fffffff/4

using namespace std;

int pos,total,tot=0,root;
int size[MAX],child[2][MAX],res[MAX];
int same[MAX],value[MAX],a[MAX],b[MAX],sum[MAX];
int MaxL[MAX],MaxR[MAX],MaxM[MAX],father[MAX],SameVal[MAX];

void down(int x)
{
	if(!x)
		return;
	if(same[x])
	{
		same[x]=res[x]=0;

		value[x]=SameVal[x];
		sum[x]=SameVal[x]*size[x];

		if(value[x]<0)
			MaxL[x]=MaxR[x]=MaxM[x]=value[x];
		else
			MaxL[x]=MaxR[x]=MaxM[x]=sum[x];

		same[child[0][x]]=same[child[1][x]]=1;
		SameVal[child[0][x]]=SameVal[child[1][x]]=SameVal[x];
	}
	if(res[x])
	{
		/*if(child[0][x])
			res[child[0][x]]^=1;
		if(child[1][x])
			res[child[1][x]]^=1;
		swap(MaxL[child[0][x]],MaxR[child[1][x]]);
		swap(child[0][x],child[1][x]);
		res[x]=0;*/
		res[x]=0;
		swap(child[0][x],child[1][x]);
		swap(MaxL[x],MaxR[x]);

		res[child[0][x]]=!res[child[0][x]];
		res[child[1][x]]=!res[child[1][x]];
	}
}

void up(int x)
{
	if(!x)
		return;
	down(child[0][x]);
	down(child[1][x]);

	size[x]=1+size[child[0][x]]+size[child[1][x]];
	sum[x]=sum[child[0][x]]+value[x]+sum[child[1][x]];

	//l
	MaxL[x]=MaxL[child[0][x]];
	MaxL[x]=max(MaxL[x],max(sum[child[0][x]]+value[x],sum[child[0][x]]+value[x]+MaxL[child[1][x]]));

	//r
	MaxR[x]=MaxR[child[1][x]];
	MaxR[x]=max(MaxR[x],max(sum[child[1][x]]+value[x],sum[child[1][x]]+value[x]+MaxR[child[0][x]]));

	//m
	MaxM[x]=max(value[x],MaxR[child[0][x]]+value[x]+MaxL[child[1][x]]);
	MaxM[x]=max(MaxM[x],max(MaxM[child[0][x]],MaxM[child[1][x]]));
	MaxM[x]=max(MaxM[x],max(value[x]+MaxR[child[0][x]],value[x]+MaxL[child[1][x]]));
	MaxM[x]=max(MaxM[x],MaxL[child[1][x]]+value[x]+MaxR[child[0][x]]);
	return;
}

void build(int &x,int l,int r)
{
	if(l>r)
	{
		x=0;
		return;
	}
	x=++tot;
	int mid=(l+r)>>1;
	value[x]=sum[x]=a[mid];
	same[x]=0;
	res[x]=0;
	MaxL[x]=MaxR[x]=MaxM[x]=SameVal[x]=-inf;
	build(child[0][x],l,mid-1);
	build(child[1][x],mid+1,r);
	if(child[0][x])
		father[child[0][x]]=x;
	if(child[1][x])
		father[child[1][x]]=x;
	up(x);
	return ;
}

void Insert(int &x,int l,int r)
{
	if(l>r)
	{
		x=0;
		return;
	}
	int mid=(l+r)>>1;
	x=++tot;
	value[x]=sum[x]=b[mid];
	same[x]=res[x]=0;
	MaxL[x]=MaxR[x]=MaxM[x]=SameVal[x]=-inf;
	Insert(child[0][x],l,mid-1);
	Insert(child[1][x],mid+1,r);
	if(child[0][x])
		father[child[0][x]]=x;
	if(child[1][x])
		father[child[1][x]]=x;
	up(x);
}

int select(int k)
{
	int t=root;
	while(1)
	{
		down(t);
	//	printf("fuck\n");
		if(size[child[0][t]]+1==k)
			return t;
		if(size[child[0][t]]>=k)
			t=child[0][t];
		else
			k-=size[child[0][t]]+1,t=child[1][t];
	}
	return -1;
}

void rotate(int p)
{
	int q=father[p],y=father[q],x=(child[1][q]==p);
	down(q);
	down(p);
	down(child[0][p]),down(child[1][p]),down(child[x^1][p]);

	father[child[x][q]=child[x^1][p]]=q;
	father[child[x^1][p]=q]=p;
	father[p]=y;
	if(y)
		child[child[1][y]==q][y]=p;

	up(q);
	return;
}	

void splay(int x,int aim=0)
{
	down(x);
	for(int y;(y=father[x])!=aim;rotate(x))
		if(father[y]!=aim)
		{
			if((child[0][y]==y)==(child[0][y]==x))
				rotate(y);
			else
				rotate(x);
		}//*/
	/*for(int y;(y=father[x])!=aim;)
	{
		int z;
		if((z=father[y])==aim)
			rotate(x);
		else
			if((child[1][y]==x)==(child[1][z]==y))
				rotate(y),rotate(x);
			else
				rotate(x),rotate(x);
	}*/
	if(!aim)
		root=x;
	up(x);
	return;
}

void debug()
{
	printf("--------------------debug------------------------\n");
	rep(i,1,tot)
		printf("%d %d %d\n",i,select(i),value[select(i)]);
	printf("i fa child_l   child_r size MaxL MaxR MaxM       val   sum   res same SameVal\n");
	rep(i,1,tot)
		printf("%d %d   %d          %d     %d  %d %d %d            %d     %d  %d %d %d\n",i,father[i],child[0][i],child[1][i],size[i],MaxL[i],MaxR[i],MaxM[i],value[i],sum[i],res[i],same[i],SameVal[i]);
	printf("--------------------debug------------------------\n");
}

void insert()
{
	splay(select(pos+1));
	splay(select(pos+2),root);
	Insert(child[0][child[1][root]],1,total);
	if(child[0][child[1][root]])
		father[child[0][child[1][root]]]=child[1][root];
	up(child[1][root]);
	up(root);
	return ;
}

void Delete()
{
	splay(select(pos));
	splay(select(pos+total+1),root);
//	debug();
	child[0][child[1][root]]=0;
	splay(child[1][root]);
//	up(child[1][root]);
//	up(root);
//	tot-=total;
	return;
}

void make_same(int Pos,int Total,int ind)
{
	splay(select(Pos));
	splay(select(Pos+Total+1),root);

	same[child[0][child[1][root]]]=1;
	SameVal[child[0][child[1][root]]]=ind;

	splay(child[0][child[1][root]],0);
//	down(child[0][child[1][root]]);
//	up(child[1][root]);
//	up(root);
	return;
}

void reserve()
{
	splay(select(pos));
	splay(select(pos+total+1),root);
	res[child[0][child[1][root]]]^=1;
	
	splay(child[0][child[1][root]],0);
}

int ask_num()
{
	//printf("ask %d %d %d %d\n",pos,total,select(pos),select(pos+1+total));
	splay(select(pos));
	splay(select(pos+1+total),root);
	down(child[0][child[1][root]]);
	return sum[child[0][child[1][root]]];
}

int get_max_num()
{
	down(root);
	up(root);
	return MaxM[root];
}

void get(int &x)
{
	int ret=0;
	char ch;
	while(ch=getchar())
		if((ch>='0'&&ch<='9')||ch=='-')
			break;
	bool f=(ch=='-');
	if(f)
		ch=getchar();
	for(;ch>='0'&&ch<='9';ch=getchar())
		ret=ret*10+ch-'0';
	x=f?-ret:ret;
	return;
}

int main()
{
	MaxL[0]=MaxR[0]=MaxM[0]=-inf;
	int n,m;
	scanf("%d%d",&n,&m);
	a[1]=a[n+2]=-inf;
	rep(i,2,n+1)
		scanf("%d",&a[i]);
	n+=2;
	build(root,1,n);
	while(m--)
	{
		char s[300];
		scanf("%s",s);
		switch (s[0])
		{
			case 'I':
				get(pos);
				get(total);
				rep(i,1,total)
					get(b[i]);
				insert();
				break;
			case 'D':
				get(pos);
				get(total);
				Delete();
				break;
			case 'M':
				{
				if(s[2]=='K')
				{
					int c;
					get(pos),get(total),get(c);
					make_same(pos,total,c);
					break;
				}
				else
				{
					printf("%d\n",get_max_num());
					break;
				}
				break;
				}
			case 'R':
				get(pos),get(total);
				reserve();
				break;
			case 'G':
				get(pos),get(total);
				printf("%d\n",ask_num());
				break;
		}
		//debug();
	}
	return 0;
}

哦還附帶贈送資料生成器

自己可以調資料生成的大小，我這個隻有10個數，不過過幾百組資料的話應該就沒問題了

#include<iostream>
#include<cstring>
#include<cstdio>
#include<string>
#include<cstdlib>
#include<ctime>
#include<algorithm>
#define mod 10
#define del 10

using namespace std;

int main()
{
	freopen("1500.in","w",stdout);
	srand((unsigned)time(0));
	int n=10,m=6,no;

	string s[10];
	s[1]="INSERT";s[2]="DELETE";
	s[3]="MAKE-SAME";s[4]="RESERVE";
	s[5]="GET-SUM";s[6]="MAX-SUM";
	printf("%d %d\n",n,m);
	for(int i=1;i<=n;i++)
		no=rand()%mod-del,printf("%d\n",no);
	while(m--)
	{
		int con=rand()%6+1;
		if(con==1)
		{
			cout<<s[1]<<' ';
			int a=n,b=n;
			while(a+b>n)
				a=rand()%n+1,b=rand()%n+1;
			printf("%d %d",a,b);
			int now;
			while(b--)
				now=rand()%mod-del,printf(" %d");
			printf("\n");
		}
		else
			if(con==2||con==4||con==5)
			{
				cout<<s[con]<<' ';
				int a=n,b=n;
				while(a+b>n)
					a=rand()%n+1,b=rand()%n+1;
				printf("%d %d\n",a,b);
			}
			else
				if(con==3)
				{
					cout<<s[3]<<' ';
					int a=n,b=n;
					while(a+b>n)
						a=rand()%n+1,b=rand()%n+1;
					int now=rand()%mod-del;
					printf("%d %d %d\n",a,b,now);
				}
				else
					if(con==6)
						cout<<s[6]<<"\n";
	}
	return 0;
}

splay BZOJ1500 NOI2005 維護數列

繼續閱讀

樹的基本概念(定義、基本術語、性質)

GSL--GNU Scientific Library

D5|哈希表，善用資料結構

如何成為一名.net 工程師?

BMP檔案結構及圖像每行位元組計算方法

D. Ehab the Xorcist(構造+思維)

查找算法之二分查找查找算法之二分查找

JAVA高效程式設計指南

CQ V1.0分詞bates(基于雙數組tire樹)—應該是目前最快的中文分詞算法

【資料結構】醫院選址

[轉]ISUP信令的IAM消息詳細内容

筆試面試題目：滑動視窗(二)

交通/城市相關的公開的資料集上學時整理的Xie et al., 2020收集的

資料結構與算法（27）——排序（二）

GitHub連夜封殺！這份阿裡 10W 字内部 Java 字面試手冊到底有多強？

Linux裝置模型（中）之上層容器