题目描述

有一排按钮，编号为 \(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