自动搬运

查看原文

来自洛谷，原作者为

	Suzt_ilymtics 公主与玫瑰，随时待骑士归来 | AFO | SDUer

搬运于2025-08-24 22:35:33，当前版本为作者最后更新于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$，那么就是要满足下面的式子：

$$(sum_{0,x} - sum_{0,l-1}) - (sum_{1,x} - sum_{1,l-1}) = k + 1 $$

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

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

式子变为：

$$sum_{0,x} - sum_{1,x} = p$$

我们可以用值域 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;
}