2023牛客多校2

qingmuhe / 2023-07-22 / 原文

H.0 and 1 in BIT

题意

给一串操作字符串，其中包含操作\(A，B\):

\(A\)代表将二进制每一位反转。
\(B\)代表将二进制加\(1\)。且当二进制为全\(1\)时，二进制变为全\(0\)

现在包含多次询问,每次询问给定一个区间（区间需要计算得到），给定一个初始二进制\(x\)，问你二进制在经过操作字符串对应区间操作后的二进制串是什么？

题解思路

让\(len\)代表\(x\)的位数，\(T\)代表\(len\)位数的循环周期，即\(T=2^{len}\)，那么操作\(A,B\)可被表示为公式。\(A\)表示\((T-1-x)\%T\)，\(B\)表示为\((x+1)\%T\)。

至此可以发现，当\(BAB\)中第一个\(B\)贡献为\(1\)时，后一个\(B\)的贡献被\(A\)反转为\(-1\)。根据这个规律可以前缀和统计\(B\)的贡献。

而对于\(A\)，我们发现当经过奇数次\(A\)操作后，值反转一次。反之，则不操作。

源代码

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;
#define int long long
#define rep(i, from, to) for(int i=from;i<=to;++i)
#define nep(i, from, to) for(int i=from;i>=to;--i)
//#define tt(i) cout<<"tt "<<i<<'\n';
#define tt(i)
const int inf = 1e18, N = 2e5 + 7, e9 = 1e9;

int pre[N], pre2[N];
int stat[N];
int lst[N];


void solve() {
    int n, q;
    cin >> n >> q;

    string s;
    cin >> s;
    s = ' ' + s;

    pre[0] = pre2[0] = 0;
    int op = 1;
    rep(i, 1, n) {
        pre2[i] = pre2[i - 1];
        pre[i] = pre[i - 1];

        if (s[i] == 'B') {
            stat[i] = op;
            pre[i] = pre[i - 1] + op;
        } else {
            pre2[i] = pre2[i - 1] + 1;
            op = -op;
        }
    }

    if (s[1] == 'B') lst[1] = 1;
    else lst[1] = 0;
    
    rep(i, 2, n) {
        if (s[i] == 'B') lst[i] = i;
        else lst[i] = lst[i - 1];
    }

    int ans = 0;
    while (q--) {
        int l1, r1;
        string x;
        cin >> l1 >> r1 >> x;
        auto l = min((ans ^ l1) % n + 1, (ans ^ r1) % n + 1);
        auto r = max((ans ^ l1) % n + 1, (ans ^ r1) % n + 1);

        int len = x.size();
        assert(l <= n && r <= n);
        int adB = pre[r] - pre[l - 1], rv = (pre2[r] - pre2[l - 1]) % 2;
        if(pre2[l-1]&1) adB=-adB;
        ll T = 1ll << len;
        ll rx = 0, tem = T >> 1;
        for (auto c: x) {
            if (c == '1') {
                rx += tem;
            }
            tem >>= 1ll;
        }

        rx = ((rx + adB) % T + T) % T;
        if (rv) {
            rx = (T - rx - 1ll) % T;
        }
        ans = rx;
        tem = T >> 1ll;
        rep(ji, 1, len) {
            if (rx >= tem) {
                cout << 1;
                rx -= tem;
            } else cout << 0;
            tem >>= 1ll;
        }
        cout << '\n';
    }
}

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int _ = 1;
//    cin >> _;
    while (_--) solve();

    return 0;
}