【BZOJ3110】【Zjoi2013】K大数查询

之前用权值线段树套区间线段树水过，现在再练习一下整体二分

原题：
有N个位置，M个操作。操作有两种，每次操作如果是1 a b c的形式表示在第a个位置到第b个位置，每个位置加入一个数c
如果是2 a b c形式，表示询问从第a个位置到第b个位置，第C大的数是多少。

N,M≤50000
对于每个1操作，abs（k)≤10^9

对于每个2操作，保证k≤所询问区间内数的个数的总数

这个数据是经过妹主席强化的，不过用整体二分解决的话没什么区别

整体二分这个东西呢，和cdq分治挺像的，我做得题少，也不好说出他们的区别

这题首先先按时间轴排序，其实并不用排序，输入顺序即可，第k大使用整体二分查找

具体过程呢，就是每次递归有两个范围，x,y表示时间轴，l,r表示数的范围

然后mid=(l+r)>>1，按照时间轴递增顺序，如果插入操作的值>mid就给插入操作的区间都++并分到右边，否则分到左边

查询操作就查询查询操作要查询的范围中的值（也就是这次递归中在查询区间中插入的个数），如果这个值<=查询的k，就什么也不动分到左边，否则k-=查询出的个数并分到右边

最后如果l==r，在x到y区间中的询问答案就是l

因为这里是使用两个栈来进行左右划分，设左边的栈顶为t1，左边的时间轴就被分成x,x+t1-1，右边分成x+t1,y，所以这里在每次递归开始的时候要判断x>y时直接退出

我做这道题的时候出现了一些问题：

栈当然要开全局，栈顶也可以开全局，但是进行左右划分的时候不能用全局的栈顶来划分！因为进行左边的递归，开始右边的递归的时候，范围本来应该是x+t1,y，但是这里的t1在进行左边递归的时候被改变了，这个时候就会发生问题

线段树区间修改要push_up

代码：

 #include<iostream>

 #include<cstdio>

 #include<algorithm>

 #include<cstring>

 #include<cmath>

 #include<vector>

 using namespace std;

 int rd(){int z=,mk=;  char ch=getchar();

     while(ch<''||ch>''){if(ch=='-')mk=-;  ch=getchar();}

     while(ch>=''&&ch<=''){z=(z<<)+(z<<)+ch-'';  ch=getchar();}

     return z*mk;

 }

 const int oo=;

 struct dcd{int x,l,r,v,mk;}a[];

 int n,m;

 int ans[];

 dcd q[][];  int hd[];

 int v[],dt[];

 void pshd(int x,int l,int r){

     int md=(l+r)>>;

     v[x<<]+=dt[x]*(md-l+),v[x<<|]+=dt[x]*(r-md);

     dt[x<<]+=dt[x],dt[x<<|]+=dt[x];

     dt[x]=;

 }

 void mdf(int x,int xx,int yy,int l,int r,int vv){

     if(xx==l && yy==r){  v[x]+=vv*(r-l+),dt[x]+=vv;  return ;}

     pshd(x,xx,yy);  int md=(xx+yy)>>;

     if(l<=md && r>md)  mdf(x<<,xx,md,l,md,vv),mdf(x<<|,md+,yy,md+,r,vv);

     else if(r<=md)  mdf(x<<,xx,md,l,r,vv);

     else  mdf(x<<|,md+,yy,l,r,vv);

     v[x]=v[x<<]+v[x<<|];

 }

 int qr(int x,int xx,int yy,int l,int r){

     if(xx==l && yy==r)  return v[x];

     pshd(x,xx,yy);  int md=(xx+yy)>>;

     if(l<=md && r>md)  return qr(x<<,xx,md,l,md)+qr(x<<|,md+,yy,md+,r);

     else  if(r<=md)  return qr(x<<,xx,md,l,r);

     else  return qr(x<<|,md+,yy,l,r);

 }

 void whlbnr(int x,int y,long long l,long long r){

     if(x>y)  return ;

     if(l==r){

         for(int i=x;i<=y;++i)if(a[i].mk==)  ans[a[i].x]=l;

         return ;

     }

     long long tmp,md=(l+r)>>;

     hd[]=hd[]=;

     for(int i=x;i<=y;++i){

         if(a[i].mk==){

             if(a[i].v>md)  q[++hd[]][]=a[i],mdf(,,n,a[i].l,a[i].r,);

             else  q[++hd[]][]=a[i];

         }

         else{

             if((tmp=qr(,,n,a[i].l,a[i].r))<a[i].v)  a[i].v-=tmp,q[++hd[]][]=a[i];

             else  q[++hd[]][]=a[i];

         }

     }

     for(int i=x;i<=y;++i)if(a[i].mk== && a[i].v>md)  mdf(,,n,a[i].l,a[i].r,-);

     for(int i=;i<hd[];++i)  a[x+i]=q[i+][];

     for(int i=;i<hd[];++i)  a[x+hd[]+i]=q[i+][];

     int t1=hd[];

     whlbnr(x,x+t1-,l,md);

     whlbnr(x+t1,y,md+,r);

     //for(int i=x;i<=y;++i)if(a[i].mk==1 && a[i].v>((md+1+r)>>1))  mdf(1,1,n,a[i].l,a[i].r,1);

     //whlbnr(x,x+hd[0]-1,l,md),whlbnr(x+hd[0],y,md+1,r);

 }

 int main(){//freopen("ddd.in","r",stdin);

     cin>>n>>m;

     for(int i=;i<=m;++i)  a[i].mk=rd(),a[i].l=rd(),a[i].r=rd(),a[i].v=rd()+(a[i].mk==?oo:),a[i].x=i;

     whlbnr(,m,,oo<<);

     //for(int i=1;i<=m;++i)if(a[i].mk==2)  printf("%d ",a[i].v);

     for(int i=;i<=m;++i)if(ans[i])  printf("%d\n",ans[i]-oo);

     return ;

 }

巴特西

【BZOJ3110】【Zjoi2013】K大数查询 - 2

最新文章

热门文章