xor xor 题解

· · 题解

本题解是经过验题人优化表述的出题人题解。

考虑一次询问。

如果 [l,r] 中 0,1 的个数均大于等于 k，那么答案一定是 2^k-1。

特判掉这种情况，因为保证了 2k\le r-l+1，那么现在一定是一个数的个数 \ge k，一个 <k。不妨设 0 的个数大于 k，另一种情况是本质相同的。

结论：存在一个最优方案，使得一个子序列全是 0，另一个子序列含有所有 1。设前者为第一个子序列，后者为第二个子序列。证明放到最后。

由于异或的答案就是第二个子序列对应的数值，我们需要尽量让它大。有一个显然的贪心：从高到低如果这一位能取 1 就取 1，如果取了 1 以后剩下的数个数不够无法满足长度限制，就取 0。因此有了一个 \mathcal{O}(nq) 的算法。

观察：开始取 0 以后，一定是取一个 [l,r] 的后缀。也就是说，第二个子序列是以一串 1 加上一段区间的后缀组成的。

因此我们可以二分第一次取零的位置并且判断。对 s 做前缀和，时间复杂度 \mathcal{O}(n+q\log n)。已经可以过了。

还可以继续优化：其实我们可以算出第二个子序列要取多少个 0（可以看成 0 从后往前取），而开始的 0 的位置可以预处理 \mathcal{O}(1) 计算出。时间复杂度 \mathcal{O}(n+q)。

前文所说的结论的证明：若有“更优方案”，由于 1 的数量不能更多，说明更优方案的答案有一个 1 的位置在更前面。而前文所说的方案的答案是一串 1 加上这段区间的一个后缀，原本方案前面的 1 的位置不可能更前，因此更优方案和原本答案的区别在于后面部分 1 的位置更靠前。然而原本方案后面部分是一段后缀，其中的数的位置无法继续往前提，因此这样的“更优方案”不存在，上面的策略得到的答案即为最优方案。

出题人 \mathcal{O}(n+q) std：

#include <bits/stdc++.h>

using namespace std;

using ll = long long;

const int N = 1e6+6;
const ll mod = 1e9+7;

int n,q;
string s;
ll hs[2][N],a1[N];
int p[2][N],wh[2][N],t[2];

ll qy(ll l,ll r,int f){
    return (hs[f][r]-hs[f][l-1]*(a1[r-l+1]+1)%mod+mod)%mod;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin>>n>>q>>s;
    s=" "+s;
    for (int i=1; i<=n; i++){
        hs[0][i]=(hs[0][i-1]*2+s[i]-'0')%mod;
        hs[1][i]=(hs[1][i-1]*2+(s[i]=='0'))%mod;
    }
    a1[1]=1;
    for (int i=2; i<=n; i++){
        a1[i]=((a1[i-1]+1)*2-1)%mod;
        a1[i]=(a1[i]+mod)%mod;
    }
    for (int i=1; i<=n; i++){
        p[1][i]=p[1][i-1]+(s[i]-'0');
        p[0][i]=p[0][i-1]+(s[i]=='0');
        wh[s[i]-'0'][++t[s[i]-'0']]=i;
    }
    while (q--){
        int l,r,k;
        cin>>l>>r>>k;
        if (p[0][r]-p[0][l-1]>=k && p[1][r]-p[1][l-1]>=k){
            cout<<a1[k]<<"\n";
            continue;
        }
        int s=0,b=1;
        if (p[1][r]-p[1][l-1]<k) swap(s,b);
        int ndb=k-(p[s][r]-p[s][l-1]);
        int fr=wh[b][p[b][r]-ndb+1];
        int cs=p[s][fr-1]-p[s][l-1];
        ll ans=(a1[cs]*(a1[k-cs]+1)%mod+qy(fr,r,b))%mod;
        cout<<ans<<"\n";
    }
    return 0;
}

验题人（我）特意测试的较大常数 \mathcal{O}(n+q\log n) 能过代码：

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e6+5,mod=1e9+7;
string ss;bool a[N];
int s[2][N];
int hsh[2][N];
int pw[N];
int num(int l,int r,bool x){
    return (hsh[x][r]-hsh[x][l-1]*(pw[r-l+1]+1)%mod+mod)%mod;
}
signed main(){
    ios::sync_with_stdio(0);cin.tie(0);
    int n,q;cin>>n>>q>>ss;
    for(int i=1;i<=n;i++){
        a[i]=ss[i-1]-'0';
        s[0][i]=s[0][i-1]+1-a[i];
        s[1][i]=s[1][i-1]+a[i];
        hsh[0][i]=(hsh[0][i-1]*2+a[i])%mod;
        hsh[1][i]=(hsh[1][i-1]*2+1-a[i])%mod;
        pw[i]=(pw[i-1]*2+1)%mod;
    }
    while(q--){
        int l,r,k;cin>>l>>r>>k;
        bool m=0;
        if(s[0][r]-s[0][l-1]>=k){
            if(s[1][r]-s[1][l-1]>=k){
                cout<<pw[k]<<"\n";
                continue;
            }else{
                m=1;
            }
        }
        int ll=l,rr=r;
        while(ll<rr){
            int mid=(ll+rr+1)>>1;
            if(s[m][mid-1]-s[m][l-1] + r-mid+1>=k){
                ll=mid;
            }else rr=mid-1;
        }
        cout<<(pw[s[m][ll-1]-s[m][l-1]]*(pw[r-ll+1]+1)%mod + num(ll,r,1-m))%mod<<"\n";
    }
    return 0;
}