题解 P8055 B Highbit & lowbit

Suzt_ilymtics · 2022-01-21 22:31:45 · 题解

update on 2022/03/16: 感谢 @Clarence_Zhu 指出一处手误的地方。

题面传送w

Solution

Subtask1

模拟。

复杂度 \mathcal O(nq)。

Subtask2

记录位数模拟。

复杂度 \mathcal O(nq)

Subtask3

观察操作 2 的本质，把最高位的 1 由 k 位移到了 k+1 位。

那每次操作一定是把最高位 1 由 k 位移到了 k+r-l+1 位。

所以每次询问的答案为 x - 2^k + 2^{k+r-l+1}。

Subtask5

4 没写

发现如果整个数在二进制位上只有一位是 1 的话两种操作都可以看作将最高位的 1 由 k 位移到 k+1 位。

然后这个和 Subtask3 的答案是相同的。

正解

考虑两个操作的本质，

如果最高位的 1 和最低位的 1 不是同一位（分别设为 R,L）（如果是同一位就是 Subtask5），1 操作就是让两个位置之间减少一个 0，2 操作就是让两个位置之间增加一个 0。

设两个位置之间有 k 个 0，通过 k+1 次 1 操作就能让整个数的二进制位上只有一个 1，剩下的操作就可以划归到 Subtask5。

考虑什么时候出现这种情况？在某个位置 1 操作比 2 操作多 k+1 次时。

设 sum_{0/1,i} 表示对 0 操作和 1 操作做的一个前缀和。

设找到的位置为 x，那么就是要满足下面的式子：

并且这个位置应该是我们遇到的第一个满足这样条件的 x。

发现其中有两项是常量，设 p = k+1 + sum_{0,l-1} - sum_{1,l-1}。

式子变为：

我们可以用值域 vector 存下每个 p 出现的位置，然后每次询问直接 lower_bound 一下找到第一个满足条件的 x。

如果能找到一个合法的 x，那么答案为 2^{R + sum_{1,p} - sum_{1,l-1} + 1 + r - p}。（这个结论手模一下应该就能算出来）

如果找不到的话，分两种情况讨论。

设 s_0 = sum_{0,r} - sum_{0,l-1}, s_1 = sum_{1,r} - sum_{1,l-1}。

如果 s_0 \le k，也就是说最低位的 1 移动后不会超过 R 一开始的位置，又因为 L 和 R 这两个位置之间的差一定不会超过 \log x 位，所以这种情况 1 操作暴跳就行，每次 x+=lowbit(x)，复杂度只有 \log x。对于 2 操作可以和 Subtask3 一样处理。

如果 s_0 > k，说明 L 会移动到 R 一开始的位置，但是永远没有一个时刻 L 会超过 R，也就是说此时整个数中只剩下了这两位有 1，那么直接算出两个 1 在第几位输出答案即可。答案为 2^{R+s_0-k} + 2^{R + s_1}。

然后这题就做完了，复杂度应该是 \mathcal O(q \log V)。

Code

/*
Work by: Suzt_ilymtics
Problem: 不知名屑题
Knowledge: 垃圾算法
Time: O(能过)
*/
#include<bits/stdc++.h>
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<queue>
#define int long long
#define orz cout<<"lkp AK IOI!"<<endl

using namespace std;
const int MAXN = 2e6+5;
const int INF = 1e9+7;
const int mod = 1e9+7;

int n, Q;
int a[MAXN], sum[2][MAXN];
vector<int> b[MAXN];

int read() {
    int s = 0, f = 0;
    char ch = getchar();
    while(!isdigit(ch)) f |= (ch == '-'), ch = getchar();
    while(isdigit(ch)) s = (s << 1) + (s << 3) + ch - '0', ch = getchar();
    return f ? -s : s;
}

int Getl(int x) { for(int i = 0; i <= 40; ++i) if(x & (1ll << i)) return i; }
int Getr(int x) { for(int i = 40; i >= 0; --i) if(x & (1ll << i)) return i; }
int lb(int x) { return x & (-x); }
int Pow(int x, int p) {
    int res = 1;
    while(p) {
        if(p & 1) res = res * x % mod;
        x = x * x % mod, p >>= 1;
    }
    return res;
}

signed main()
{
    n = read(), Q = read();
    for(int i = 1; i <= n; ++i) scanf("%1d", &a[i]);
    for(int i = 1; i <= n; ++i) 
        sum[0][i] = sum[0][i - 1] + (a[i] == 0), sum[1][i] = sum[1][i - 1] + (a[i] == 1);
    int M = 100000;
    for(int i = 1; i <= n; ++i) b[M + sum[0][i] - sum[1][i]].push_back(i); // 用值域 vector 预处理一下位置
    for(int i = -M; i <= M; ++i) b[i + M].push_back(n + 1); // 每个值域都放一个 vector 方便判断有无解（其实我就是忘了 vector 用 lower_bound 找不到一个数是返回什么值）
    for(int i = 1, l, r, x; i <= Q; ++i) {
        l = read(), r = read(), x = read();
        int L = Getl(x), R = Getr(x), k = 0;
        if(L == R) { // Subtask5
            printf("%lld\n", Pow(2, L + r - l + 1));
        } else {
            ++k;
            for(int j = L; j <= R; ++j) if(!(x & (1ll << j))) ++k;
            k = M + k + sum[0][l - 1] - sum[1][l - 1];
            int p = lower_bound(b[k].begin(), b[k].end(), l) - b[k].begin();
            if(b[k][p] > r) {
                int s0 = sum[0][r] - sum[0][l - 1], s1 = sum[1][r] - sum[1][l - 1];
                k = k - M - sum[0][l - 1] + sum[1][l - 1];
                if(s0 < k) { // 无解下的情况 1
                    int ans = Pow(2, R + s1);
                    x -= (1ll << R);
                    while(s0--) x += lb(x);
                    ans = (ans + x) % mod;
                    printf("%lld\n", ans);
                } else { // 无解下的情况 2
                    int ans = (Pow(2, R + s0 - k) + Pow(2, R + s1)) % mod;
                    printf("%lld\n", ans);
                }
            } else { // 有解的情况
                p = b[k][p];
                printf("%lld\n", Pow(2, R + sum[1][p] - sum[1][l - 1] + 1 + (r - p)));
            }
        }
    }
    return 0;
}