bzoj 3110 K大数查询 整体二分
发布时间:2020-12-30 15:47:35 所属栏目:大数据 来源:网络整理
导读:#includecstdio #includeiostream #define maxn 50005 #define LL long long using namespace std; int n, m ;struct Que{ int op,l,r, x ,id; void read () { scanf( " %d %d %d %d " ,op,l,r, x ); if (op== 1 ) x +=n+ 1 ; }} q[50005] ;Que q1[maxn],q2[
#include<cstdio> #include<iostream> #define maxn 50005 #define LL long long using namespace std; int n,m; struct Que{ int op,l,r,x,id; void read() { scanf("%d%d%d%d",&op,&l,&r,&x); if(op==1) x+=n+1; } }q[50005]; Que q1[maxn],q2[maxn]; int ans[maxn]; struct XDS { struct xds { int l,add; LL sum; bool clear; }tree[maxn<<3]; void build(int x,int l,int r) { tree[x].l=l; tree[x].r=r; if(l==r) return ; int mid=(l+r)>>1; build(x<<1,mid); build(x<<1|1,mid+1,r); } void init() { tree[1].sum=tree[1].add=0; tree[1].clear=1; } int L,R; int sz(int x) {return tree[x].r-tree[x].l+1;} void update(int x) {tree[x].sum=tree[x<<1].sum+tree[x<<1|1].sum;} void spread(int x) { if(tree[x].clear) { // cout<<x<<endl; tree[x<<1].sum=tree[x<<1|1].sum=0; tree[x<<1].add=tree[x<<1|1].add=0; tree[x<<1].clear=tree[x<<1|1].clear=1; tree[x].clear=0; } if(tree[x].add) { tree[x<<1].add+=tree[x].add; tree[x<<1|1].add+=tree[x].add; tree[x<<1].sum+=(LL)tree[x].add*sz(x<<1); tree[x<<1|1].sum+=(LL)tree[x].add*sz(x<<1|1); tree[x].add=0; } } void Add(int x) { if(tree[x].l>=L&&tree[x].r<=R) { tree[x].sum+=(LL)sz(x); tree[x].add++; return ; } spread(x); int mid=(tree[x].l+tree[x].r)>>1; if(mid>=L) Add(x<<1); if(mid<R) Add(x<<1|1); update(x); } LL ask(int x) { spread(x); if(tree[x].l>=L&&tree[x].r<=R) return tree[x].sum; int mid=(tree[x].l+tree[x].r)>>1; LL ans=0; if(mid>=L) ans+=ask(x<<1); if(mid<R) ans+=ask(x<<1|1); return ans; } }TR; void solve(int H,int T,int r) { if(H>T) return ; if(l==r) { for(int i=H;i<=T;i++) if(q[i].op==2) ans[q[i].id]=l; return ; } TR.init(); int H1=0,H2=0; int mid=(l+r)>>1; for(int i=H;i<=T;i++) { TR.L=q[i].l; TR.R=q[i].r; if(q[i].op==1) { if(q[i].x>mid) { TR.Add(1); q2[++H2]=q[i]; } else q1[++H1]=q[i]; } else { LL tmp=TR.ask(1); if(tmp<(LL)q[i].x) { q[i].x-=tmp; q1[++H1]=q[i]; } else q2[++H2]=q[i]; } } for(int i=1;i<=H1;i++) q[H+i-1]=q1[i]; for(int i=1;i<=H2;i++) q[H+H1+i-1]=q2[i]; solve(H,H+H1-1,mid); solve(H+H1,T,r); } int main() { scanf("%d%d",&n,&m); for(int i=1;i<=m;i++) q[i].read(),q[i].id=i; TR.build(1,1,n); solve(1,m,2*n+1); for(int i=1;i<=m;i++) if(ans[i]) printf("%dn",ans[i]-n-1); return 0; } (编辑:好传媒网) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |