BZOJ 3110: [Zjoi2013]K大数查询

starli posted @ 2016年2月12日 10:10 in 数据结构 , 221 阅读

学了一下整体二分,就拿这题练练手- -

线段树标记下传的时候把+=写成了=调了N久也是醉

#include <cstdio>
#include <algorithm>
using namespace std;
const int N=50010,INF=~0u>>1;
struct ask{int op,cur,ans,tmp,l,r,c,id;}qs[N],q[N*4],q1[N*4],q2[N*4];
int T[N*4],tag[N*4],L[N*4],R[N*4],ans[N*4],n,m;
typedef long long LL;
void up(int x){T[x]=T[x<<1]+T[x<<1|1];}
void down(int x){
	if(tag[x]){
		T[x<<1]+=(R[x<<1]-L[x<<1]+1)*tag[x];tag[x<<1]+=tag[x];
		T[x<<1|1]+=(R[x<<1|1]-L[x<<1|1]+1)*tag[x];tag[x<<1|1]+=tag[x];
		tag[x]=0;
	}
}
void build(int x,int l,int r){
	L[x]=l;R[x]=r;
	if(l==r){T[x]=0;return;}
	int mid=(l+r)>>1;
	build(x<<1,l,mid);build(x<<1|1,mid+1,r);
	up(x);
}
void change(int x,int l,int r,int d){
	if(l<=L[x] && R[x]<=r) {tag[x]+=d;T[x]+=d*(R[x]-L[x]+1);return;}
	int mid=(L[x]+R[x])>>1;
	down(x);
	if(mid>=l) change(x<<1,l,r,d);
	if(mid<r) change(x<<1|1,l,r,d);
	up(x);
}
int query(int x,int l,int r){
	if(l<=L[x] && R[x]<=r) {return T[x];}
	int mid=(L[x]+R[x])>>1,ret=0;
	down(x);
	if(mid>=l) ret+=query(x<<1,l,r);
	if(mid<r) ret+=query(x<<1|1,l,r);
	return ret;
}
void solve(int s,int t,LL l,LL r){
	if(s>t) return ; 
	if(l==r) {for(int i=s;i<=t;i++) if(q[i].op==2) ans[q[i].id]=l;return;}
	int mid=(l+r)>>1,t1=0,t2=0;
	for(int i=s;i<=t;i++){
		if(q[i].op==1 && q[i].c>mid) change(1,q[i].l,q[i].r,1);
		if(q[i].op==2)q[i].tmp=query(1,q[i].l,q[i].r);
	}
	for(int i=s;i<=t;i++) if(q[i].op==1 && q[i].c>mid) change(1,q[i].l,q[i].r,-1); 
	for(int i=s;i<=t;i++) 
		if(q[i].op==2){
			if(q[i].cur+q[i].tmp>=q[i].c) q1[++t1]=q[i];
			else q[i].cur+=q[i].tmp,q2[++t2]=q[i];
		}else{ 
			if(q[i].c>mid) q1[++t1]=q[i];else q2[++t2]=q[i];
		}
	for(int i=1;i<=t1;i++) q[s+i-1]=q1[i];
	for(int i=1;i<=t2;i++) q[s+t1+i-1]=q2[i];
	solve(s,s+t1-1,mid+1,r);
	solve(s+t1,t,l,mid);
}
int main(){
	//freopen("3110.in","r",stdin);freopen("3110.out","w",stdout);
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++) scanf("%d%d%d%d",&qs[i].op,&qs[i].l,&qs[i].r,&qs[i].c),qs[i].id=i,q[i]=qs[i];
	build(1,1,n);
	solve(1,m,-INF,INF);
	for(int i=1;i<=m;i++) if(qs[i].op==2)printf("%d\n",ans[i]==INF?0:ans[i]);
	return 0;
}	

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter