线段树10分求调(赏3关注)
查看原帖
线段树10分求调(赏3关注)
936147
Pigsyy楼主2023/8/10 12:11

麻烦巨佬们帮本蒟蒻调一调

#include <bits/stdc++.h>
#define int long long

using namespace std;

const int SIZE = 1e5 + 10;

int N, M;
struct Segment
{
	int l, r;
	int sum, add;
}Tree[4 * SIZE];

void Pushup(int u)
{
	Tree[u].sum = Tree[u << 1].sum + Tree[u << 1 | 1].sum;
}

void Pushdown(int u)
{
	if (Tree[u].add)
	{
		Tree[u << 1].add = !Tree[u].add;
		Tree[u << 1].sum = Tree[u << 1].r - Tree[u << 1].l + 1 - Tree[u << 1].sum;
		Tree[u << 1 | 1].add = !Tree[u].add;
		Tree[u << 1 | 1].sum = Tree[u << 1 | 1].r - Tree[u << 1 | 1].l + 1 - Tree[u << 1 | 1].sum;
		Tree[u].add = 0;
	}
}

void Build(int u, int l, int r)
{
	if (l == r)
		Tree[u] = {l, r, 0, 0};
	else
	{
		Tree[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 (Tree[u].l >= l && Tree[u].r <= r)
	{
		Tree[u].sum = Tree[u].r - Tree[u].l + 1 - Tree[u].sum;
		Tree[u].add = !Tree[u].add;
	}
	else
	{
		Pushdown(u);
		int mid = Tree[u].l + Tree[u].r >> 1;
		if (mid >= l) Modify(u << 1, l, r);
		if (mid < r) Modify(u << 1 | 1, l, r);
		Pushup(u);
	}
}

int Query(int u, int l, int r)
{
	if (Tree[u].l >= l && Tree[u].r <= r)
		return Tree[u].sum;

	Pushdown(u);
	int mid = Tree[u].l + Tree[u].r >> 1, sum = 0;
	if (mid >= l) sum += Query(u << 1, l, r);
	if (mid < r) sum += Query(u << 1 | 1, l, r);

	return sum;
}

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

	cin >> N >> M;

	Build(1, 1, N);

	while (M --)
	{
		int op,  l,  r;
		cin >> op >> l >> r;

		if (l > r) swap(l, r);

		if (op == 0) Modify(1, l, r);
		else cout << Query(1, l, r) << endl;
	}

	return 0;
}
2023/8/10 12:11
加载中...