【HNOI模拟】 K小数查询

时间:2022-12-16 21:59:00

Description

【HNOI模拟】 K小数查询

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);
}
}
}