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

CJZJC · 2025-03-23 22:52:50 · 题解

大家不要像我一样不打单独的一场 div2。

对于这道题，可以发现他的异或操作差不多是个诈骗，因为当你一个区间里面 0 的个数和 1 的个数都大于 k 的时候答案可以取到 2^k-1。

接着发现题目中保证 2k\leq r-l+1。所以当 0 和 1 中有一个数的个数小于 k 时，另一个数的个数必然大于 k。

继续想可以发现，把个数大于 k 的数取出 k 个排成一个长度为 k 的子序列一定是最优情况，证明比较简单，调整一下即可。且少于 k 个的数全部取出最优。

现在相当于答案为个数少于 k 个的数在子序列中出现的位置。考虑贪心，从高到低为能取就取，这里可以用二分实现。

代码：

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define N 1000010
const int mod=1e9+7;
int n,q,a[N],h[N],bas[N],s[N][2];
int gt0(int l,int r){
    return s[r][0]-s[l-1][0];
}
int gt1(int l,int r){
    return s[r][1]-s[l-1][1];
}
int gth(int l,int r){
    return (h[r]-h[l-1]*bas[r-l+1]%mod+mod)%mod;
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    bas[0]=1;
    for(int i=1;i<=1000000;i++){
        bas[i]=bas[i-1]*2%mod;
    }
    cin>>n>>q;
    for(int i=1;i<=n;i++){
        char c;
        cin>>c;
        if(c=='1'){
            a[i]=1;
        }
        s[i][0]=s[i-1][0];
        s[i][1]=s[i-1][1];
        s[i][a[i]]++;
    }
    for(int i=1;i<=n;i++){
        h[i]=(h[i-1]*2%mod+a[i])%mod;
    }
    while(q--){
        int l,r,k;
        bool fl=0;
        cin>>l>>r>>k;
        if(gt0(l,r)>=k&&gt1(l,r)>=k){
            cout<<(bas[k]-1+mod)%mod<<'\n';
            continue;
        }
        if(gt0(l,r)>=k){
            fl=1;
        }
        int le=l,ri=r,pos;
        while(le<=ri){
            int mid=(le+ri)>>1;
            int tmp=fl?gt1(l,mid):gt0(l,mid);
            if(tmp+r-mid<k){
                ri=mid-1;
            }
            else{
                pos=mid;
                le=mid+1;
            }
        }
        cout<<((bas[fl?gt1(l,pos):gt0(l,pos)]-1+mod)*bas[k-(fl?gt1(l,pos):gt0(l,pos))]%mod+(fl?((pos==r)?0:gth(pos+1,r)):(bas[k-(fl?gt1(l,pos):gt0(l,pos))]-((pos==r)?0:gth(pos+1,r))-1+mod)))%mod<<'\n';
    }
    return 0;
}