NC210158. 二逼平衡树
描述
输入描述
第一行两个数 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
输出:
2 4 3 4 9
C++(clang++ 11.0.1) 解法, 执行用时: 902ms, 内存消耗: 1228K, 提交时间: 2022-10-16 22:07:44
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int ls[N],rs[N],pos[N],a[N],tmp[N];
void init(int n) {
int len=sqrt(n);
for(int i=1;i<=n;i++) pos[i]=(i-1)/len+1;
for(int i=1;i<=pos[n];i++){
ls[i]=(i-1)*len+1;
rs[i]=min(n,i*len);
}
for(int i=1;i<=pos[n];i++){
sort(tmp+ls[i],tmp+rs[i]+1);
}
}
int find_rank(int l,int r,int k){
int ans=0;
if(pos[l]==pos[r]){
for(int i=l;i<=r;i++){
if(k>a[i]){
ans++;
}
}
return ans+1;//这里有问题。
}
for(int i=l;i<=rs[pos[l]];i++){
if(k>a[i]) ans++;
}
for(int i=ls[pos[r]];i<=r;i++){
if(k>a[i]) ans++;
}
for(int i=pos[l]+1;i<=pos[r]-1;i++){
int p=lower_bound(tmp+ls[i],tmp+rs[i],k)-tmp;
if(tmp[p]>=k) p--;
p=p-ls[i]+1;
ans+=p;
}
return ans+1;
}
void change(int p,int k){
a[p]=k;
for(int i=ls[pos[p]];i<=rs[pos[p]];i++){
tmp[i]=a[i];
}
sort(tmp+ls[pos[p]],tmp+rs[pos[p]]+1);
}
int solve_2(int l,int r,int k){
int ll=0,rr=1e8,ans,now;
while(ll<rr){
int mid=ll+rr+1>>1;
now=find_rank(l,r,mid);
if(now>k){
rr=mid-1;
}
else {
ll=mid,ans=mid;
}
}
/* cout<<find_rank(l,r,ll)<<endl;*/
return ll;
}
int solve_4(int l,int r,int k){
int ans=-1e9;
if(pos[l]==pos[r]){
for(int i=l;i<=r;i++){
if(k>a[i]){
ans=max(ans,a[i]);
}
}
return ans;
}
for(int i=l;i<=rs[pos[l]];i++){
if(k>a[i]) ans=max(ans,a[i]);
}
for(int i=ls[pos[r]];i<=r;i++){
if(k>a[i]) ans=max(ans,a[i]);
}
for(int i=pos[l]+1;i<=pos[r]-1;i++){
int p=lower_bound(tmp+ls[i],tmp+rs[i],k)-tmp;
if(p>ls[i]&&tmp[p]>=k) p--;
if(k>tmp[p])
ans=max(ans,tmp[p]);
}
return ans;
}
int solve_5(int l,int r,int k){
int ans=1e9;
if(pos[l]==pos[r]){
for(int i=l;i<=r;i++){
if(k<a[i]){
ans=min(ans,a[i]);
}
}
return ans;
}
for(int i=l;i<=rs[pos[l]];i++){
if(k<a[i]) ans=min(ans,a[i]);
}
for(int i=ls[pos[r]];i<=r;i++){
if(k<a[i]) ans=min(ans,a[i]);
}
for(int i=pos[l]+1;i<=pos[r]-1;i++){
int p=upper_bound(tmp+ls[i],tmp+rs[i],k)-tmp;
if(tmp[p]>k)
ans=min(ans,tmp[p]);
}
return ans;
}
int main() {
int n,m;
cin>>n>>m;
for(int i=1;i<=n;i++) {
cin>>a[i];
tmp[i]=a[i];
}
init(n);
while(m--){
int op,l,r,k,pos;
cin>>op;
if(op==1) {
cin>>l>>r>>k;
cout<<find_rank(l,r,k)<<endl;
}
if(op==2){
cin>>l>>r>>k;
cout<<solve_2(l,r,k)<<endl;
}
if(op==3){
cin>>pos>>k;
change(pos,k);
}
if(op==4){
cin>>l>>r>>k;
cout<<solve_4(l,r,k)<<endl;
} if(op==5){
cin>>l>>r>>k;
cout<<solve_5(l,r,k)<<endl;
}
}
return 0;
}