AtCoder——第一题

AtCoder Beginner Contest 322 F Vacation Query

题目大意

处理01字符串，给定Q次询问，询问区间内最长连续1的字符个数

题目理解

• 使用线段树维护区间
• 需要使用懒标记下传修改信号
• 线段树要维护7个信息（区间的最长连续1的个数、区间左端点开始连续1的个数、区间左端点开始连续0的个数、区间的连续0的个数、区间右端点开始连续1的个数、区间右端点开始连续0的个数、区间总字符数）
• pushup操作
• pushdown操作

AC代码

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 500010;

struct Node
{
	int l, r;
	int l1, r1, m1, sum, m0, l0, r0; 
	int tag=0; // 懒标记
	// l1:左端点开始连续1的个数，r1:右端点连续1的个数，m1:最长1子串的长度
	// sum:子串字符个数
	// l0:左端点开始连续0的个数，r0:右端点连续0的个数，m0:最长0子串的长度
	
	// 方便query时直接返回，重载了加号
	Node operator+ (const Node &b) const
	{
		Node u;
		u.sum = sum + b.sum;
		u.l1 = l1 + (l1 == sum ? b.l1 : 0);
		u.l0 = l0 + (l0 == sum ? b.l0 : 0);
		u.r1 = b.r1 + (b.r1 == b.sum ? r1 : 0);
		u.r0 = b.r0 + (b.r0 == b.sum ? r0 : 0);
		u.m1 = max(r1 + b.l1, max(m1, b.m1));
		u.m0 = max(r0 + b.l0, max(m0, b.m0));
		return u;
	}
	
} tr[4 * N];
int n, m;
string s;

void pushup(Node &u, Node &left, Node &right)
{
	u.sum = left.sum + right.sum;
	u.l1 = left.l1 + (left.l1 == left.sum ? right.l1 : 0);
	u.l0 = left.l0 + (left.l0 == left.sum ? right.l0 : 0);
	u.r1 = right.r1 + (right.r1 == right.sum ? left.r1 : 0);
	u.r0 = right.r0 + (right.r0 == right.sum ? left.r0 : 0);
	u.m1 = max(left.r1 + right.l1, max(left.m1, right.m1));
	u.m0 = max(left.r0 + right.l0, max(left.m0, right.m0));
}

void pushup(int u)
{
	pushup(tr[u], tr[u << 1], tr[u << 1 | 1]);
}

void push(Node &p)
{
	p.tag = !p.tag;
	swap(p.l0, p.l1);
	swap(p.r0, p.r1);
	swap(p.m0, p.m1);
}

void push_down(int u)
{
	if (tr[u].tag)
	{
		push(tr[u << 1]);
		push(tr[u << 1 | 1]);
		tr[u].tag = 0;
	}
}

void build(int u, int l, int r)
{
	if (l == r) 
	{
		tr[u].l = tr[u].r = l;
		tr[u].l0 = tr[u].r0 = tr[u].m0 = (s[l - 1] == '0');
		tr[u].l1 = tr[u].r1 = tr[u].m1 = (s[l - 1] == '1');
		tr[u].sum = 1;
	}
	else
	{
		tr[u] = {l, r};
		int mid = (l + r) >> 1;
		build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
		pushup(u);
	}
}

void modify(int u, int l, int r)
{
	if (tr[u].l >= l && tr[u].r <= r)
	{
		push(tr[u]);
	}
	else
	{
		push_down(u);
		int mid = (tr[u].l + tr[u].r) >> 1;
		if (l <= mid) modify(u << 1, l, r);
		if (r > mid) modify(u << 1 | 1, l, r);
		pushup(u); 
	}
}

Node query(int u, int l, int r)
{
	if (tr[u].l >= l && tr[u].r <= r)
	{
		return tr[u];
	}
	push_down(u);
	int mid = (tr[u].l + tr[u].r) >> 1;

	if (l <= mid) 
	{
		if (mid >= r) return query(u << 1, l, r);
		return query(u << 1, l, r) + query(u << 1 | 1, l, r);
	}
	return query(u << 1 | 1, l, r);
}

void solve()
{
	cin >> n >> m;
	cin >> s;
	
	build(1, 1, n);
	
	while (m--)
	{
		int op, l, r;
		cin >> op >> l >> r;
		if (op == 1)
		{
			modify(1, l, r);
		}
		else
		{
			cout << query(1, l, r).m1 << '\n';
		}
	}
}

int main()
{
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	int T = 1;
	while (T--)
	{
		solve();
	}
	return 0;
}