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

ELECTRODE_kaf · 2025-03-26 17:24:19 · 题解

若限定区间内 0 和 1 的个数均多于 k 个，则选 k 个 0 和 k 个 1 得到 2^k-1 显然最优。

否则必然是其中一个多于 k 个，另一个不够。贪心得到最优策略为其中一个序列全选足够的那种数字，在另一个序列中尽可能把不够的那种数字放在高位，最终答案中这些位置上就是 1，其他位置为 0。

进一步发现由于选择不够的那种数字时需要跳着选，所以可能造成最终其中一个序列凑不满 k 个数，不然尽可能多选一定更优。所以最优策略应该由两段构成：跳着选不够的那种数字，再选一段后缀。这里存在单调性，故二分后缀的开头，找到最靠右侧的满足全选前面不够的那种数字再选它和它右侧所有数字可以凑足 k 个数的位置。

最终答案的数字也由两部分构成：前半段全为不够的那种数字，后半段是限定区间的一个后缀。其中一个序列应该全为足够的那种数字。

const ll N=1e6+10,mod=1e9+7;
string s;
bool a[N];
ll n,q,L,R,k,ps[2][N],pf[2][N],pow2[N];

ll cut(ll l,ll r,bool x) {
    return (pf[x][r]-pf[x][l-1]*pow2[r-l+1]%mod+mod)%mod;
}

int main() {
    sync_off;
    cin>>n>>q>>s;
    pow2[0]=1;

    rep(i,1,n) {
        a[i]=s[i-1]-'0';
        ps[0][i]=ps[0][i-1]+1-a[i];
        ps[1][i]=ps[1][i-1]+a[i];
        pf[0][i]=(pf[0][i-1]*2+a[i])%mod;
        pf[1][i]=(pf[1][i-1]*2+1-a[i])%mod;
        pow2[i]=pow2[i-1]*2%mod;
    }

    count(q) {
        cin>>L>>R>>k;
        bool st;

        if(ps[0][R]-ps[0][L-1]>=k and ps[1][R]-ps[1][L-1]>=k) {
            cout<<pow2[k]-1<<'\n';
            ctn;
        } else if(ps[0][R]-ps[0][L-1]>=k) st=1;
        else st=0;

//      cout<<"st="<<st<<'\n';
        ll l=L,r=R,ans=L;

        while(l<=r) {
            ll mid=(l+r)/2;

            if(ps[st][mid-1]-ps[st][L-1]+R-mid+1>=k) {
                ans=mid;
                l=mid+1;
            } else r=mid-1;
        }

        cout<<((pow2[ps[st][ans-1]-ps[st][L-1]]-1)*pow2[R-ans+1]%mod+cut(ans,R,1-st))%mod<<'\n';
    }
}