[ZJOI2013]K大数查询

洛咕

题意:(n(n<=50000))个位置,每个位置可以看做一个集合,初始为空,(m(m<=50000))个操作,一是给([l,r])每个位置插入一个数(x),二是询问([l,r])中第(k)大的数是多少?

分析:询问操作对于整体二分来说很熟悉,只是注意本题是查询第(k)大,注意一下符号的问题.然后考虑插入操作((l,r,x)),如果(x>=mid),相当于我们现在要给([l,r])中每个数都加上1,相当于是区间增加操作,然后统计答案的时候就是区间询问了,可以用线段树(好像还不是普通的线段树)维护,本人太懒,为此学了一下树状数组的区间修改和区间询问操作,推荐一篇博客:树状数组的区间修改和区间询问操作.

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
#include<map>
#include<set>
#define ll long long
using namespace std;
inline ll read(){
    ll x=0,o=1;char ch=getchar();
    while(ch!='-'&&(ch<'0'||ch>'9'))ch=getchar();
    if(ch=='-')o=-1,ch=getchar();
    while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
    return x*o;
}
const int N=50005;
int n,m,tim,ans[N];ll c1[N],c2[N];
struct query{int x,y,opt,id;ll z;}q[N],ql[N],qr[N];
inline int lowbit(int x){return x&-x;}
inline void add(int pos,int val){
    for(int x=pos;x<=n;x+=lowbit(x))
        c1[x]+=val,c2[x]+=1ll*pos*val;
}
inline ll ask(int pos){
    ll cnt=0;
    for(int x=pos;x;x-=lowbit(x))
        cnt+=1ll*(pos+1)*c1[x]-c2[x];
    return cnt;
}
inline void solve(int l,int r,int st,int ed){
	if(st>ed)return;
	if(l==r){
		for(int i=st;i<=ed;++i)
			if(q[i].opt==2)ans[q[i].id]=l;
		return;
	}
	int mid=(l+r)>>1,lt=0,rt=0;
	for(int i=st;i<=ed;++i){
		if(q[i].opt==1){
			if(q[i].z>mid)add(q[i].x,1),add(q[i].y+1,-1),qr[++rt]=q[i];
			else ql[++lt]=q[i];
		}
		else if(q[i].opt==2){
			ll sum=ask(q[i].y)-ask(q[i].x-1);//sum会爆int
			if(sum>=q[i].z)qr[++rt]=q[i];
			else q[i].z-=sum,ql[++lt]=q[i];
		}
	}
	for(int i=ed;i>=st;--i){
		if(q[i].opt==2||q[i].z<=mid)continue;
		add(q[i].x,-1),add(q[i].y+1,1);
	}
	for(int i=1;i<=lt;++i)q[st+i-1]=ql[i];
	for(int i=1;i<=rt;++i)q[lt+st+i-1]=qr[i];
	solve(l,mid,st,st+lt-1);solve(mid+1,r,st+lt,ed);
}
int main(){
	n=read();m=read();
	for(int i=1;i<=m;++i){
		q[i].opt=read();q[i].x=read();q[i].y=read();q[i].z=read();
		if(q[i].opt==2)q[i].id=++tim;//额外给询问操作记录一下顺序,方便离线回答
	}
	solve(-n,n,1,m);//题目保证了增加操作中的数在[-n,n]范围内
	for(int i=1;i<=tim;++i)printf("%d
",ans[i]);
    return 0;
}