QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#40166#2831. Game TheoryDoIdoWA 58ms49264kbC++236.3kb2022-07-16 20:12:152022-07-16 20:12:18

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-07-16 20:12:18]
  • 评测
  • 测评结果：WA
  • 用时：58ms
  • 内存：49264kb
查看
  • [2022-07-16 20:12:15]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

#pragma region Debug
template<typename T>
std::istream& operator>> (std::istream& in, std::vector<T>& v)
{
	for (auto& val : v) {
		in >> val;
	}
	return in;
}
template<typename T>
std::ostream& operator<< (std::ostream& out, const std::vector<T>& v)
{
	for (const auto& val : v) {
		out << val << ' ';
	}
	return out;
}

void debugAll() {  }
template<typename T1, typename... T2>
void debugAll(const T1& first, const T2&... second)
{
	std::cout << first;
	if (sizeof...(second)) {
		std::cout << ", ";
	}
	debugAll(second...);
}
template<typename T1, typename... T2>
void debug(const T1& first, const T2&... second)
{
	std::cout << "[";
	debugAll(first, second...);
	std::cout << "]" << std::endl;
}
template<typename T>
void debug(const std::vector<T>& v) {
	std::cout << '[';
	for (int i = 0; i < v.size(); i++) {
		std::cout << v[i];
		if (i < v.size() - 1) cout << ", ";
	}
	std::cout << ']' << std::endl;
}
#pragma endregion

//#define Debug
#ifdef Debug
#else
#define debug(...)
#endif
#define N (int)(2e5 + 10)
#define MOD (int)(998244353)

struct Node {
	int l, r;
	int cnt0;
	int cnt1;
	ll pre0, pre1;
	ll suf0, suf1;
	bool flag;

	Node() {
		l = 0, r = 0;
		cnt0 = 0, cnt1 = 0;
		pre0 = 0, pre1 = 0;
		suf0 = 0, suf1 = 0;
		flag = false;
	}
	Node(const int val, const int l, const int r)
	{
		this->l = 0;
		this->r = 0;
		cnt0 = 0, cnt1 = 0;
		pre0 = 0, pre1 = 0;
		suf0 = 0, suf1 = 0;
		flag = false;

		this->l = l;
		this->r = r;
		if (val == 0) cnt0 = 1;
		if (val == 1) cnt1 = 1;
	}
	void init(int l, int r, int val = -1)
	{
		pre0 = 0, pre1 = 0;
		suf0 = 0, suf1 = 0;
		flag = false;

		this->l = l;
		this->r = r;
		if (val == 0) cnt0 = 1;
		if (val == 1) cnt1 = 1;
	}
	int len() const
	{
		return r - l + 1;
	}
	void pushup(const Node& A, const Node& B)
	{
		cnt0 = A.cnt0 + B.cnt0;
		cnt1 = A.cnt1 + B.cnt1;
		pre0 = A.pre0 + B.pre0 + (1LL * B.cnt0 * A.len());
		pre1 = A.pre1 + B.pre1 + (1LL * B.cnt1 * A.len());
		suf0 = B.suf0 + A.suf0 + (1LL * A.cnt0 * B.len());
		suf1 = B.suf1 + A.suf1 + (1LL * A.cnt1 * B.len());
		pre0 %= MOD;
		pre1 %= MOD;
		suf0 %= MOD;
		suf1 %= MOD;
	}
};
//void debug(const Node& A)
//{
//	printf("l = %d, r = %d\n", A.l, A.r);
//	printf("cnt0 = %d, cnt1 = %d\n", A.cnt0, A.cnt1);
//	printf("pre0 = %lld, pre1 = %lld\n", A.pre0, A.pre1);
//	printf("suf0 = %lld, suf1 = %lld\n", A.suf0, A.suf1);
//
//}

Node tr[N * 4];

struct SegmentTree {
public:
	const int n;

private:
	inline void __pushup(int u)
	{
		tr[u].pushup(tr[u << 1], tr[u << 1 | 1]);
		//tr[u] = tr[u << 1] + tr[u << 1 | 1];
	}
	inline void __pushdown(int u)
	{
		if (tr[u].flag) {
			__modify(tr[u << 1]);
			__modify(tr[u << 1 | 1]);
			tr[u].flag = false;
		}
	}
	inline void __modify(Node& node)
	{
		node.flag = !node.flag;
		swap(node.cnt0, node.cnt1);
		swap(node.pre0, node.pre1);
		swap(node.suf0, node.suf1);
	}

public:
	inline SegmentTree(const int& n, int* init) : n(n)
	{
		__build(1, 1, n, init);
	}
	inline void __build(int u, int l, int r, int* init)
	{
		if (l == r) {
			tr[u].init(l, r, init[l]);
			return;
		}

		tr[u].init(l, r);
		int mid = (l + r) >> 1;
		__build(u << 1, l, mid, init);
		__build(u << 1 | 1, mid + 1, r, init);
		__pushup(u);
	}
	inline void modify(int u, int l, int r) {
		if (tr[u].l >= l && tr[u].r <= r) {
			__modify(tr[u]);
			return;
		}

		__pushdown(u);
		int mid = (tr[u].l + tr[u].r) >> 1;
		if (l <= mid) modify(u << 1, l, r);
		if (r >= mid + 1) modify(u << 1 | 1, l, r);
		__pushup(u);
	}
	inline void modify(int l, int r) {
		modify(1, l, r);
	}
	inline Node query(int u, int l, int r, int ql, int qr) {
		if (ql > qr) return Node();
		if (l >= ql && r <= qr) {
			return tr[u];
		}

		__pushdown(u);
		int mid = (l + r) >> 1;
		if (qr <= mid) return query(u << 1, l, mid, ql, qr);
		if (ql >= mid + 1) return query(u << 1 | 1, mid + 1, r, ql, qr);

		Node res;
		res.pushup(
			query(u << 1, l, mid, ql, qr),
			query(u << 1 | 1, mid + 1, r, ql, qr)
		);
		return res;
	}
	inline Node query(int l, int r) {
		return query(1, 1, n, l, r);
	}
	/*void debug(int u, int l, int r) {
		if (l == r) {
			return;
		}

		int mid = (l + r) >> 1;
		debug(u << 1, l, mid);
		debug(u << 1 | 1, mid + 1, r);
	}*/
};

