[ZJJOI2013]K大数查询 整体二分

[ZJJOI2013]K大数查询

链接

luogu

思路

整体二分。

代码

#include <bits/stdc++.h>

#define ll long long

using namespace std;

const ll _=5e5+7;

ll read() {

	ll x=0,f=1;char s=getchar();

	for(;s>'9'||s<'0';s=getchar()) if(s=='-') f=-1;

	for(;s>='0'&&s<='9';s=getchar()) x=x*10+s-'0';

	return x*f;

}

ll n,m,ans[_];

struct OPT {ll opt,a,b,c,id;}Q[_],tmp1[_],tmp2[_];

namespace seg {

	#define ls rt<<1

	#define rs rt<<1|1

	struct node {

		ll l,r,lazy,siz;

		unsigned ll tot;

	}e[_<<2];

	void build(ll l,ll r,ll rt) {

		e[rt].l=l,e[rt].r=r,e[rt].siz=r-l+1;

		ll mid=(l+r)>>1;

		if(l==r) return;

		build(l,mid,ls);

		build(mid+1,r,rs);

	}

	void pushdown(ll rt) {

		if(e[rt].lazy) {

			e[ls].tot+=e[ls].siz*e[rt].lazy;

			e[rs].tot+=e[rs].siz*e[rt].lazy;

			e[ls].lazy+=e[rt].lazy;

			e[rs].lazy+=e[rt].lazy;

			e[rt].lazy=0;

		}

	}

	void modify(ll L,ll R,ll ad,ll rt) {

		if(L<=e[rt].l&&e[rt].r<=R) {

			e[rt].tot+=e[rt].siz*ad;

			e[rt].lazy+=ad;

			return;

		}

		ll mid=(e[rt].l+e[rt].r)>>1;

		pushdown(rt);

		if(L<=mid) modify(L,R,ad,ls);

		if(R>mid) modify(L,R,ad,rs);

		e[rt].tot=e[ls].tot+e[rs].tot;

	}

	unsigned ll query(ll L,ll R,ll rt) {

		if(L<=e[rt].l&&e[rt].r<=R) return e[rt].tot;

		ll mid=(e[rt].l+e[rt].r)>>1;

		unsigned ll ans=0;

		pushdown(rt);

		if(L<=mid) ans+=query(L,R,ls);

		if(R>mid) ans+=query(L,R,rs);

		return ans;

	}

}

void solve(ll l,ll r,ll vl,ll vr) {

	if(vl==vr||l>r) {

		for(ll i=l;i<=r;++i) ans[Q[i].id]=vl;

		return;

	}

	ll mid=(vl+vr)>>1,p=-1,q=-1;

	for(ll i=l;i<=r;++i) {

		if(Q[i].opt==1) {

			if(Q[i].c>mid) {

				seg::modify(Q[i].a,Q[i].b,1,1);

				tmp2[++q]=Q[i];

			} else tmp1[++p]=Q[i];

		} else {

			ll tmp=seg::query(Q[i].a,Q[i].b,1);

			if(Q[i].c<=tmp) tmp2[++q]=Q[i];

			else Q[i].c-=tmp,tmp1[++p]=Q[i];

		}

	}

	for(ll i=l;i<=r;++i)

		if(Q[i].opt==1&&Q[i].c>mid) seg::modify(Q[i].a,Q[i].b,-1,1);

	for(ll i=0;i<=p;++i) Q[l+i]=tmp1[i];

	for(ll i=0;i<=q;++i) Q[l+p+1+i]=tmp2[i];

	solve(l,l+p,vl,mid);

	solve(l+p+1,r,mid+1,vr);

}

int main() {

	n=read(),m=read();

	seg::build(1,n,1);

	ll cnt=0;

	for(ll i=1;i<=m;++i) {

		Q[i].opt=read();

		Q[i].a=read(),Q[i].b=read(),Q[i].c=read();

		if(Q[i].opt==2) Q[i].id=++cnt;

	}

	solve(1,m,-n,n);

	for(ll i=1;i<=cnt;++i)

		printf("%lld\n",ans[i]);

	return 0;

}