BZOJ_P3110 [ZJOI2013]K大数查询(线段树+整体二分)
BZOJ传送门 Input Output Sample Input Sample Output HINT Source 读了半天题都读错了QuQ,果然是我语文不好,返回的是第K大数的位置 第一道整体二分,用了离线处理(貌似网上整体二分的资料不多?),先思考如果只有一个询问,如何二分?很简单嘛,在[L,R]的区间中取M=(L+R)>>1,计算在[L,M]区间中比询问的数大的有多少个。而整体二分,自然要整体,在二分区间的同时将所有询问一起二分处理。下面就是主要的思路
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
using namespace std;
#define N 50005
#define lc o*2
#define rc o*2+1
#define done seg.ql=q[i].l,seg.qr=q[i].r
struct SegmentTree{
int ql,qr;bool clr[N<<2];
int add[N<<2],sum[N<<2];
inline void init(){sum[1]=add[1]=0,clr[1]=1;}
inline void updata(int o){sum[o]=sum[lc]+sum[rc];}
inline void pushdown(int o,int L,int R){
if(clr[o]){sum[lc]=sum[rc]=add[lc]=add[rc]=0,clr[lc]=clr[rc]=1,clr[o]=0;}
int M=(L+R)>>1;
if(add[o]){add[lc]+=add[o],add[rc]+=add[o];
sum[lc]+=(M-L+1)*add[o],sum[rc]+=(R-M)*add[o];add[o]=0;}
}
void Add(int o,int R){
if(ql<=L&&R<=qr){add[o]++,sum[o]+=(R-L+1);return;}
int M=(L+R)>>1;pushdown(o,L,R);
if(ql<=M) Add(lc,M);if(qr>M) Add(rc,M+1,R);updata(o);
}
int Query(int o,int R){
if(ql<=L&&R<=qr){return sum[o];}
pushdown(o,R);int res=0,M=(L+R)>>1;
if(ql<=M) res+=Query(lc,M);if(qr>M) res+=Query(rc,R);
return res;
}
}seg;
struct qs{int opt,l,r,v,id,k;}q[N];
int n,m;int ans[N];
int cmp(qs a,qs b){return a.k==b.k?a.id<b.id:a.k<b.k;}
void solve(int L,int R,int l,int r){
if(l>r) return;
if(L==R){
for(int i=l;i<=r;i++)
if(q[i].opt==2) ans[q[i].id]=L;
return;
}
seg.init();
int M=(L+R)>>1,t=l-1,s;
for(int i=l;i<=r;i++){
if(q[i].opt==1){
if(q[i].v>M){done;seg.Add(1,1,n);q[i].k=1;}
else{t++,q[i].k=0;}
}
else{
done;s=seg.Query(1,n);
if(q[i].v<=s) q[i].k=1;
else t++,q[i].k=0,q[i].v-=s;
}
}
sort(q+l,q+r+1,cmp);
solve(L,M,t);solve(M+1,R,t+1,r);
}
inline int in(int x=0,char ch=getchar()){
while(ch>'9'||ch<'0') ch=getchar();
while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+ch-'0',ch=getchar();return x;
}
int main(){
n=in(),m=in();
for(int i=1;i<=m;i++){
q[i].opt=in(),q[i].l=in(),q[i].r=in(),q[i].v=in(),q[i].id=i;
}
memset(ans,-1,sizeof(ans));
solve(0,n,m);
for(int i=1;i<=m;i++) if(ans[i]!=-1) printf("%dn",ans[i]);
return 0;
}
(编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |