Question
有 \(n\) 只花瓶，一只花瓶中只能插一朵花，Alice 经常收到很多花并插到花瓶中，她也经常清理花瓶
1 A F表示收到了 \(F\) 朵花，从第 \(A\) 只花瓶开始插，如果花瓶中原来有花，就跳过去插下一只花瓶，如果插到最后的花瓶还没有插完就丢弃，输出插入花瓶的第一个位置和最后一个位置2 A B表示清理从 \(A\) 到 \(B\) 的花瓶，输出清理了几朵花
Solution
一个比较典的线段树二分
用线段树，定义线段树的 "区间" ，表示这个区间已经插了花的花瓶数量
对于 \(2\) 操作，很明显就是一个区间求和 + 区间修改，先查询 \([A,B]\) 的区间和，然后把 \([A,B]\) 都赋为 \(1\)
对于 \(1\) 操作，我们先二分 \([A,n]\) 的第一个 \(0\) 的位置 \(pos1\)，然后二分查找 \([pos1,n]\) 的第 \(F\) 个 \(0\) 的位置 \(pos2\)
这里的二分可以直接二分，用 \(query()\) 来查找 \([L,R]\) 中 \(1\) 的个数，也可以直接在线段树上二分
前者的时间复杂度是 \(O(m \log ^2 n)\) ，后者的时间复杂度是 \(O(m \log \log n)\)
Code
在值域上二分
#include<bits/stdc++.h>
using namespace std;
struct Seg_Tree{
int n;
vector<int> t,tag; // t 表示这个区间内花瓶的插了几个了，如果 tag=1 就表示已经插满了花了，tag=0 表示全部清零
Seg_Tree(int n){this->n=n;t.assign(n<<2,0);tag.assign(n<<2,-1);}
void push_up(int x){t[x]=t[x<<1]+t[x<<1|1];}
void add_tag(int x,int l,int r,int val){
if(val==0)
t[x]=0,tag[x]=0;
if(val==1)
t[x]=(r-l+1),tag[x]=1;
}
void push_down(int x,int l,int r){
if(tag[x]!=-1){
int mid=(l+r)>>1;
add_tag(x<<1,l,mid,tag[x]);
add_tag(x<<1|1,mid+1,r,tag[x]);
tag[x]=-1;
}
}
void update(int x,int l,int r,int ql,int qr,int val){ //给 ql-qr 全部赋值为 val
if(ql<=l&&r<=qr){add_tag(x,l,r,val);return ;}
push_down(x,l,r);
int mid=(l+r)>>1;
if(ql<=mid) update(x<<1,l,mid,ql,qr,val);
if(qr>mid) update(x<<1|1,mid+1,r,ql,qr,val);
push_up(x);
}
int query(int x,int l,int r,int ql,int qr){ //询问 ql-qr 一共有多少个 1
if(ql<=l&&r<=qr) return t[x];
push_down(x,l,r);
int mid=(l+r)>>1,ret=0;
if(ql<=mid) ret+=query(x<<1,l,mid,ql,qr);
if(qr>mid) ret+=query(x<<1|1,mid+1,r,ql,qr);
return ret;
}
int find(int ql,int qr,int k) { //寻找 ql-qr 第 k 个 0 的位置
if(ql>qr) return -1;
if(ql==qr) return qr;
int mid=(ql+qr)>>1;
int tmp_sum=query(1,1,n,ql,mid);
if((mid-ql+1)-tmp_sum>=k)
return find(ql,mid,k);
else
return find(mid+1,qr,(k-((mid-ql+1)-tmp_sum)));
}
};
void solve(){
int n,m;scanf("%d%d",&n,&m);
Seg_Tree T(n);
while(m--){
int op,A,B;scanf("%d%d%d",&op,&A,&B);
if(op==1){
A++;
int tmp_sum=T.query(1,1,n,A,n);
if(tmp_sum==(n-A+1)) {printf("Can not put any one.\n");continue;}
if((n-A+1)-tmp_sum < B) B=(n-A+1)-tmp_sum;
int pos1=T.find(A,n,1);
int pos2=T.find(pos1,n,B);
if(pos2==-1) pos2=n;
printf("%d %d\n",pos1-1,pos2-1);
T.update(1,1,n,pos1,pos2,1);
}
else{
A++;B++;
printf("%d\n",T.query(1,1,n,A,B));
T.update(1,1,n,A,B,0);
}
}
printf("\n");
}
int main(){
freopen("4614.in","r",stdin);
freopen("4614.out","w",stdout);
int T;scanf("%d",&T);
while(T--) solve();
return 0;
}
在线段树上二分
#include<bits/stdc++.h>
using namespace std;
struct Seg_Tree{
int n;
vector<int> t,tag; // t 表示这个区间内花瓶的插了几个了，如果 tag=1 就表示已经插满了花了，tag=0 表示全部清零
Seg_Tree(int n){this->n=n;t.assign(n<<2,0);tag.assign(n<<2,-1);}
void push_up(int x){t[x]=t[x<<1]+t[x<<1|1];}
void add_tag(int x,int l,int r,int val){
if(val==0)
t[x]=0,tag[x]=0;
if(val==1)
t[x]=(r-l+1),tag[x]=1;
}
void push_down(int x,int l,int r){
if(tag[x]!=-1){
int mid=(l+r)>>1;
add_tag(x<<1,l,mid,tag[x]);
add_tag(x<<1|1,mid+1,r,tag[x]);
tag[x]=-1;
}
}
void update(int x,int l,int r,int ql,int qr,int val){ //给 ql-qr 全部赋值为 val
if(ql<=l&&r<=qr){add_tag(x,l,r,val);return ;}
push_down(x,l,r);
int mid=(l+r)>>1;
if(ql<=mid) update(x<<1,l,mid,ql,qr,val);
if(qr>mid) update(x<<1|1,mid+1,r,ql,qr,val);
push_up(x);
}
int query(int x,int l,int r,int ql,int qr){ //询问 ql-qr 一共有多少个 1
if(ql<=l&&r<=qr) return t[x];
push_down(x,l,r);
int mid=(l+r)>>1,ret=0;
if(ql<=mid) ret+=query(x<<1,l,mid,ql,qr);
if(qr>mid) ret+=query(x<<1|1,mid+1,r,ql,qr);
return ret;
}
int find(int x,int l,int r,int ql,int qr,int k) { //寻找 ql-qr 第 k 个 0 的位置
if(l==r) return l;
push_down(x,l,r);
int mid=(l+r)>>1;
if(ql>mid) return find(x<<1|1,mid+1,r,ql,qr,k); //如果查询区间不包括左区间，之间查询右区间
int left_sum=query(x<<1,l,mid,ql,mid); // 左区间 1 的个数
if(k <= mid-ql+1-left_sum)
return find(x<<1,l,mid,ql,mid,k); // 在左边
else
return find(x<<1|1,mid+1,r,mid+1,qr,k-(mid-ql+1-left_sum)); //在右边
}
};
void solve(){
int n,m;scanf("%d%d",&n,&m);
Seg_Tree T(n);
while(m--){
int op,A,B;scanf("%d%d%d",&op,&A,&B);
if(op==1){
A++;
int tmp_sum=T.query(1,1,n,A,n);
if(tmp_sum==(n-A+1)) {printf("Can not put any one.\n");continue;}
if((n-A+1)-tmp_sum < B) B=(n-A+1)-tmp_sum;
int pos1=T.find(1,1,n,A,n,1);
int pos2=T.find(1,1,n,pos1,n,B);
if(pos2==-1) pos2=n;
printf("%d %d\n",pos1-1,pos2-1);
T.update(1,1,n,pos1,pos2,1);
}
else{
A++;B++;
printf("%d\n",T.query(1,1,n,A,B));
T.update(1,1,n,A,B,0);
}
}
printf("\n");
}
int main(){
// freopen("4614.in","r",stdin);
// freopen("46140.out","w",stdout);
int T;scanf("%d",&T);
while(T--) solve();
return 0;
}