10
15
2015
1

【区间第K大带修改】BZOJ3196 2B平衡树

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的后继

Output

对于操作1,2,4,5各输出一行,表示查询结果

Sample Input

9 6
4 2 2 1 9 4 0 1 1
2 1 4 3
3 4 10
2 1 4 3
1 2 5 9
4 3 9 5
5 2 8 5

Sample Output

2
4
3
4
9

学了树套树来水一水= =

位置线段树套权值平衡树。

就是原来线段树上的每个区间都造一棵Treap

然后利用线段树的区间加法就可以乱搞了233

建树:对于每段区间的Treap强行从L加到R。

k的排名:区间L、R中小于k的数的个数+1

第k大:二分答案,最后取mid的后继(因为我的算法中mid不一定存在于该区间)

修改:区间强行鏼出鏼入

后继:线段树上L,R之间的各段的后继中的最小值(理解一下)

前缀:线段树上L,R之间的各段的前缀中的最大值

就随便水了= =

Code:

#include<cstdio>
#include<cstring>
#include<cstdlib>
//#include<ctime>
#include<algorithm>
#include<vector>
using namespace std;
#define maxn 100000
#define maxm 1000000
#define INF 1000000000
#define MAX 100000000
#define _CNM 4000000
int a[maxn];
typedef long long LL;
int pri[_CNM],key[_CNM],ch[_CNM][2],size[_CNM],cnt[_CNM],rt[2*maxm],CNT;
//Treap
	void Init()
	{
		CNT=0;
		pri[0]=INF;
		key[0]=0;
		size[0]=0;
		memset(rt,0,sizeof(rt));
	}
	void update(int x)
	{
		size[x]=size[ch[x][0]]+cnt[x]+size[ch[x][1]];
	}
	void rotate(int &x,int t)//x的t子树旋转至x 
	{
		int y=ch[x][t];
		ch[x][t]=ch[y][1-t];
		ch[y][1-t]=x;
		update(x);
		update(y);
		x=y;
	}
	void __insert(int &x,int k)
	{
		if (x)
		{
			if (key[x]==k) cnt[x]++;
			else
			{
				int t=k>key[x];
				__insert(ch[x][t],k);
				if (pri[x]>pri[ch[x][t]]) rotate(x,t);
			}
		}
		else
		{
			x=++CNT;
			key[x]=k;
			pri[x]=rand();
			cnt[x]=1;
			ch[x][0]=ch[x][1]=0;
		}
		update(x);
	}
	void Insert(int &rt,int k)
	{
		__insert(rt,k); 
	}
	void __delete(int &x,int k)
	{
		if (!x) return;
		if (key[x]==k)
			if (cnt[x]>1) cnt[x]--;
			else
			{
				if (ch[x][0]*ch[x][1]==0) x=ch[x][0]+ch[x][1];
				else
				{
					int t=pri[ch[x][0]]>pri[ch[x][1]];
					rotate(x,t);
					__delete(x,k);
				}
			}
		else 
			__delete(ch[x][k>key[x]],k);
		update(x);
	}
	void Erase(int &rt,int k)
	{
		__delete(rt,k); 
	}
	int __GRK(int &x,int k)
	{
		int w=0;
		if (!x) return 0;
		if (key[x]==k) return size[ch[x][0]];
		if (key[x]<k) return size[ch[x][0]]+cnt[x]+__GRK(ch[x][1],k);
		if (key[x]>k) return __GRK(ch[x][0],k);
	}
	int _GRK(int rt,int k)
	{
		return __GRK(rt,k);
	}
	void __pred(int &x,int k,int &ans)
	{
		if (!x) return;
		if (key[x]<k) ans=key[x],__pred(ch[x][1],k,ans);
		if (k<=key[x])__pred(ch[x][0],k,ans);
	}
	int _Pred(int rt,int k)
	{
		int a=-INF;
		__pred(rt,k,a);
		return a;
	}
	void __succ(int &x,int k,int &ans)
	{
		if (!x) return;
		if (key[x]>k) ans=key[x],__succ(ch[x][0],k,ans);
		if (k>=key[x])__succ(ch[x][1],k,ans);
	}
	int _Succ(int rt,int k)
	{
		int a=INF;
		__succ(rt,k,a);
		return a;
	}
