整体二分算法

这个算法还是挺抽象的，但不过仔细看了一下代码后就会发现其实并没有那么的难。 思路：

• 每一次赋值、查询、添加、删除都视作一次操作,修改操作=删除后添加新的值。
• 对答案和操作进行二分，二分操作的区间和答案范围
• 二分的主要内容：修改/查询的值在mid左右两侧的结果 Update 在整体二分中，有两个特殊的内容需要注意。

1. struct query(有的大佬喜欢这样叫)，在这个结构体中存放type(本次操作的类型)、x(本次操作最左边的影响下标)、y(最右边的影响下标)、z(本次操作的值，一般为删除/添加的值)、id(如果是查询操作)、now（如果是查询操作，这个值一般代表二分到当前区间的时候还差多少的意思）这几个比较重要的变量。

   struct node{
   int type,x,y,z,id,now;
   //1为插入2为删除3为查询
   }w[N],wl[N],wr[N]; //wl和wr为临时数组，用来存二分时需要向左/右边分的内容
   

2.solve( l , r , L , R ) 这个是二分的核心代码，答案的区间在 L->R ，其中操作区间为 l->r，并且使用树状数组/线段树进行快速区间操作 （有的题可能涉及到二维区间）。难以理解，结合代码 某些题会在L==R的时候可能并不能得到答案，此时需要一些小操作

void solve(int l,int r,int L,int R)
{
  if( l>r ) return;  //当操作区间不合理的时候，就直接退出，结束L->R区间的二分
  if( L==R )  //当L==R的时候，在某些题里面就可以直接得到结果了
  {
    for(int i=l;i<=r;i++)
    {
      if( w[i].type==3 ) ans[w[i].id]=L;  //当这个操作是询问操作的时候，就可以对离线后的答案赋值
    }
    return;
  }
  int mid=L+R>>1;
//二分中值
  for(int i=l;i<=r;i++)
  {
    if( w[i].type==1 and w[i].y<=mid ) add(w[i].x,1);
    //操作类型为添加操作的时候，并且这次操作的值是小于mid的，就对x位置进行了一次贡献
    if( w[i].type==2 and w[i].y<=mid ) add(w[i].x,-1);
    //同理，对x位置进行了一次负贡献（删除操作）
    if( w[i].type==3  )
    //查询操作，查询x到y区间有多少贡献值，也就是小于等于mid的数有多少个
    {
      v[i]=getsum(w[i].y)-getsum(w[i].x-1);
    }
  }
    for(int i=l;i<=r;i++)  //逆操作，作用：对区间赋为0，比memset快
  {
    if( w[i].type==1 and w[i].y<=mid ) add(w[i].x,-1);
    if( w[i].type==2 and w[i].y<=mid ) add(w[i].x,1);
}
  int lt=0,rt=0;
  //应该往左二分的数量和往右二分的数量
  for(int i=l;i<=r;i++)
  {
    if( w[i].type==3 ) //如果这个操作为查询操作的话
    {
      if( w[i].now+v[i]>=w[i].z ) wl[++lt]=w[i];
      //我们要求的比mid大的值的数量大/等于了要求的数量，证明答案应该是要小一些的，应当往左分。
      //后续同理，注意取等的小细节就可以了
      else
      {
        w[i].now+=v[i];
        wr[++rt]=w[i];
      }
    }
    else{
      if( w[i].y<=mid ) wl[++lt]=w[i];
      else wr[++rt]=w[i];
    }
  }
  for(int i=1;i<=lt;i++) w[l+i-1]=wl[i];
  for(int i=1;i<=rt;i++) w[l+lt+i-1]=wr[i];
  solve(l,l+lt-1,L,mid);
  solve(l+lt,r,mid+1,R);
}

# Talk is cheap, show me your code.

#include<bits/stdc++.h>
#define lowbit(x) x&(-x)
using namespace std;
const int inf=1e9+12,N=5e5+12;
int v[N],tr[N],n,ans[N],q,cnt,x,y,z,a[N];
char ch;
struct node{
  int type,x,y,z,id,now;
  //1为插入2为删除3为查询
}w[N],wl[N],wr[N];

void add(int x,int v)
{
  while(x<=n) tr[x]+=v,x+=lowbit(x);
}

int getsum(int x)
{
  int sum=0;
  while(x)
  {
    sum+=tr[x];
    x-=lowbit(x);
  }
  return sum;
}

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( w[i].type==3 ) ans[w[i].id]=L;
    }
    return;
  }
  int mid=L+R>>1;
  for(int i=l;i<=r;i++)
  {
    if( w[i].type==1 and w[i].y<=mid ) add(w[i].x,1);
    if( w[i].type==2 and w[i].y<=mid ) add(w[i].x,-1);
    if( w[i].type==3  )
    {
      v[i]=getsum(w[i].y)-getsum(w[i].x-1);
    }
  }
    for(int i=l;i<=r;i++)
  {
    if( w[i].type==1 and w[i].y<=mid ) add(w[i].x,-1);
    if( w[i].type==2 and w[i].y<=mid ) add(w[i].x,1);
  }
  int lt=0,rt=0;
  for(int i=l;i<=r;i++)
  {
    if( w[i].type==3 )
    {
      if( w[i].now+v[i]>=w[i].z ) wl[++lt]=w[i];
      else
      {
        w[i].now+=v[i];
        wr[++rt]=w[i];
      }
    }
    else{
      if( w[i].y<=mid ) wl[++lt]=w[i];
      else wr[++rt]=w[i];
    }
  }
  for(int i=1;i<=lt;i++) w[l+i-1]=wl[i];
  for(int i=1;i<=rt;i++) w[l+lt+i-1]=wr[i];
  solve(l,l+lt-1,L,mid);
  solve(l+lt,r,mid+1,R);
}

int main(){
  cin>>n>>q;
  for(int i=1;i<=n;i++)
  {
    cin>>a[i];
    w[++cnt]=(node){1,i,a[i],0,0,0};
  }
  int qr=0;
  for(int i=1;i<=q;i++)
  {
    cin>>ch;
    if( ch=='Q' )
    {
      cin>>x>>y>>z;
      w[++cnt]=(node){3,x,y,z,++qr,0};
    }
    else{
      cin>>x>>y;
      w[++cnt]=(node){2,x,a[x],0,0,0};
      a[x]=y;
      w[++cnt]=(node){1,x,a[x],0,0,0};
    }
  }
  solve(1,cnt,0,inf);
  for(int i=1;i<=qr;i++)
  {
    cout<<ans[i]<<e