记录编号	155189	评测结果	AAAAAAAAAA
题目名称	[ZJOI 2013] K大数查询	最终得分	100
用户昵称	水中音	是否通过	通过
代码语言	C++	运行时间	0.522 s
提交时间	2015-03-27 16:55:15	内存使用	9.28 MiB

#include<iostream>
#include<cstdio>
using namespace std;
#define lowbit(x) x&-x

int n,m,i,p,zj1,zj2,zj3;

int typ[50010]={0},l[50010]={0},r[50010]={0},c[50010]={0};
int workl[20][50010]={0},workr[20][50010]={0},ans[50010]={0};
int Add[50010]={0},Addxi[50010]={0},Sum;

inline int get_(int u,int v)
{
	for(Sum=0,i=u-1;i;i-=lowbit(i))Sum+=u*Add[i]-Addxi[i];
	for(Sum*=-1,i=v,v++;i;i-=lowbit(i))Sum+=v*Add[i]-Addxi[i];
	return Sum;
}

inline void add_(int u,int v,int w)
{
	for(v++,i=v;i<=n;i+=lowbit(i))Add[i]-=w,Addxi[i]-=w*v;
	for(i=u;i<=n;i+=lowbit(i))Add[i]+=w,Addxi[i]+=w*u;
}

inline void cdq(int dep,int *work,int L,int R)
{
	if(!work[0])return;
	int *wl=workl[dep],*wr=workr[dep],h,mid=(L+R+1)>>1;
	wl[0]=wr[0]=0;
	for(zj1=work[h=1];h<=work[0];zj1=work[++h])
	if(typ[zj1]==1)
		if(c[zj1]>=mid)wr[++wr[0]]=zj1,add_(l[zj1],r[zj1],1);
		else wl[++wl[0]]=zj1;
	else
	{
		zj2=get_(l[zj1],r[zj1]);
		if(zj2>=c[zj1])wr[++wr[0]]=zj1,ans[zj1]=mid;
		else wl[++wl[0]]=zj1,c[zj1]-=zj2;
	}
	for(zj1=work[h=1];h<=work[0];zj1=work[++h])
	if(typ[zj1]==1&&c[zj1]>=mid)add_(l[zj1],r[zj1],-1);
	if(L==R)return;
	cdq(dep+1,wl,L,mid-1);
	cdq(dep+1,wr,mid,R);
}
int main()
{
	freopen("zjoi13_sequence.in","r",stdin);
	freopen("zjoi13_sequence.out","w",stdout);
	scanf("%d%d",&n,&m);
	for(i=1;i<=m;i++)
	{
		scanf("%d%d%d%d",typ+i,l+i,r+i,c+i);
		workr[0][i]=i;
	}
	workr[0][0]=m;
	cdq(1,workr[0],1,n);
	for(i=1;i<=m;i++)
	if(typ[i]==2)printf("%d\n",ans[i]);
	return 0;
}