//Treap-End
struct ST
{
	#define lc(x) ((x)<<1)
	#define rc(x) ((x)<<1|1)
	int l[maxm],r[maxm];
	int L,R,pos,k;
	void build(int x,int L,int R)
	{
		if (L>R) return;
		l[x]=L;r[x]=R;
		int mid=L+R>>1;
		for (int i=L;i<=R;i++)
			Insert(rt[x],a[i]);
		if (L==R) return;
		build(lc(x),L,mid);
		build(rc(x),mid+1,R); 
	}
	void modify(int x)
	{
		Erase(rt[x],a[pos]);
		Insert(rt[x],k);
		if (l[x]==r[x]) return;
		int mid=l[x]+r[x]>>1;
		if (pos<=mid) modify(lc(x));
		else modify(rc(x));
	}
	void Mod(int pos,int k)
	{
		this->pos=pos;this->k=k;
		modify(1);
		a[pos]=k;
	}
	int _pred(int x)
	{
		if (L<=l[x]&&r[x]<=R) return _Pred(rt[x],k);
		if (R<l[x]||r[x]<L) return -INF;
		return max(_pred(lc(x)),_pred(rc(x)));
	}
	int Pred(int L,int R,int k)
	{
		this->L=L;this->R=R;this->k=k;
		return _pred(1);
	}
	int _succ(int x)
	{
		if (L<=l[x]&&r[x]<=R) return _Succ(rt[x],k);
		if (R<l[x]||r[x]<L) return INF;
		return min(_succ(lc(x)),_succ(rc(x)));
	}
	int Succ(int L,int R,int k)
	{
		this->L=L;this->R=R;this->k=k;
		return _succ(1);
	}
	int __GKR(int x)
	{
		if (L<=l[x]&&r[x]<=R) return _GRK(rt[x],k);
		if (R<l[x]||r[x]<L) return 0;
		return __GKR(lc(x))+__GKR(rc(x));
	}
	int GKR(int L,int R,int k)//K的排名 
	{
		this->L=L;this->R=R;this->k=k;
		return __GKR(1)+1;
	}
	int GRK(int L,int R,int k)//第K大 
	{
		int ans;
		int l=0,r=MAX,mid;
		while (l<r)
		{
			mid=l+r>>1;
			int w=GKR(L,R,mid);
			if (w>k) r=mid;
			else ans=mid,l=mid+1;
		}
		return Succ(L,R,ans-1);
	}
}WQNMLGB;
inline int read()
{
	int x=0,f=1;char ch=getchar();
	while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int main()
{
	Init();
	srand(2333);
	int n=read(),Q=read();
	for (int i=1;i<=n;i++)
		a[i]=read();
	WQNMLGB.build(1,1,n);
	int opt,L,R,x,pos;
	for(int i=1;i<=Q;i++)
	{
		opt=read();
		if (opt==1) L=read(),R=read(),x=read(),printf("%d\n",WQNMLGB.GKR(L,R,x));
		else if (opt==2) L=read(),R=read(),x=read(),printf("%d\n",WQNMLGB.GRK(L,R,x));
		else if (opt==3) pos=read(),x=read(),WQNMLGB.Mod(pos,x);
		else if (opt==4) L=read(),R=read(),x=read(),printf("%d\n",WQNMLGB.Pred(L,R,x));
		else L=read(),R=read(),x=read(),printf("%d\n",WQNMLGB.Succ(L,R,x));
	}
	return 0;
}
Category: BZOJ | Tags: 树套树 线段树 平衡树 | Read Count: 1001
jcvb 说:
2015年10月23日 09:18

%%%树套树大师


登录 *


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