Vases and flowers

线段树的二分操作

#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<cstdio>
#include<cstdlib>
#include<vector>
#include<map>
#include<set>
#include<stack>
#include<queue>
#define PI atan(1.0)*4
#define e 2.718281828
#define rp(i,s,t) for (i = (s); i <= (t); i++)
#define RP(i,s,t) for (i = (t); i >= (s); i--)
#define ll long long
#define ull unsigned long long
#define mst(a,b) memset(a,b,sizeof(a))
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
using namespace std;
inline int read()                 //逐字读取输入内容
{
  int a=0,b=1;
  char c=getchar();
  while(c<'0'||c>'9')
  {
    if(c=='-')
      b=-1;
    c=getchar();
  }
  while(c>='0'&&c<='9')
  {
    a=(a<<3)+(a<<1)+c-'0';
    c=getchar();
  }
  return a*b;
}
const int N = 5e4+7;
int n;
struct node{
  int l,r;
  int sum;                     //维护空瓶子的数量
  int lazy;                    //标记区间内是否花瓶全为空，全空为1，否则为0，已更新-1
}tree[N<<2];
void pushup(int rt){           //上传
  tree[rt].sum=tree[rt<<1].sum+tree[rt<<1|1].sum;
}
void pushdown(int rt){        //下传
  tree[rt<<1].lazy=tree[rt<<1|1].lazy=tree[rt].lazy;
  tree[rt<<1].sum=tree[rt].lazy*(tree[rt<<1].r-tree[rt<<1].l+1);          //左儿子标记上空花瓶数量
  tree[rt<<1|1].sum=tree[rt].lazy*(tree[rt<<1|1].r-tree[rt<<1|1].l+1);    //右儿子标记上空花瓶数量
  tree[rt].lazy=-1;          //标记已更新
}
void build(int l,int r,int rt){
  tree[rt].l=l,tree[rt].r=r;
  tree[rt].lazy=-1;
  tree[rt].sum=r-l+1;
  if(l==r) return;
  int m=(l+r)>>1;
  build(lson);
  build(rson);
  pushup(rt);
}
void update(int rt,int L,int R,int val){
  if(L<=tree[rt].l&&tree[rt].r<=R){                                      //全覆盖
    tree[rt].lazy=val;
    tree[rt].sum=val*(tree[rt].r-tree[rt].l+1);
    return ;
  }
  if(tree[rt].l==tree[rt].r) return ;                                    //叶节点不用递归
  if(tree[rt].lazy!=-1) pushdown(rt);                                    //更新子节点
  int m=(tree[rt].l+tree[rt].r)>>1;
  if(L<=m) update(rt<<1,L,R,val);
  if(m<R) update(rt<<1|1,L,R,val);
  pushup(rt);               //归来更新父节点
}
int query(int rt,int L,int R){                                          //查找[L,R]区间内的空瓶子个数
  if(tree[rt].l>R||tree[rt].r<L) return 0;                              //越界
  int ans=0;
  if(L<=tree[rt].l&&tree[rt].r<=R) return tree[rt].sum;                 //全覆盖返回区间花瓶内的空花瓶数量
  if(tree[rt].lazy!=-1) pushdown(rt);                                   //更新子节点
  int m=(tree[rt].l+tree[rt].r)>>1;
  if(L<=m) ans+=query(rt<<1,L,R);
  if(m<R) ans+=query(rt<<1|1,L,R);
  pushup(rt);              //归来更新父节点
  return ans;
}
int bin_search(int x,int num){                                           //二分查找第num个空瓶子的位置
int l=x,r=n;
int ans=0,m;
while(l<=r){
  m=(l+r)>>1;
  if(query(1,x,m)>=num){                                                 //关键部分，精髓
    ans=m;                 //标记其实或者结束的空花瓶区间
    r=m-1;
    } 
    else l=m+1;
  }
  return ans;
}
int main(){
  int T=read();            //测试用例的数量
  while(T--){
    n=read();              //花瓶数量
    int m=read();          //操作次数
    build(1,n,1);          //建树
    // printf("%d %d %d\n",tree[1].l,tree[1].r,tree[1].sum);
    while(m--){
      int opt=read(),x=read(),y=read();
      if(opt==1){
        x++;
        if (x < 0) x = 1;
        int cnt=query(1,x,n);                                           //得到[x,n]区间内的空花瓶个数
        // cout<<cnt<<endl;
        if(cnt==0) printf("Can not put any one.\n");                    //没有空瓶的情况
        else{
          int l=bin_search(x,1);                                        //二分得到第一个出现空瓶子的位置
          int r=bin_search(x,min(y,cnt));                               //二分得到符合条件的最后一个出现空瓶子的位置
          // cout<<l<<" "<<r<<endl;
          update(1,l,r,0);                                              //将[l,r]区间内的空瓶子全部插上花
          printf("%d %d\n",l-1,r-1);
        }
      }
      else{
        x++,y++;
        if (x < 0) x = 1;                                               //x和y都不超过操作区间
        if (y > n) y = n;
        printf("%d\n",y-x+1-query(1,x,y));                              //右区间减去左区间再减去空瓶数量
        update(1,x,y,1);                                                //将[l,r]区间内的瓶子都清空
      }
    }
    printf("\n");
  }
  return 0;
}

笔记：瓶子的数量是从零开始，在线段树上操作需要加一，操作花瓶插花或者是减花都用二分查找寻找操作的区间