P3071 [USACO13JAN] Seating G 题解

题意：维护两个操作，区间推平，求连续 \(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;
}