【bzoj3110】 Zjoi2013—K大数查询

http://www.lydsy.com/JudgeOnline/problem.php?id=3110 (题目链接)

题意

　　有N个位置，M个操作。操作有两种，每次操作如果是1 a b c的形式表示在第a个位置到第b个位置，每个位置加入一个数c；如果是2 a b c形式，表示询问从第a个位置到第b个位置，第C大的数是多少。

Solution

　　整体二分入门题。

　　对于一段操作，我们二分一个答案mid，将修改操作中加入的数c大于等于mid的操作执行（用树状数组维护一段区间中大于等于mid的数的个数）。然后对于询问判断c是否大于等于已经加入的大于等于mid的数的个数，然后不断递归下去。

细节

　　第K大的二分写的我心慌，整个都是反过来的。。

代码

// bzoj3110

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstring>

#include<cstdio>

#include<cmath>

#define LL long long

#define MOD 100000000

#define inf 2147483640

#define Pi acos(-1.0)

#define free(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout);

using namespace std;

const int maxn=50010;

struct data {int t,l,r,k,id;}a[maxn],tr[maxn],tl[maxn];

LL c1[maxn],c2[maxn];

int ans[maxn],n,m;

int lowbit(int x) {return x&-x;}

LL query(int x) {

	LL res=0;

	for (int i=x;i;i-=lowbit(i)) res+=(x+1)*c1[i]-c2[i];

	return res;

}

void add(int x,int val) {

	for (int i=x;i<=n;i+=lowbit(i)) c1[i]+=val,c2[i]+=(LL)x*val;

}

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

	if (L>R) return;

	if (l==r) {

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

		return;

	}

	int mid=(l+r+1)>>1,ll=0,rr=0,fl=0,fr=0;

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

		if (a[i].t==1) {

			if (a[i].k>=mid) add(a[i].l,1),add(a[i].r+1,-1),tr[++rr]=a[i];

			else tl[++ll]=a[i];

		}

		else {

			LL x=query(a[i].r)-query(a[i].l-1);

			if (x>=a[i].k) tr[++rr]=a[i],fr=1;

			else a[i].k-=x,tl[++ll]=a[i],fl=1;

		}

	}

	for (int i=L;i<=R;i++) if (a[i].t==1 && a[i].k>=mid) add(a[i].l,-1),add(a[i].r+1,1);

	for (int i=1;i<=ll;i++) a[L+i-1]=tl[i];

	for (int i=1;i<=rr;i++) a[L+ll+i-1]=tr[i];

	if (fl) solve(L,L+ll-1,l,mid-1);

	if (fr) solve(L+ll,R,mid,r);

}

int main() {

	scanf("%d%d",&n,&m);

	int tot=0;

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

		scanf("%d%d%d%d",&a[i].t,&a[i].l,&a[i].r,&a[i].k);

		if (a[i].t==2) a[i].id=++tot;

	}

	solve(1,m,1,n);

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

	return 0;

}