自动搬运

查看原文

来自洛谷，原作者为

	cff_0102 & aqua_qaq | 团子群 185800038 | 如果我死了说明我 AFO 了

搬运于2025-08-24 23:11:47，当前版本为作者最后更新于2025-02-20 21:17:26，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

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

考虑一次询问。

如果 $[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;
}