QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #40169 | #2831. Game Theory | DoIdo | WA | 108ms | 49120kb | C++23 | 6.5kb | 2022-07-16 20:27:24 | 2022-07-16 20:27:25 |
Judging History
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;
}
void clear()
{
l = 0, r = 0;
cnt0 = 0;
cnt1 = 0;
pre0 = 0, pre1 = 0;
suf0 = 0, suf1 = 0;
flag = false;
}
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);
}*/
void clear()
{
for (int i = 1; i <= n * 4; i++) {
tr[i].clear();
}
}
};
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 - 1);
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;
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(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;
if (val) ans += pos - left0;
else ans += right1 - pos;
printf("%lld\n", ans);
//cout << ans << endl;
}
seg.clear();
}
return 0;
}
/*
3 2
010
1 2
2 3
5 1
00000
1 5
*/
詳細信息
Test #1:
score: 100
Accepted
time: 2ms
memory: 47676kb
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: 49120kb
input:
1 1 0 1 1
output:
1
result:
ok single line: '1'
Test #3:
score: 0
Accepted
time: 63ms
memory: 47776kb
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 0 1 0 1 2 0 0 2 0 1 2 0 1 3 1 0 1 2 1 0 0 1 3 2 1 0 1 3 3 2 1 0 1 0 0 1 0 1 0 2 2 1 0 1 2 1 1 0 2 0 2 3 1 0 0 1 2 0 0 1 0 1 0 1 1 0 1 2 2 0 0 2 0 1 0 1 1 0 1 0 1 0 0 1 0 1 0 1 2 0 3 0 1 0 0 1 1 0 1 0 1 2 0 2 1 0 0 3 1 2 0 1 3 2 1 0 0 1 2 0 2 0 0 1 0 1 1 0 1 0 1 0 1 0 1 2 1 0 3 1 0 3 0 1 0 1 ...
result:
ok 200000 lines
Test #4:
score: -100
Wrong Answer
time: 108ms
memory: 47416kb
input:
11 20 00010111000 1 6 1 11 5 6 8 11 1 4 3 8 4 11 1 7 5 9 1 4 6 10 5 6 1 7 5 10 1 10 9 11 6 8 1 4 8 11 1 4 10 20 0101000010 3 4 2 2 4 8 4 6 6 7 3 7 3 3 1 5 1 5 6 8 2 2 2 4 2 6 5 7 1 3 2 5 6 8 7 9 5 8 3 10 4 20 1011 2 4 1 4 1 3 2 3 1 1 2 2 1 2 2 4 1 2 3 4 3 4 3 4 1 4 2 2 1 4 1 3 1 1 1 3 1 3 2 2 4 20 1...
output:
22 61 57 35 16 21 56 56 42 36 38 54 46 47 42 34 32 38 51 47 20 21 38 42 40 48 40 37 40 34 23 37 21 24 33 27 25 10 16 37 2 10 5 7 10 9 7 2 0 10 0 10 2 1 9 6 7 4 7 8 4 9 1 7 8 3 5 7 3 7 6 8 6 9 6 7 2 0 5 3 83 140 109 77 125 182 123 109 119 123 159 147 139 131 168 87 112 132 70 62 47 58 26 21 33 67 82 ...
result:
wrong answer 1st lines differ - expected: '16', found: '22'