2017-02-25

【bzoj2034】K大数查询

本文为博主原创，未经许可不得转载

AC通道

题解

我们可以用整体二分解决插入对询问的影响
在此过程中，用线段树维护区间修改和区间查询即可

参考代码

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<ctime>
#include<algorithm>
using namespace std;
typedef long long ll;
#define FILE "read"
#define MAXN 50010
#define INF 1000000000
//#define up(i,j,n) for(int i=j;i<=n;++i)
//#define dn(i,j,n) for(int i=j;i>=n;--i)
#define cmax(a,b) a=max(a,b)
#define cmin(a,b) a=min(a,b)
struct node{ll x,y,opt,k,id;}q[MAXN],stack[MAXN][2];
ll n,m,cnt,ans[MAXN];
namespace INIT{
	char buf[1<<15],*fs,*ft;
	inline char getc(){return (fs==ft&&(ft=(fs=buf)+fread(buf,1,1<<15,stdin),fs==ft))?0:*fs++;}
	inline ll read(){
		ll x=0,f=1;  char ch=getc();
		while(!isdigit(ch))  {if(ch=='-')  f=-1;  ch=getc();}
		while(isdigit(ch))  {x=x*10+ch-'0';  ch=getc();}
		return x*f;
	}
}using namespace INIT;
namespace Segment_Tree{
	ll tr[MAXN<<2],clean[MAXN<<2],delt[MAXN<<2];
	void relord(int p){tr[p]=tr[p<<1]+tr[p<<1|1];}
	void pushdown(int p,int l,int r){
		if(clean[p]){
			clean[p<<1]=clean[p<<1|1]=1;  clean[p]=0;
			delt[p<<1]=delt[p<<1|1]=tr[p<<1]=tr[p<<1|1]=0;
		}
		ll d=delt[p],mid=(l+r)>>1;
		delt[p<<1]+=d;  delt[p<<1|1]+=d;
		tr[p<<1]+=d*(mid-l+1);  tr[p<<1|1]+=d*(r-mid);
		delt[p]=0;
	}
	void insert(int p,int l,int r,int x,int y){
		if(x>r||y<l)  return;
		if(x<=l&&y>=r)  {delt[p]++; tr[p]+=(r-l+1); return;}
		int mid=(l+r)>>1;  pushdown(p,l,r);
		insert(p<<1,l,mid,x,y); insert(p<<1|1,mid+1,r,x,y);
		relord(p);
	}
	ll ask(int p,int l,int r,int x,int y){
		if(x>r||y<l)  return 0;
		if(x<=l&&y>=r)  return tr[p];
		int mid=(l+r)>>1;  pushdown(p,l,r);
		return ask(p<<1,l,mid,x,y)+ask(p<<1|1,mid+1,r,x,y);
	}
}using namespace Segment_Tree;
void init(){
	n=read();  m=read();
	up(i,1,m){
		ll opt=read(),x=read(),y=read(),k=read();
		if(opt==1)  q[i]=(node){x,y,opt,k,0};
		else q[i]=(node){x,y,opt,k,++cnt};
	}
}
void solve(int l,int r,int L,int R){
	if(l>r) return;
	if(L==R){
		up(i,l,r) if(q[i].opt==2) ans[q[i].id]=L;
		return;
	}
	int mid=(L+R)>>1,ta(0),tb(0);
	clean[1]=1;  delt[1]=tr[1]=0; //清空线段树
	up(i,l,r){
		if(q[i].opt==1){
			if(q[i].k<=mid) stack[++ta][0]=q[i];
			else insert(1,1,n,q[i].x,q[i].y),stack[++tb][1]=q[i];
		}else{
			ll temp=ask(1,1,n,q[i].x,q[i].y);
			if(temp<q[i].k) q[i].k-=temp,stack[++ta][0]=q[i];
			else stack[++tb][1]=q[i];
		}
	}
	up(i,1,ta) q[i+l-1]=stack[i][0];
	up(i,1,tb) q[i+l+ta-1]=stack[i][1];
	solve(l,l+ta-1,L,mid);
	solve(l+ta,r,mid+1,R);
}
int main(){
	freopen(FILE".in","r",stdin);
	freopen(FILE".out","w",stdout);
	init(); solve(1,m,-INF,INF);
	up(i,1,cnt) printf("%lld\n",ans[i]);
	return 0;
}

本文标题:【bzoj2034】K大数查询

文章作者:chty

发布时间:2017年02月25日 - 13时41分

最后更新:2018年03月02日 - 17时27分

许可协议:本文为博主原创，未经许可不得转载。