题解：P13274 [NOI2025] 三目运算符

· · 题解

场外奶龙想了 1h 写了 40min（应该不止），给我糖丸了兄弟。

首先发现 s_i 只和 s_{i - 1}, s_{i - 2} 有关，于是考虑 n = 3，发现 110,101 时最后一位会改变。考虑更大的情况，110 的 border 为零看上去似乎互相影响没有那么大，考虑 101 的重复出现，比如 1010101010101，这样第一次就会全部变成 1000000000000，很好处理。

考虑 110，这似乎有点难，比如 110 后面跟着很多个 0，那么最后把它变好需要操作 0 的数目次，再比如 11010101，最后操作也是不断把第一个 0 变成 1。通过不断地手玩，打个暴力，我们发现一个惊天大秘密，最后它会变成全部是 1 的状态，而且似乎第一个 0 会每次不断向右移动一个，直到出去。于是我们大胆猜测，长度为 n 形如 110...... 串的答案其实就是 (n - 2)。这很好证明。

考虑归纳法，对于 n = 3，显然操作一次即可，对于 n > 3，我们只考虑 (n - 1) 次操作那么就会出现 (n - 1) 个 1 最后跟着一个 0。如果 (n+1) 是 1，那么这个 1 会变成一个 0，第 n 个数会变成 1，最后三个仍然是 110。如果第 (n+1) 是 0 那么最后三个就显然是 110。

如果在这个 110 前面增加一段前缀使得它改变了呢？其实不会的，因为开头的 1 变了并不影响这一段第 n 次操作后会最后出现一个 110，中间的 1 则显然不可能改变。

然后你发现这道题找到出现最早的 110 位置和有没有出现过 101 就做完了。线段树即可。

#include <bits/stdc++.h>
#define il inline
#define ll long long
using namespace std;
const int N = 4e5, inf = 8e5;
il int ls(int x) {
    return 2 * x;
}
il int rs(int x) {
    return 2 * x + 1;
}
int p101[N * 4 + 10], p010[N * 4 + 10], p110[N * 4 + 10], p001[N * 4 + 10];//最早出现位置
int pre[N * 4 + 10], suf[N * 4 + 10];//这个节点最开始两个和最后两个（可能只有 1 个要特判）
int tag[N * 4 + 10];

il bool check1(int x, int y, int z) {
    return ((x % 2) * 4 + y == z);
}
il bool check2(int x, int y, int z) {
    return (x * 2 + y / 2 == z);
}
il void push_up(int now, int s, int t) {
    int mid = (s + t) >> 1;
    if(t - s + 1 == 2)
        pre[now] = suf[now] = pre[ls(now)] * 2 + pre[rs(now)];
    else if(t - s + 1 == 3)
        pre[now] = pre[ls(now)], suf[now] = (pre[ls(now)] % 2) * 2 + suf[rs(now)];
    else pre[now] = pre[ls(now)], suf[now] = suf[rs(now)];

    p110[now] = min(p110[ls(now)], p110[rs(now)]);
    p101[now] = min(p101[ls(now)], p101[rs(now)]);
    p001[now] = min(p001[ls(now)], p001[rs(now)]);
    p010[now] = min(p010[ls(now)], p010[rs(now)]);
    if(t - s + 1 >= 4) {
        if(check1(suf[ls(now)], pre[rs(now)], 6)) p110[now] = min(p110[now], mid);
        if(check2(suf[ls(now)], pre[rs(now)], 6)) p110[now] = min(p110[now], mid - 1);
        if(check1(suf[ls(now)], pre[rs(now)], 5)) p101[now] = min(p101[now], mid);
        if(check2(suf[ls(now)], pre[rs(now)], 5)) p101[now] = min(p101[now], mid - 1);
        if(check1(suf[ls(now)], pre[rs(now)], 1)) p001[now] = min(p001[now], mid);
        if(check2(suf[ls(now)], pre[rs(now)], 1)) p001[now] = min(p001[now], mid - 1);
        if(check1(suf[ls(now)], pre[rs(now)], 2)) p010[now] = min(p010[now], mid);
        if(check2(suf[ls(now)], pre[rs(now)], 2)) p010[now] = min(p010[now], mid - 1);
    }
    else if(t - s + 1 == 3) {
        int r = pre[ls(now)] * 2 + suf[rs(now)];
        if(r == 6) p110[now] = min(p110[now], mid - 1);
        if(r == 5) p101[now] = min(p101[now], mid - 1);
        if(r == 1) p001[now] = min(p001[now], mid - 1);
        if(r == 2) p010[now] = min(p010[now], mid - 1);
    }
}
il void push_tag(int now, int s, int t) {
    if(t - s + 1 == 1) pre[now] = 1 - pre[now], suf[now] = 1 - suf[now];
    else pre[now] = 3 - pre[now], suf[now] = 3 - suf[now];

    tag[now] ^= 1;
    swap(p101[now], p010[now]);
    swap(p001[now], p110[now]);
} 
il void push_down(int now, int s, int t) {
    if(tag[now]) {
        int mid = (s + t) >> 1;
        push_tag(ls(now), s, mid);
        push_tag(rs(now), mid + 1, t);
        tag[now] = 0;
    }
}

int a[N + 10], n, m;
void build(int l, int r, int now) {
    tag[now] = 0;
    p101[now] = p110[now] = p010[now] = p001[now] = inf;
    pre[now] = suf[now] = 0;
    if(l == r) {
        pre[now] = suf[now] = a[l];
        return ;
    }
    int mid = (l + r) >> 1;
    build(l, mid, ls(now));
    build(mid + 1, r, rs(now));
    push_up(now, l, r);
}
void upd(int ql, int qr, int s, int t, int now) {
    if(ql <= s && t <= qr) {
        push_tag(now, s, t);
        return ;
    }
    int mid = (s + t) >> 1;
    push_down(now, s, t);
    if(ql <= mid) upd(ql, qr, s, mid, ls(now));
    if(qr > mid) upd(ql, qr, mid + 1, t, rs(now));
    push_up(now, s, t);
}
il int qry() {
    int ans = 0;
    if(p101[1] != inf) ans = 1;
    ans = max(ans, n - p110[1] - 1);
    return ans;
}

void init() {
    cin >> n >> m;
    for(int i = 1; i <= n; i++) {
        char ch; cin >> ch;
        a[i] = ch - '0';
    }
    build(1, n, 1);

    ll ans = 0;
    ans ^= qry();
    for(int i = 1, l, r; i <= m; i++) {
        cin >> l >> r;
        upd(l, r, 1, n, 1);
        ans ^= (1ll * (i + 1) * 1ll * qry());
    }
    cout << ans << '\n';
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    int c, T; cin >> c >> T;
    while(T--) init();
}