题目描述
您需要写一种数据结构（可参考题目标题），来维护一个有序数列，其中需要提供以下操作：
-
查询k在区间内的排名
-
查询区间内排名为k的值
-
修改某一位值上的数值
-
查询k在区间内的前驱(前驱定义为严格小于x，且最大的数，若不存在输出-2147483647)
- 查询k在区间内的后继(后继定义为严格大于x，且最小的数，若不存在输出2147483647)
注意上面两条要求和tyvj或者bzoj不一样，请注意
输入输出格式
输入格式：
第一行两个数 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,2,4,5各输出一行，表示查询结果
输入输出样例
输入样例#1： 复制
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
输出样例#1： 复制
2 4 3 4 9
说明
时空限制：2s，128M
n,m≤5⋅104 n,m leq 5cdot {10}^4 n,m≤5⋅104 保证有序序列所有值在任何时刻满足 [0,108] [0, {10} ^8] [0,108]
题目来源：bzoj3196 / Tyvj1730 二逼平衡树，在此鸣谢
此数据为洛谷原创。（特别提醒：此数据不保证操作5、6一定存在，故请务必考虑不存在的情况）
一直觉得树套树好难好难的,写了一下，觉得还好，(●'◡'●)
#include<bits/stdc++.h>
#define lb(x) (-x&x)
#define nn 500011
using namespace std;
const int inf=1e8;
int ls[nn*97],rs[nn*97],sum[nn*97];
int rot[nn],a[nn],ql[nn],qr[nn];
int li,nod,n;
int read()
{
int ans=0,f=1;char ch=getchar();
while(!isdigit(ch)) {if(ch=='-') f=-1;ch=getchar();}
while(isdigit(ch)) {ans=ans*10+ch-'0';ch=getchar();}
return ans*f;
}
void amend(int &rt,int l,int r,int v,int nv)
{
if(!rt) rt=++nod;
sum[rt]+=nv;
if(l==r) return;
int mid=(l+r)>>1;
if(v<=mid) amend(ls[rt],l,mid,v,nv);
else amend(rs[rt],mid+1,r,v,nv);
}
void modify(int p,int v,int nv)
{
for(int i=p;i<=n;i+=lb(i))
amend(rot[i],0,inf,v,nv);
}
int getnum(int rt,int l,int r,int x)
{
if(!rt) return 0;
if(l==r) return sum[rt];
int mid=(l+r)>>1;
if(x<=mid)
return getnum(ls[rt],l,mid,x);
else
return sum[ls[rt]]+getnum(rs[rt],mid+1,r,x);
}
int rank(int l,int r,int x) //l,r里查询x的排名
{
int num=0;l--;
for(int i=r;i>=1;i-=lb(i))
num+=getnum(rot[i],0,inf,x-1);
for(int i=l;i>=1;i-=lb(i))
num-=getnum(rot[i],0,inf,x-1);
return num+1;
}
int findk(int l,int r,int k) //l,r里查询排名为k的
{
int h1=1,t1=0,tt1,h2=1,t2=0,tt2,lv=0,rv=inf,num;l--;
for(int i=l;i>=1;i-=lb(i))
if(rot[i]&&sum[rot[i]])
ql[++t1]=rot[i];
for(int i=r;i>=1;i-=lb(i))
if(rot[i]&&sum[rot[i]])
qr[++t2]=rot[i];
while(lv!=rv)
{
num=0;
for(int i=h1;i<=t1;i++)
num-=sum[ls[ql[i]]];
for(int i=h2;i<=t2;i++)
num+=sum[ls[qr[i]]];
tt1=t1,tt2=t2;
while(h1<=tt1)
{
if(num>=k)
{
ql[++t1]=ls[ql[h1++]];
if(!ql[t1]||!sum[ql[t1]]) t1--;
}
else
{
ql[++t1]=rs[ql[h1++]];
if(!ql[t1]||!sum[ql[t1]]) t1--;
}
}
while(h2<=tt2)
{
if(num>=k)
{
qr[++t2]=ls[qr[h2++]];
if(!qr[t2]||!sum[qr[t2]]) t2--;
}
else
{
qr[++t2]=rs[qr[h2++]];
if(!qr[t2]||!sum[qr[t2]]) t2--;
}
}
if(num>=k)
rv=(lv+rv)>>1;
else
lv=((lv+rv)>>1)+1,k-=num;
}
return rv;
}
int pre(int l,int r,int x)
{
int k=rank(l,r,x)-1;
if(k<=0)
return -2147483647;
return findk(l,r,k);
}
int sub(int l,int r,int x)
{
int k=rank(l,r,x+1)-1;
if(k==r-l+1)
return 2147483647;
int ans=findk(l,r,k+1);
return ans;
}
int main()
{
int m,opt,x,l,r;
n=read();m=read();
for(int i=1;i<=n;i++)
a[i]=read(),modify(i,a[i],1);
for(int i=1;i<=m;i++)
{
opt=read();l=read();r=read();
if(opt==1)
x=read(),printf("%d
",rank(l,r,x));
if(opt==2)
x=read(),printf("%d
",findk(l,r,x));
if(opt==3)
modify(l,a[l],-1),modify(l,a[l]=r,1);
if(opt==4)
x=read(),printf("%d
",pre(l,r,x));
if(opt==5)
x=read(),printf("%d
",sub(l,r,x));
}
return 0;
}