首页 > 代码库 > 【bzoj3110】 Zjoi2013—K大数查询

【bzoj3110】 Zjoi2013—K大数查询

2024-08-17 21:28:31   221人阅读

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;}

　　

【bzoj3110】 Zjoi2013—K大数查询


联系
我们