题解：P11971 「ALFR Round 7」T4 xor xor

· · 题解

题意

给你一段01串，每次询问你一段区间和一个 k，让你选出来两个长为 k 的子序列，把这两个子序列看为两个二进制数，求可能的异或最大值。

题解：

分几种情况。

先看第一种情况，在这种情况下，第一个子序列只选 0，第二个子序列自选 1 一定时优的。

那么此时答案就是 k 个 1 对应的十进制数也就是 2 ^ k - 1。

再看第二种情况。题目中保证 2k \le r - l + 1，而我们有的是一段01串，也就是除了 1 都是 0，既然 1 的个数小于 k，那么 0 的个数必然大于 k。

而我们发现，想要异或最大，就要尽量保证在同一位上第一个子序列和第二个子序列上的数不一样，那我们就要尽量保证能造成贡献的 1 所在的位尽量错开。

而异或是对于每一位的，也就是说在某一位上互换不影响答案。

那我们不妨钦定把 1 全放到第一个子序列，也就是第二个子序列完全由 0 构成，那么最终的答案就是第一个子序列构成的数。

而我们发现，只要第一位是 1，那选的有用位越多坑定比位更少更优，那我们发现，最终答案一定是前面一些 1，后面一段区间。

而 1 全用到在位数一样下必然比舍弃一些 1 不用而用 0 更优，所以我们发现在选择的后面一段区间的更后面没选的一段区间定然全都是 0，而我们如果舍弃前面的一个 0 不选而选这后面的一个 0，就可以让 1 更靠前使答案更优，所以最终选择的一定是前面一些 1，以及一段后缀。

而且这个后缀开头越靠后答案必然更优。

所以我们可以二分查找这个再此之前只选 1，在此之后选后缀的断点，满足能选满 k 个的最靠后断点。

而一段区间的答案我们可以用类似前缀和维护。dd_i 表示 [1, i] 的一段的区间前缀二进制对应的数，那么 [l, r] 这一段的答案就是 dd_r - dd_{l - 1} \times 2 ^ {r - l + 1}。

至于 0 不足 k 的方案数和 1 一样，取反一下即可。

代码

::::info[丑陋至极的代码]{open}

#include<bits/stdc++.h>
#define mod 1000000007
#define int long long
#define maxn 1000005
using namespace std;
inline int read(){
    int x = 0, f = 1;
    char ch = getchar();
    while(ch < '0' || ch > '9'){
        if(ch == '-'){
            f = -1;
        }
        ch = getchar();
    }
    while(ch >= '0' && ch <= '9'){
        x = x * 10 + ch - '0';
        ch = getchar();
    }
    return x * f;
}
void write(int x){
    if(x < 0){
        putchar('-');
        x = -x;
    }
    if(x > 9){
        write(x / 10);
    }
    putchar(x % 10 + '0');
    return;
}
int n, q, l, r, k;
int d[maxn], f[maxn], dd[maxn], ff[maxn], bs[maxn];//d,f,dd,ff,bs分别表示前缀1的个数，前缀0的个数，前缀二进制对应的数，取反后前缀二进制对应的数，以及二的幂次方
string s;
int ksm(int a, int b){//快速幂
    int s = 1;
    while(b){
        if(b & 1){
            s = s * a % mod;
        }
        a = a * a % mod, b >>= 1;
    }
    return s;
}
int get(int x){//能把k个选满的答案
    int ans = ksm(2, x) - 1;
    ans = (ans % mod + mod) % mod;
    return ans;
}
int do_d(int l, int r){//1为正值l-r这一段对应的答案
    int ans = (dd[r] - dd[l - 1] * bs[r - l + 1]) % mod;
    return ans;
} 
int do_f(int l, int r){//0为正值l-r这一段对应的答案
    int ans = (ff[r] - ff[l - 1] * bs[r - l + 1]) % mod;
    return ans;
}
int solve(int x, int l, int r, int op){//表示先选x个1/0，再选l-r这一段
    if(op == 1){
        int ans = ((ksm(2, x) - 1) * ksm(2, r - l + 1) + do_d(l, r)) % mod;
        ans = (ans % mod + mod) % mod;
        return ans;
    }
    else{
        int ans = ((ksm(2, x) - 1) * ksm(2, r - l + 1) + do_f(l, r)) % mod;
        ans = (ans % mod + mod) % mod;
        return ans;
    }
}
void work(){
    l = read(), r = read(), k = read();
    int x = d[r] - d[l - 1], y = f[r] - f[l - 1];
    if(x >= k && y >= k){//1,0都能选满k个
        write(get(k)), puts("");
        return;
    }
    else if(x < k){//1选不满
        int ll = l, rr = r, ans = ll;
        while(ll <= rr){//二分寻找再此之前只选1，在此之后选后缀的断点
            int mid = (ll + rr) >> 1;
            if(r - mid + 1 + d[mid - 1] - d[l - 1] >= k){
                ans = mid;
                ll = mid + 1;
            }
            else{
                rr = mid - 1;
            }
        }
        write(solve(d[ans - 1] - d[l - 1], ans, r, 1)), puts("");
        return;
    }
    else{//0选不满
        int ll = l, rr = r, ans = ll;
        while(ll <= rr){//同上
            int mid = (ll + rr) >> 1;
            if(r - mid + 1 + f[mid - 1] - f[l - 1] >= k){
                ans = mid;
                ll = mid + 1;
            }
            else{
                rr = mid - 1;
            }
        }
        write(solve(f[ans - 1] - f[l - 1], ans, r, 0)), puts("");
        return;
    }
    return;
}
signed main(){
    n = read(), q = read();
    cin >> s;
    s = ' ' + s, bs[0] = 1;
    for(int i = 1; i <= n; i++){
        d[i] = d[i - 1] + (s[i] - '0'), f[i] = f[i - 1] + !(s[i] - '0');//d,f分别表示1,0的个数
        dd[i] = (dd[i - 1] * 2 + (s[i] - '0')) % mod, ff[i] = (ff[i - 1] * 2 + !(s[i] - '0')) % mod, bs[i] = bs[i - 1] * 2 % mod;//求一段对应的值
    }
    while(q--){
        work();
    }
    return 0;
}

::::