P2572 线段树求调,码风良好
  • 板块学术版
  • 楼主fengziyi
  • 当前回复1
  • 已保存回复1
  • 发布时间2023/8/21 10:27
  • 上次更新2023/11/3 02:18:31
查看原帖
P2572 线段树求调,码风良好
540226
fengziyi楼主2023/8/21 10:27

无法通过样例,看不出来啥问题。
昨天已经看了一天了,救救孩子吧

代码使用了 C++ 11 function 理解为多个函数即可。

#include <bits/stdc++.h>

#define i64 long long
#define endl '\n'
#define qwq puts("fzy qwq ~");

using namespace std;

const int N = 1e5 + 10;

struct Node
{
	int l, r, siz;
	int _0, _1, l0, l1, r0, r1, res0, res1;
	int cvr = -1, rev = 0;
	Node() {}
	Node(int _l, int _r)
	{
		l = _l, r = _r,
		siz = (_r - _l + 1),
		_0 = 0, _1 = 0, 
		l0 = 0, l1 = 0, 
		r0 = 0, r1 = 0, 
		res0 = 0, res1 = 0;
	}
	Node(int _l, int _r, int a, int b, int c, int d, int e, int f, int g, int h)
	{
		l = _l, r = _r, 
		siz = (_r - _l + 1), 
		_0 = a, _1 = b, 
		l0 = c, l1 = d, 
		r0 = e, r1 = f, 
		res0 = g, res1 = h;
	}
};

int n, m;
bool a[N];
Node t[N << 2];

#define ls (p << 1)
#define rs (p << 1 | 1)

inline void pushup(int p)
{
	Node& L = t[ls], R = t[rs];
	t[p] = Node(
		t[p].l, t[p].r,
		L._0 + R._0, 							// _0
		L._1 + R._1,							// _1
		(L._1 ? L.l0 : L.l0 + R.l0),			// l0
		(L._0 ? L.l1 : L.l1 + R.l1),			// l1
		(R._1 ? R.r0 : L.r0 + R.r0),			// r0
		(R._0 ? R.r1 : L.r1 + R.r1),			// r1
		max({ L.res0, R.res0, L.r0 + R.l0 }),	// res0
		max({ L.res1, R.res1, L.r1 + R.l1 })	// res1
	);
}

function<void(int)> spread[3] = {
	[](int p)
	{
		t[p].cvr = 0; t[p].rev = 0;
		t[p] = Node(t[p].l, t[p].r, t[p].siz, 0, t[p].siz, 0, t[p].siz, 0, t[p].siz, 0);
	},
	[](int p)
	{
		t[p].cvr = 1; t[p].rev = 0;
		t[p] = Node(t[p].l, t[p].r, 0, t[p].siz, 0, t[p].siz, 0, t[p].siz, 0, t[p].siz);
	},
	[](int p)
	{
		t[p].rev ^= 1;
		t[p] = Node(t[p].l, t[p].r, t[p]._1, t[p]._0, t[p].l1, t[p].l0, t[p].r1, t[p].r0, t[p].res1, t[p].res0);
	}
};

inline void pushdown(int p)
{
	if (t[p].cvr != -1) spread[t[p].cvr](ls), spread[t[p].cvr](rs);
	if (t[p].rev) spread[2](ls), spread[2](rs);
	t[p].cvr = -1; t[p].rev = 0;
}

inline void build(int p, int l, int r)
{
	t[p].l = l, t[p].r = r;
	t[p].siz = (r - l + 1);
	if (l == r)
	{
		int v = a[l];
		t[p] = Node(t[p].l, t[p].r, v ^ 1, v, v ^ 1, v, v ^ 1, v, v ^ 1, v);
		return;
	}
	int mid = (l + r) >> 1;
	build(ls, l, mid);
	build(rs, mid + 1, r);
	pushup(p);
}

inline void modify(int p, int l, int r, int c)
{
	if (l <= t[p].l && t[p].r <= r)
		{ spread[c](p); return; }
	pushdown(p);
	int mid = (t[p].l + t[p].r) >> 1;
	if (l <= mid) modify(ls, l, r, c);
	if (mid <  r) modify(rs, l, r, c);
	pushup(p);
}

inline Node query(int p, int l, int r)
{
	if (l <= t[p].l && t[p].r <= r)
		return t[p];
	pushdown(p);
	int mid = (t[p].l + t[p].r) >> 1;
	if (r <= mid) return query(ls, l, r);
	if (mid <  l) return query(rs, l, r);
	Node L = query(ls, l, r), R = query(rs, l, r);
	return Node(
		t[p].l, t[p].r,
		L._0 + R._0, 							// _0
		L._1 + R._1,							// _1
		(L._1 ? L.l0 : L.l0 + R.l0),			// l0
		(L._0 ? L.l1 : L.l1 + R.l1),			// l1
		(R._1 ? R.r0 : L.r0 + R.r0),			// r0
		(R._0 ? R.r1 : L.r1 + R.r1),			// r1
		max({ L.res0, R.res0, L.r0 + R.l0 }),	// res0
		max({ L.res1, R.res1, L.r1 + R.l1 })	// res1
	);
}

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	cin >> n >> m;
	for (int i = 1; i <= n; ++i)
		cin >> a[i];

	build(1, 1, n);

	for (int i = 1, opt, l, r; i <= m; ++i)
	{
		cin >> opt >> l >> r; ++l, ++r;
		
		if (opt <= 2)
			modify(1, l, r, opt);
		else if (opt == 3)
			cout << query(1, l, r)._1 << endl;
		else if (opt == 4)
			cout << query(1, l, r).res1 << endl;
	}
	return 0;
}
2023/8/21 10:27
加载中...