bzoj3196 Tyvj 1730 二逼平衡树 线段树套splay

Description

您需要写一种数据结构（可参考题目标题），来维护一个有序数列，其中需要提供以下操作：

1.查询k在区间内的排名

2.查询区间内排名为k的值

3.修改某一位值上的数值

4.查询k在区间内的前驱(前驱定义为小于x，且最大的数)

5.查询k在区间内的后继(后继定义为大于x，且最小的数)

Input

第一行两个数 n,m 表示长度为n的有序序列和m个操作

第二行有n个数，表示有序序列

下面有m行，opt表示操作标号

若opt=1 则为操作1，之后有三个数l,r,k 表示查询k在区间[l,r]的排名

若opt=2 则为操作2，之后有三个数l,r,k 表示查询区间[l,r]内排名为k的数

若opt=3 则为操作3，之后有两个数pos,k 表示将pos位置的数修改为k

若opt=4 则为操作4，之后有三个数l,r,k 表示查询区间[l,r]内k的前驱

若opt=5 则为操作5，之后有三个数l,r,k 表示查询区间[l,r]内k的后继

1.n和m的数据范围：n,m<=50000

2.序列中每个数的数据范围：[0,1e8]

3.虽然原题没有，但事实上5操作的k可能为负数

Solution

无脑题做得整个人都无脑掉了。。。

注意到我们要对序列和值域两维搞搞正，考虑数据结构套数据结构

一个比较显然的小常数做法是树状数组套离散线段树，由于卡空间考虑线段树套splay

我们每次插入一个数字就在对应线段树区间上的splay插入，删除同理

操作1就把x在多个splay中的rank加起来，操作2就二分答案，操作3就插入删除logn次，操作4和5直接在splay上取前驱后继求minmax

说起来非常的容易

Code

#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <set>
#define rep(i,st,ed) for (int i=st;i<=ed;++i)
#define lowbit(x) (x&-x)

const int INF=2147483647;
const int N=50005;

struct treeNode {int son[2],size,cnt,fa,val;} t[N*51];

int root[N*51],tot;
int a[N],n,ans;

int read() {
	int x=0,v=1; char ch=getchar();
	for (;ch<'0'||ch>'9';v=(ch=='-')?(-1):(v),ch=getchar());
	for (;ch<='9'&&ch>='0';x=x*10+ch-'0',ch=getchar());
	return x*v;
}

void push_up(int x) {
	t[x].size=t[t[x].son[0]].size+t[t[x].son[1]].size+t[x].cnt;
}

void rotate(int x) {
	int y=t[x].fa; int z=t[y].fa;
	int k=t[y].son[1]==x;
	t[x].fa=z; t[z].son[t[z].son[1]==y]=x;
	t[y].son[k]=t[x].son[!k]; t[t[x].son[!k]].fa=y;
	t[y].fa=x; t[x].son[!k]=y;
	push_up(y); push_up(x);
}

void splay(int &root,int x,int goal=0) {
	for (;t[x].fa!=goal;) {
		int y=t[x].fa; int z=t[y].fa;
		if (z!=goal) {
			if ((t[y].son[1]==x)^(t[z].son[1]==y)) rotate(x);
			else rotate(y);
		}
		rotate(x);
	}
	if (!goal) root=x;
}

void insert(int &root,int v) {
	for (int x=root,y;233;) {
		if (!x) {
			t[x=++tot].fa=y;
			t[x].size=t[x].cnt=1;
			t[x].val=v;
			t[y].son[v>t[y].val]=x;
			splay(root,x,0);
			return ;
		}
		if (v==t[x].val) {
			t[x].size++; t[x].cnt++;
			splay(root,x,0);
			return ;
		}
		if (v<t[x].val) y=x,x=t[x].son[0];
		else y=x,x=t[x].son[1];
	}
}

int get_pre(int root,int x) {
	int res=-INF;
	for (int pre=root;pre;) {
		if (t[pre].val<x) res=std:: max(res,t[pre].val),pre=t[pre].son[1];
		else pre=t[pre].son[0];
	}
	return res;
}

int get_nex(int root,int x) {
	int res=INF;
	for (int nex=root;nex;) {
		if (t[nex].val>x) res=std:: min(res,t[nex].val),nex=t[nex].son[0];
		else nex=t[nex].son[1];
	}
	return res;
}

