题目描述
有一排按钮，编号为 \(0 \sim n-1\)。现在有两种操作：
-
\(p\) \(l\) \(r\):表示把编号在 \([l,r]\) 范围内的按钮都按下去。
-
\(r\) \(l\) \(r\):表示把编号在 \([l,r]\) 范围内的按钮都提一格。保证这个操作与之前某个按下操作的区间一样，且一次按下只会释放一次。
如下图，是一个有6个按钮的初始情况:
按下 \([0,2]\) 和 \([2,3]\) 的结果:
释放 \([0,2]\) 的结果:
每次操作之后，你需要输出，现在有多少个连续段的按钮是复位的（在初始高度）。
输入格式
第 1 行，两个整数和 \(n\) ，\(m\) 表示按钮个数和操作次数。
接下来 \(m\) 行，每行一个操作。
输出格式
每次操作之后，输出现在有多少个连续段的按钮是复位的（在初始高度）。
数据范围
\(n \leq 10^8 , m \leq 10^5\)
一道 *2500 的题。是一道看起来很难，其实很简单，其实也很难的题ze。
题目要求维护连续段的复位按钮，我们可以把每个按钮初始状态看作 \(0\) ，每次 \(p\) 操作相当于区间加一， \(r\) 操作相当于区间减一，每次操作后求连续 \(0\) 的个数。
嘶~在01序列中维护连续 \(0\) 的个数很简单，但这次权值不只有 \(0\) 和 \(1\) ，有点难办。
注意到题目中有一句话：保证这个操作与之前某个按下操作的区间一样，且一次按下只会释放一次。
这说明什么？序列中一定不会出现负数！换句话说，区间的最小值一定大于等于 \(0\) 。
这样，我们只需要维护区间连续最小值的段数和区间最小值。输出答案时，如果最小值大于 \(0\) ，则答案为 0 ,反之答案则为区间连续最小值的段数。
代码实现
由于 \(n\) 很大，所以需要离线下来离散化。
说着很简单，但考虑到格点什么的，写代码时要考虑很多细节（尤其是边界什么的）。
还好这题不强制在线，不然肯定要 *3000 起步了daze。
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
const int N=1e5+5;
int n,m;
struct ques{
char op;
int l,r;
}Q[N];
int lsh[N<<2],tot;
int lv[N<<4],rv[N<<4],v[N<<4],mn[N<<4],tag[N<<4];
#define mid ((l+r)>>1)
#define ls (p<<1)
#define rs (p<<1|1)
inline void push_up(int p,int l,int r){
if(mn[ls]==mn[rs]){
mn[p]=mn[ls];
v[p]=v[ls]+v[rs];
if(lv[ls]==mid-l+1)lv[p]=lv[ls]+lv[rs];
else lv[p]=lv[ls];
if(rv[rs]==r-mid)rv[p]=rv[rs]+rv[ls];
else rv[p]=rv[rs];
if(rv[ls]>0&&lv[rs]>0)v[p]--;
}
else if(mn[ls]<mn[rs]){
mn[p]=mn[ls];
lv[p]=lv[ls],rv[p]=0;
v[p]=v[ls];
}
else {
mn[p]=mn[rs];
lv[p]=0,rv[p]=rv[rs];
v[p]=v[rs];
}
}
inline void push_down(int p){
if(tag[p]){
tag[ls]+=tag[p],tag[rs]+=tag[p];
mn[ls]+=tag[p],mn[rs]+=tag[p];
tag[p]=0;
}
}
void build(int p,int l,int r){
mn[p]=tag[p]=0;
lv[p]=rv[p]=lsh[r+1]-lsh[l],v[p]=1;
if(l==r)return;
build(ls,l,mid),build(rs,mid+1,r);
}
void update(int p,int l,int r,int L,int R,int x){
if(l>=L&&r<=R)return mn[p]+=x,tag[p]+=x,void();
if(l>R||r<L)return;
push_down(p);
update(ls,l,mid,L,R,x),update(rs,mid+1,r,L,R,x);
push_up(p,l,r);
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cin>>n>>m;
lsh[++tot]=0,lsh[++tot]=n;
for(int i=1;i<=m;i++){
cin>>Q[i].op>>Q[i].l>>Q[i].r;
lsh[++tot]=Q[i].l,lsh[++tot]=Q[i].r+1;
}
sort(lsh+1,lsh+1+tot);
tot=unique(lsh+1,lsh+1+tot)-lsh-1;
build(1,1,tot-1);
for(int i=1;i<=m;i++){
int l=lower_bound(lsh+1,lsh+1+tot,Q[i].l)-lsh;
int r=lower_bound(lsh+1,lsh+1+tot,Q[i].r+1)-lsh-1;
if(Q[i].op=='p')update(1,1,tot-1,l,r,1);
else update(1,1,tot-1,l,r,-1);
if(mn[1]==0)cout<<v[1]<<'\n';
else cout<<0<<'\n';
}
return 0;
}
//iictiw-marisa