int n, q;
char str[N];
int bit[N * 10];

int main()
{
	while (scanf("%d %d", &n, &q) != EOF) {
		scanf("%s", str + 1);
		for (int i = 1; i <= n; i++) {
			bit[i] = str[i] - '0';
		}

		SegmentTree seg(n, bit);
		/*Node t1 = seg.query(1, n);
		debug(t1);
		Node t2 = seg.query(n, n);
		debug(t2);*/

		for (int i = 1; i <= q; i++) {
			int l, r;
			scanf("%d %d", &l, &r);
			seg.modify(l, r);
			//while (true);

			// 总的
			Node t = seg.query(1, n);

			int pos = t.cnt1;
			if (pos == 0) {
				printf("0\n");
				continue;
			}

			Node tk = seg.query(pos, pos);
			bool val = false;
			if (tk.cnt1) val = true;
			Node left = seg.query(1, pos);
			Node right = seg.query(pos + 1, n);

			if (left.cnt1 == t.cnt1) {
				printf("%lld\n", left.cnt1);
				continue;
			}


			ll cnt = left.cnt0 + right.cnt1;
			ll ans = cnt * n % MOD;
			//auto bins1 = [&](int R) {
			//	if (R == 0) return 0;
			//	int l = 1, r = R;
			//	while (l < r) {
			//		int mid = (l + r + 1) >> 1;
			//		Node tmp = seg.query(mid, R);
			//		if (tmp.cnt0) l = mid;
			//		else r = mid - 1;
			//	}
			//	return l;
			//};
			//int left0 = bins1(pos - 1);
			//if (left.cnt0 == 0) left0 = 0;
			////debug(left0);
			//auto bins2 = [&](int L) {
			//	if (L == n + 1) return 0;
			//	int l = L, r = n;
			//	while (l < r) {
			//		int mid = (l + r) >> 1;
			//		Node tmp = seg.query(L, mid);
			//		if (tmp.cnt1) r = mid;
			//		else l = mid + 1;
			//	}
			//	return l;
			//};
			//int right1 = bins2(pos + 1);
			//if (right.cnt1 == 0) right1 = 0;
			//debug(right1);

			debug(ans);
			ans -= left.pre0;
			ans = (ans % MOD + MOD) % MOD;
			ans -= right.suf1;
			ans = (ans % MOD + MOD) % MOD;
			if (ans != 0)
				ans -= (cnt - 1);
			ans = (ans % MOD + MOD) % MOD;
			ans = (ans % MOD + MOD) % MOD;
			printf("%lld\n", ans);
			//cout << ans << endl;
		}
	}
	return 0;
}

/*
3 2
010
1 2
2 3
5 1
00000
1 5
*/
Source code, Language: C++23

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 4ms
memory: 48504kb

input:

3 2
010
1 2
2 3
5 1
00000
1 5

output:

1
3
5

result:

ok 3 lines

Test #2:

score: 0
Accepted
time: 9ms
memory: 47740kb

input:

1 1
0
1 1

output:

1

result:

ok single line: '1'

Test #3:

score: -100
Wrong Answer
time: 58ms
memory: 49264kb

input:

2 2
01
2 2
2 2
2 2
01
1 2
1 2
1 2
1
1 1
1 1
1 2
1
1 1
1 1
2 2
00
1 2
1 2
2 2
11
1 2
1 2
2 2
01
2 2
1 1
2 2
10
2 2
1 2
2 2
01
1 2
1 2
1 2
0
1 1
1 1
2 2
01
1 2
2 2
1 2
0
1 1
1 1
1 2
1
1 1
1 1
2 2
10
1 2
1 1
1 2
0
1 1
1 1
2 2
01
1 2
1 2
2 2
10
1 2
1 1
1 2
0
1 1
1 1
1 2
0
1 1
1 1
1 2
1
1 1
1 1
2 2
10
1 ...

output:

0
3
1
3
1
1
1
1
2
3
2
2
2
2
2
2
2
2
1
2
2
2
1
2
1
1
2
2
1
2
2
2
2
2
1
2
1
2
1
1
2
2
2
2
2
2
2
1
2
2
1
2
2
2
2
2
1
2
1
1
2
2
2
1
2
1
2
1
1
1
2
2
2
2
2
2
2
1
2
2
1
2
1
2
1
2
2
2
2
2
2
1
2
2
2
2
1
2
1
1
1
1
1
1
2
2
2
2
1
2
2
2
2
2
2
1
2
2
2
2
2
1
2
2
2
2
2
1
2
2
1
2
1
2
1
2
1
2
2
2
1
2
2
2
2
2
2
1
2
1
...

result:

wrong answer 5th lines differ - expected: '0', found: '1'
English 繁體中文 简体中文

Server Time: 2024-11-30 00:35:44 | OpenSource Project