[BZOJ3110][ZJOI2013]K大数查询（整体二分）

时间：2024-08-06 17:32:50

BZOJ

Luogu

sol

整体二分，其实很简单的啦。

对所有询问二分一个答案mid，把所有修改操作中数字大于mid的做一个区间覆盖（区间加1）

查询就是区间查询

然后左右分一分即可

注意是第k大

然后关于树状数组的区间修改区间查询，有一篇学长的博客链接，其实原理还是蛮简单的。

比线段树好写还常数小比yyb跑得快

code

#include<cstdio>

#include<algorithm>

using namespace std;

const int N = 50005;

#define ll long long

int gi()

{

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

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

	if (ch=='-') w=0,ch=getchar();

	while (ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+ch-'0',ch=getchar();

	return w?x:-x;

}

struct query{

	int opt,a,b,c,id;

}q[N],q1[N],q2[N];

int n,m,qcnt,ans[N];ll c1[N],c2[N],tmp[N];

void modify(int pos,int val)

{

	for (int k=pos;k<=n;k+=k&-k)

		c1[k]+=val,c2[k]+=pos*val;

}

ll query(int pos)

{

	ll res=0;

	for (int k=pos;k;k-=k&-k)

		res+=(ll)(pos+1)*c1[k]-c2[k];

	return res;

}

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

{

	if (L>R) return;

	if (l==r)

	{

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

			if (q[i].opt==2) ans[q[i].id]=l;

		return;

	}

	int mid=(l+r)/2;

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

		if (q[i].opt==2) tmp[q[i].id]=query(q[i].b)-query(q[i].a-1);

		else if (q[i].c>mid) modify(q[i].a,1),modify(q[i].b+1,-1);

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

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

	int t1=0,t2=0;

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

		if (q[i].opt==2)

			if ((ll)q[i].c>tmp[q[i].id]) q[i].c-=tmp[q[i].id],q1[++t1]=q[i];

			else q2[++t2]=q[i];

		else

			if (q[i].c<=mid) q1[++t1]=q[i];

			else q2[++t2]=q[i];

	for (int i=L,j=1;j<=t1;i++,j++) q[i]=q1[j];

	for (int i=L+t1,j=1;j<=t2;i++,j++) q[i]=q2[j];

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

}

int main()

{

	n=gi();m=gi();

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

	{

		q[i].opt=gi();q[i].a=gi();q[i].b=gi();q[i].c=gi();

		if (q[i].opt==2) q[i].id=++qcnt;

	}

	solve(1,m,0,n);

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

	return 0;

}

相关文章