记录编号	129601	评测结果	AAAAAAAAAA
题目名称	[ZJOI 2013] K大数查询	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	0.494 s
提交时间	2014-10-20 10:41:07	内存使用	3.94 MiB

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
typedef long long LL;
const int SIZEN=50010,SIZEM=50010,INF=0x7fffffff;
class TARRAY{//改段求段的树状数组
public:
	int n;
	//我们设在数组A上进行操作,数组B:A[1~i]被整体加了多少,数组C=B[i]*i
	//则A[1~i]的前缀和为:i*(B[i]+...+B[N])+(C[1]+...+C[i-1])
	//我们需要维护B的前缀和(s)及C的后缀和(rs)
	int s[SIZEN];
	int rs[SIZEN];
	void clear(int x){n=x;memset(s,0,sizeof(s));memset(rs,0,sizeof(rs));}
	int lowbit(int x){return x&(-x);}
	void prefchange(int x,int t){
		if(x<1) return;
		for(int i=x;i>0;i-=lowbit(i)) s[i]+=t;
		for(int i=x;i<=n;i+=lowbit(i)) rs[i]+=x*t;
	}
	int prefsum(int x){
		if(x<1) return 0;
		int b=0,c=0;
		for(int i=x;i<=n;i+=lowbit(i)) b+=s[i];
		for(int i=x-1;i>0;i-=lowbit(i)) c+=rs[i];
		return b*x+c;
	}
	void change(int l,int r,int t){
		prefchange(r,t);
		prefchange(l-1,-t);
	}
	int segsum(int l,int r){
		return prefsum(r)-prefsum(l-1);
	}
};
class OPT{
public:
	int id,cmd;
	int a,b,c;
	void print(void){cout<<id<<" "<<cmd<<" "<<a<<" "<<b<<" "<<c<<endl;}
};
OPT s[SIZEM];
int ans[SIZEM]={0};
int cnt[SIZEM]={0};
TARRAY T;
OPT s1[SIZEM],s2[SIZEM];
void solve(int a,int b,int l,int r){//已确定s[a]~s[b]的操作与答案均在[l,r]区间内
	if(l==r){
		for(int i=a;i<=b;i++) if(s[i].cmd==2) ans[s[i].id]=l;
		return;
	}
	int mid=(LL)(l+r)/2;
	//下面2我们只统计那些>=mid+1的修改
	for(int i=a;i<=b;i++){
		if(s[i].cmd==1){//这是一个修改
			if(s[i].c>=mid+1) T.change(s[i].a,s[i].b,1);
		}
		else if(s[i].cmd==2){
			cnt[i]=T.segsum(s[i].a,s[i].b);
		}
	}
	for(int i=a;i<=b;i++)//再改回去......
		if(s[i].cmd==1&&s[i].c>=mid+1) T.change(s[i].a,s[i].b,-1);
	int p1=0,p2=0;
	for(int i=a;i<=b;i++){//第一部分是<=mid的
		if(s[i].cmd==1){
			if(s[i].c<=mid) s1[p1++]=s[i];
			else s2[p2++]=s[i];
		}
		else if(s[i].cmd==2){
			if(cnt[i]>=s[i].c) s2[p2++]=s[i];
			else s[i].c-=cnt[i],s1[p1++]=s[i];
		}
	}
	for(int i=0;i<p1;i++) s[a+i]=s1[i];
	for(int i=0;i<p2;i++) s[a+p1+i]=s2[i];
	solve(a,a+p1-1,l,mid);
	solve(a+p1,b,mid+1,r);
}
int N,M,qn=0;
int mn=INF,mx=0;
void answer(void){
	for(int i=1;i<=qn;i++) printf("%d\n",ans[i]);
}
void read(void){
	scanf("%d%d",&N,&M);
	T.clear(N);
	for(int i=1;i<=M;i++){
		scanf("%d%d%d%d",&s[i].cmd,&s[i].a,&s[i].b,&s[i].c);
		if(s[i].cmd==2) s[i].id=++qn;
		else mn=min(mn,s[i].c),mx=max(mx,s[i].c);
	}
}
int main(){
	freopen("zjoi13_sequence.in","r",stdin);
	freopen("zjoi13_sequence.out","w",stdout);
	read();
	solve(1,M,mn,mx);
	answer();
	return 0;
}