题意：维护两个操作，区间推平，求连续 \(0\) 的个数为 \(x\) 的最前位置。
线段树。
因为需要求连续 \(0\) 的个数，所以维护区间左边连续 \(0\) 的最大个数，区间右边连续 \(0\) 的最大个数以及区间连续 \(0\) 的最大个数。
注意修改的时候要看是修改为 \(1\) 还是修改为 \(0\)。
查询的时候如果整个区间连续 \(0\) 的最大个数小于 \(x\) 就操作失败。否则一直往区间连续 \(0\) 的个数大于 \(x\) 的位置跳，优先跳左区间，然后跳中间（左区间的右边和右区间的左边相接），最后跳右区间。
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define ls id << 1
#define rs id << 1 | 1
const int MAXN = 5e5 + 10;
int n,m,x,y,ans;
char op;
struct SegmentTree{int id,l,r,lmx,rmx,sum,tag;}tree[MAXN << 2];
inline void Pushup(int id)
{
tree[id].sum = max(max(tree[ls].sum,tree[rs].sum),tree[ls].rmx + tree[rs].lmx);
if(tree[ls].sum == tree[ls].r - tree[ls].l + 1) tree[id].lmx = tree[ls].sum + tree[rs].lmx;
else tree[id].lmx = tree[ls].lmx;
if(tree[rs].sum == tree[rs].r - tree[rs].l + 1) tree[id].rmx = tree[rs].sum + tree[ls].rmx;
else tree[id].rmx = tree[rs].rmx;
}
inline void Pushdown(int id)
{
if(tree[id].tag == -1) return;
if(tree[id].tag == 1)
{
tree[ls].lmx = tree[ls].rmx = tree[ls].sum = 0;
tree[rs].lmx = tree[rs].rmx = tree[rs].sum = 0;
tree[ls].tag = tree[rs].tag = tree[id].tag,tree[id].tag = -1;
} else
{
tree[ls].lmx = tree[ls].rmx = tree[ls].sum = tree[ls].r - tree[ls].l + 1;
tree[rs].lmx = tree[rs].rmx = tree[rs].sum = tree[rs].r - tree[rs].l + 1;
tree[ls].tag = tree[rs].tag = tree[id].tag,tree[id].tag = -1;
}
}
inline void Build(int id,int l,int r)
{
tree[id].l = l,tree[id].r = r,tree[id].tag = -1;
tree[id].lmx = tree[id].rmx = tree[id].sum = r - l + 1;
if(l == r) return;
int mid = (l + r) >> 1;
Build(ls,l,mid),Build(rs,mid + 1,r);
Pushup(id);
}
inline void Update(int id,int l,int r,int a,int b,int c)
{
if(a <= l && b >= r)
{
if(c == 1) tree[id].sum = tree[id].lmx = tree[id].rmx = 0;
else tree[id].sum = tree[id].lmx = tree[id].rmx = r - l + 1;
tree[id].tag = c;return;
}
Pushdown(id);
int mid = (l + r) >> 1;
if(a <= mid) Update(ls,l,mid,a,b,c);
if(b > mid) Update(rs,mid + 1,r,a,b,c);
Pushup(id);
}
inline int Query(int id,int l,int r,int a,int b,int c)
{
Pushdown(id);
if(l == r) return l;
int mid = (l + r) >> 1;
if(tree[ls].sum >= c) return Query(ls,l,mid,a,b,c);
else if(tree[ls].rmx + tree[rs].lmx >= c) return mid - tree[ls].rmx + 1;
else return Query(rs,mid + 1,r,a,b,c);
}
signed main()
{
cin >> n >> m;
Build(1,1,n);
while(m--)
{
cin >> op;
if(op == 'A')
{
cin >> x;
if(tree[1].sum < x) ans++;
else
{
int pos = Query(1,1,n,1,n,x);
Update(1,1,n,pos,pos + x - 1,1);
}
}
else cin >> x >> y,Update(1,1,n,x,y,0);
}
cout << ans;
return 0;
}