K大数查询

前言

摸到一点整体二分的门路了，写一写吧。

WARNING:笔者可能自己都没懂而是在瞎BB，谨慎食用！

题目

洛谷

讲解

我们从这道例题入手整体二分。

在背了多次代码后，我终于悟到了整体二分的精髓。

有多个询问，每个询问单独来做都可以二分！

而整体二分又与 ( t dp) 有点类似，在本区间处理询问之后，将询问状态更新，变为子区间的询问，然后递归地下去处理。

而我们二分的自然就是答案了。

比如这道题，首先区间查询区间修改可以用树状数组实现，不再赘述。

对于一个区间，我们二分一个答案，我们将所有修改大于它的数都加入树状数组。

对于询问，我们直接计算区间和再与排名比较即可，由于是第K大，所以询问排名小放在右区间，否则放在左区间。

记得清空树状数组。

时间复杂度 (O(nlog^2n))。

多看看代码就懂了。

代码

int ans[MAXN];
struct node
{
	int opt,l,r,ID;
	LL c;
}s[MAXN],z[MAXN],y[MAXN];
LL t1[MAXN],t2[MAXN];
int lowbit(int x){return (x & -x);}
void Add(int x,LL val){for(int i = x;i <= n;i += lowbit(i)) t1[i] += val,t2[i] += (x-1) * val;}
void Add(int l,int r,LL val){Add(l,val);Add(r+1,-val);}
LL Sum(LL x){LL ret = 0;for(int i = x;i >= 1;i -= lowbit(i)) ret += t1[i] * x - t2[i];return ret;}

void solve(int ql,int qr,int l,int r)
{
	if(ql > qr) return;
	if(l == r)
	{
		for(int i = ql;i <= qr;++ i) if(s[i].opt == 2) ans[s[i].ID] = l;
		return;
	}
	int mid = (l+r) >> 1,zt = 0,yt = 0;
	for(int i = ql;i <= qr;++ i)
	{
		if(s[i].opt == 1)
		{
			if(s[i].c > mid) Add(s[i].l,s[i].r,1),y[++yt] = s[i];
			else z[++zt] = s[i];
		}
		else
		{
			LL dz = Sum(s[i].r) - Sum(s[i].l-1);
			if(s[i].c <= dz) y[++yt] = s[i];
			else s[i].c -= dz,z[++zt] = s[i];
		}
	}
	int now = ql;
	for(int i = ql;i <= qr;++ i)
		if(s[i].opt == 1 && s[i].c > mid) Add(s[i].l,s[i].r,-1);
	for(int i = 1;i <= zt;++ i) s[now++] = z[i];
	for(int i = 1;i <= yt;++ i) s[now++] = y[i];
	solve(ql,ql+zt-1,l,mid); solve(ql+zt,qr,mid+1,r);
}

int main()
{
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
	n = Read(); m = Read();
	for(int i = 1;i <= m;++ i) 
	{
		s[i].opt = Read();
		s[i].l = Read(),s[i].r = Read(),s[i].c = Read();
		s[i].ID = i;
	}
	solve(1,m,1,n);//数据似乎有点水，并没有负数的情况，所以。。。
	for(int i = 1;i <= m;++ i) if(ans[i]) Put(ans[i],'
');
	return 0;
}