【BZOJ3110】K大数查询（整体二分）

时间：2023-03-08 15:52:46
【BZOJ3110】K大数查询（整体二分）

【BZOJ3110】K大数查询（整体二分）

题面

BZOJ

题解

看了很久整体二分

一直不知道哪里写错了

。。。

又把树状数组当成线段树区间加法来用了。。

整体二分还是要想清楚在干什么：

我们考虑第\(K\)大是什么

就是还有\(K-1\)个比他小

这样子就可以考虑二分之后如何\(check\)

当前二分出一个答案之后

按照时间顺序检查每个操作

如果是添加：

如果加进去的值比二分的答案要小

证明对结果没有贡献

直接丢到左区间里不管

否则线段树做区间加法

如果是修改

检查一下当前是否满足

然后分类丢到左右区间

总的来说

想清楚还是挺容易的

#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<cmath>

#include<algorithm>

#include<set>

#include<map>

#include<vector>

#include<queue>

using namespace std;

#define ll long long

#define RG register

#define MAX 52000

#define lson (now<<1)

#define rson (now<<1|1)

inline int read()

{

    RG int x=0,t=1;RG char ch=getchar();

    while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();

    if(ch=='-')t=-1,ch=getchar();

    while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();

    return x*t;

}

struct Node

{

	int clr;

	int ly;

	ll sum;

	void clear(){clr=ly=sum=0;}

}t[MAX<<3];

int n,m,ans[MAX];

void putlazy(int now,int l,int r,int w)

{

	t[now].sum+=w*(r-l+1);

	t[now].ly+=w;

}

void clr(int now)

{

	if(t[now].clr)

	{

		t[lson].clear();

		t[rson].clear();

		t[lson].clr=1;

		t[rson].clr=1;

		t[now].clr=0;

	}

}

void pushdown(int now,int l,int r)

{

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

	clr(now);

	putlazy(lson,l,mid,t[now].ly);

	putlazy(rson,mid+1,r,t[now].ly);

	t[now].ly=0;

}

void Modify(int now,int l,int r,int L,int R)

{

	pushdown(now,l,r);

	if(l==L&&r==R){putlazy(now,l,r,1);return;}

	t[now].sum+=R-L+1;

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

	if(R<=mid)Modify(lson,l,mid,L,R);

	else if(L>mid)Modify(rson,mid+1,r,L,R);

	else{Modify(lson,l,mid,L,mid);Modify(rson,mid+1,r,mid+1,R);}

}

ll Query(int now,int l,int r,int L,int R)

{

	pushdown(now,l,r);

	if(L<=l&&r<=R)return t[now].sum;

	int mid=(l+r)>>1;ll ret=0;

	if(L<=mid)ret+=Query(lson,l,mid,L,R);

	if(R>mid)ret+=Query(rson,mid+1,r,L,R);

	return ret;

}

struct Ask{int opt,l,r,c,id;}p[MAX],p1[MAX],p2[MAX];

void Work(int L,int R,int l,int r)

{

	if(L>R)return;

	if(l==r)

	{

		for(int i=L;i<=R;++i)ans[p[i].id]=l;

		return;

	}

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

	int t1=0,t2=0;

	for(int i=L;i<=R;++i)

	{

		if(p[i].opt==1)

		{

			if(p[i].c<=mid)p1[++t1]=p[i];

			else

			{

				p2[++t2]=p[i];

				Modify(1,1,n,p[i].l,p[i].r);

			}

		}

		else

		{

			ll ss=Query(1,1,n,p[i].l,p[i].r);

			if(ss>=p[i].c)p2[++t2]=p[i];

			else p[i].c-=ss,p1[++t1]=p[i];

		}

	}

	for(int i=1;i<=t1;++i)p[L+i-1]=p1[i];

	for(int i=1;i<=t2;++i)p[L+t1+i-1]=p2[i];

	t[1].clear();t[1].clr=1;

	Work(L,L+t1-1,l,mid);Work(L+t1,R,mid+1,r);

}

int main()

{

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

	int sum=0;

	for(int i=1;i<=m;++i)

	{

		p[i].opt=read();p[i].l=read();p[i].r=read();p[i].c=read();

		if(p[i].opt==2)p[i].id=++sum;

	}

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

	for(int i=1;i<=sum;++i)printf("%d\n",ans[i]);

	return 0;

}

相关文章