【HNOI模拟】 K小数查询

Description

Solution

用什么

一眼看上去就像一个数据结构，但是好像很复杂。
看看能干什么先！
能支持区间找名次，支持修改。
不知道treap可不可以做，不过区间维护名词好像不行吧。
发现范围十分的小，分块大法好。

怎么做

对每一块排一个序，维护一个加号的标记就可以了。

Code

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#define fo(i,a,b) for(i=a;i<=b;i++)
const int maxn=80007;
using namespace std;
int i,j,k,l,t,n,m,ans,a[maxn],o;
int b[405][405],jia[405],shu[maxn],chang[maxn],kua;
/*int read(){
 int x=0,f=1;
 char ch=getchar();
 while(ch<'0'||ch>'9'){
 if(ch=='-') f=-1;
 ch=getchar();
 }
 while(ch>='0'&&ch<='9'){
 x=x*10+ch-'0';
 ch=getchar();
 }
 return x*f;
}*/
void build(int x){
    chang[x]=0;
int i;
    fo(i,(x-1)*kua+1,min(n,x*kua)){
        b[x][++chang[x]]=a[i];
    }
    sort(b[x]+1,b[x]+chang[x]+1);
}
int erfen(int x,int y){
int l=0,r=chang[x],mid;
while(l<r){
        mid=(l+r+1)/2;
if(b[x][mid]+jia[x]<y)l=mid;else r=mid-1;
    }
return l;
} 
int pan(int x,int l,int r){
int i,j,k=0;
if(shu[l]==shu[r]){
        fo(i,l,r)if(a[i]+jia[shu[l]]<x)k++;
return k;
    }
    fo(i,shu[l]+1,shu[r]-1){
        k+=erfen(i,x);
    }
    fo(i,l,kua*shu[l])
if(a[i]+jia[shu[l]]<x)k++;
    fo(i,kua*(shu[r]-1)+1,r)
if(a[i]+jia[shu[r]]<x)k++;
return k;
}
int main(){
scanf("%d",&n);
    kua=400;
    fo(i,1,n){
scanf("%d",&a[i]);
        shu[i]=(i-1)/kua+1;
    }
    fo(i,1,shu[n]){
        build(i);
    }
scanf("%d",&m);
    fo(j,1,m){
scanf("%d%d%d%d",&k,&l,&t,&o);
if(k==1){
int u=shu[l],v=shu[t];
if(u==v){
                fo(i,l,t)a[i]+=o;
                build(u);
            }
else{
                fo(i,u+1,v-1)jia[i]+=o;
                fo(i,l,u*kua)a[i]+=o;
                fo(i,(v-1)*kua+1,t)a[i]+=o;
                build(u);
                build(v);
            }
        }
else{
int zuo=-5000000,you=5000000,mid;    
while(zuo<you){
                mid=(zuo+you+1)/2;
int p=pan(mid,l,t);
if(p<o){
                    zuo=mid;
                }else you=mid-1;
            } 
printf("%d\n",zuo);
        }
    }
}