int find(int root,int v) {
	for (int x=root;233;) {
		if (t[x].val==v) return x;
		if (t[x].val>v) x=t[x].son[0];
		else x=t[x].son[1];
	}
}

void del(int &root,int v) {
	int pre=find(root,get_pre(root,v));
	splay(root,pre,0);
	int nex=find(root,get_nex(root,v));
	splay(root,nex,root);
	int x=t[nex].son[0];
	if (t[x].cnt>1) {
		t[x].cnt--;
		splay(root,x,0);
		return ;
	}
	t[x].fa=t[nex].son[0]=0;
	push_up(nex); push_up(pre);
}

void modify(int now,int tl,int tr,int x,int v,int opt) {
	if (x<tl||tr<x) return ;
	if (opt) insert(root[now],v);
	else del(root[now],v);
	if (tl==tr) return ;
	int mid=(tl+tr)>>1;
	modify(now<<1,tl,mid,x,v,opt);
	modify(now<<1|1,mid+1,tr,x,v,opt);
}

int get_rank(int root,int v) {
	int res=0;
	for (int x=root;x;) {
		if (t[x].val>v) x=t[x].son[0];
		else if (t[x].val<v) {
			res+=t[t[x].son[0]].size+t[x].cnt;
			x=t[x].son[1];
		} else if (t[x].val==v) {
			res+=t[t[x].son[0]].size;
			x=t[x].son[1];
		}
	}
	return res;
}

int query(int now,int tl,int tr,int l,int r,int x) {
	if (r<l) return 0;
	if (tl>=l&&tr<=r) {
		return get_rank(root[now],x);
	}
	int mid=(tl+tr)>>1;
	int qx=query(now<<1,tl,mid,l,std:: min(r,mid),x);
	int qy=query(now<<1|1,mid+1,tr,std:: max(mid+1,l),r,x);
	return qx+qy;
}

void build_tree(int now,int tl,int tr) {
	root[now]=++tot;
	t[tot].val=-INF;
	t[root[now]].son[1]=++tot;
	t[tot].val=INF;
	t[tot].fa=tot-1;
	if (tl==tr) return ;
	int mid=(tl+tr)>>1;
	build_tree(now<<1,tl,mid);
	build_tree(now<<1|1,mid+1,tr);
}

void qpre(int now,int tl,int tr,int l,int r,int x) {
	if (r<l) return ;
	if (tl>=l&&tr<=r) {
		ans=std:: max(ans,get_pre(root[now],x));
		return ;
	}
	int mid=(tl+tr)>>1;
	qpre(now<<1,tl,mid,l,std:: min(r,mid),x);
	qpre(now<<1|1,mid+1,tr,std:: max(mid+1,l),r,x);
}

void qnex(int now,int tl,int tr,int l,int r,int x) {
	if (r<l) return ;
	if (tl>=l&&tr<=r) {
		ans=std:: min(ans,get_nex(root[now],x));
		return ;
	}
	int mid=(tl+tr)>>1;
	qnex(now<<1,tl,mid,l,std:: min(r,mid),x);
	qnex(now<<1|1,mid+1,tr,std:: max(mid+1,l),r,x);
}

int main(void) {
	freopen("data.in","r",stdin);
	freopen("myp.out","w",stdout);
	n=read(); int m=read();
	build_tree(1,1,n);
	rep(i,1,n) {
		a[i]=read();
		modify(1,1,n,i,a[i],1);
	}
	for (int opt,l,r,k;m--;) {
		opt=read(),l=read(),r=read();
		if (opt!=3) k=read();
		if (opt==1) printf("%d\n", query(1,1,n,l,r,k)+1);
		else if (opt==2) {
			int tl=0,tr=INF;
			for (;tl<=tr;) {
				int mid=(tl+tr)>>1;
				if (query(1,1,n,l,r,mid)<k) tl=mid+1;
				else tr=mid-1;
			}
			printf("%d\n", tr);
		} else if (opt==3) {
			modify(1,1,n,l,a[l],0); a[l]=r;
			modify(1,1,n,l,a[l],1);
		} else if (opt==4) {
			ans=-INF; qpre(1,1,n,l,r,k);
			printf("%d\n", ans);
		} else if (opt==5) {
			ans=INF; qnex(1,1,n,l,r,k);
			printf("%d\n", ans);
		}
	}
	return 0;
}