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
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
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;
}
2015年10月23日 09:18
%%%树套树大师