首页 > 代码库 > [BZOJ 3110][Zjoi2013]K大数查询（整体二分+BIT）
[BZOJ 3110][Zjoi2013]K大数查询（整体二分+BIT）
Description
有N个位置，M个操作。操作有两种，每次操作如果是1 a b c的形式表示在第a个位置到第b个位置，每个位置加入一个数c
如果是2 a b c形式，表示询问从第a个位置到第b个位置，第C大的数是多少。
Solution
标解似乎是树套树？=w=
二分答案。
对于每一个修改，如果c>mid就进行操作，并划到后一个集合里，反之加入前一个集合；对于每一个询问，如果a-b中的数大于c个就划到后一个集合里，反之要减掉a-b中数的个数并加入前一个集合。然后对于两个集合递归下去blahblah
其中数的个数可以用区间修改区间查询的树状数组来维护（树状数组大法好…本来用的是线段树然而打清空标记的操作写得太乱调不下去了）
#include<cstdio>#include<iostream>#include<cstdlib>#include<cstring>#include<algorithm>#define MAXN 50005typedef long long LL;using namespace std;int n,m,id[MAXN],t1[MAXN],t2[MAXN],T=0;LL ans[MAXN];struct Node1{ int opt,a,b; LL c;}O[MAXN];struct BIT{ LL c[MAXN];int sign[MAXN]; int lowbit(int x){return x&-x;} void add(int pos,int x) { while(pos<=n) { if(sign[pos]!=T)c[pos]=0,sign[pos]=T; c[pos]+=x,pos+=lowbit(pos); } } LL query(int pos) { LL res=0; while(pos>0) { if(sign[pos]!=T)c[pos]=0,sign[pos]=T; res+=c[pos],pos-=lowbit(pos); } return res; }}c1,c2;void ADD(int a,int b){ c1.add(a,1),c1.add(b+1,-1); c2.add(a,a),c2.add(b+1,-b-1);}LL QUERY(int a,int b){ LL res=0; res+=(b+1)*c1.query(b)-c2.query(b); res-=a*c1.query(a-1)-c2.query(a-1); return res;}LL read(){ LL x=0,f=1;char c=getchar(); while(c<‘0‘||c>‘9‘){ if(c==‘-‘)f=-1;c=getchar(); } while(c>=‘0‘&&c<=‘9‘){ x=x*10+c-‘0‘;c=getchar(); } return x*f;}void solve(int l,int r,int ansl,int ansr){ if(l>r)return; if(ansl==ansr) { for(int i=l;i<=r;i++) if(O[id[i]].opt==2)ans[id[i]]=ansl; return; } int mid=(ansl+ansr)>>1; int j=1,k=1; T++; for(int i=l;i<=r;i++) { int idx=id[i]; if(O[idx].opt==1) { if(O[idx].c<=mid)t1[j++]=idx; else t2[k++]=idx,ADD(O[idx].a,O[idx].b); } else { LL res=QUERY(O[idx].a,O[idx].b); if(res>=O[idx].c)t2[k++]=idx; else t1[j++]=idx,O[idx].c-=res; } } --j,--k; for(int i=1;i<=j;i++)id[l+i-1]=t1[i]; for(int i=1;i<=k;i++)id[l+j+i-1]=t2[i]; solve(l,l+j-1,ansl,mid),solve(l+j,r,mid+1,ansr); }int main(){ n=read(),m=read(); for(int i=1;i<=m;i++) O[i].opt=read(),O[i].a=read(),O[i].b=read(),O[i].c=read(),id[i]=i; solve(1,m,-n,n); for(int i=1;i<=m;i++) if(O[i].opt==2)printf("%d\n",ans[i]); return 0;}
[BZOJ 3110][Zjoi2013]K大数查询（整体二分+BIT）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。