自动搬运

查看原文

来自洛谷，原作者为

	Po7ed **

搬运于2025-08-24 23:10:44，当前版本为作者最后更新于2025-08-17 15:25:09，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

拜谢 @happy_zero 大神提供的单 log 做法。

先将修改差分处理，形成若干连续段。

考虑答案的形态。由于是给定子串的一个长度为 $k$ 的子序列，且要求字典序最大，考虑一个理想的情况，即子串内 $1$ 的个数大于 $k$，那么答案子序列所有元素均为 $1$。

当 $1$ 不够用的时候，从后往前接受 $0$。也就是说，答案的形态是前半段全是 $1$，后半段是给定子串的一个后缀。

考虑如何找到这个后缀。由于子串内 $1$ 的个数 $c_1$ 已经确定，需要的 $0$ 的个数 $n_0$ 也确定，即 $n_0=k-c_1$。而需要的 $0$ 均由后缀提供，所有后缀中 $0$ 的出现次数有单调性，可以二分。

如果直接二分后缀，需要再二分找到其属于哪个连续段，复杂度达到线性对数平方。

这时候我们直接二分后缀所属连续段，然后就可以 $O(1)$ 确定后缀位置。复杂度线性对数。

::::success[代码]

#include <bits/stdc++.h>

using std::cin;
typedef long long ll;
constexpr int N=2e5+114,mod=1e9+7;
int n,m,q;
std::map<int,int> c; // 端点
std::vector<int> v,s; // 端点、前缀 0 数量
std::vector<ll> p; // 前缀和
int t;

ll qpow(ll x,ll y)
{
	ll r=1;
	for(;y;x=1ll*x*x%mod,y/=2)if(y&1)r=1ll*r*x%mod;
	return r;
}

int main()
{
	cin.tie(nullptr)->sync_with_stdio(false);
	cin>>n>>m>>q;
	c[1]=c[n+1]=2;
	for(int i=1,l,r;i<=m;i++)
	{
		cin>>l>>r;
		c[l]^=1,c[r+1]^=1;
	}
	t=c[1]&1; // 第一块颜色
	for(auto [x,y]:c)if(y)
	{
		v.push_back(x);
	}
	s.resize(v.size()),p.resize(v.size());
	if(t)s[0]=0,p[0]=(qpow(2,v[1]-v[0])+mod-1)%mod;
	else s[0]=v[1]-v[0],p[0]=0;
	for(int i=1,j=t^1;i<v.size()-1;i++,j^=1) // 计算前缀 0 数量和前缀和
	{
		if(j)
		{
			s[i]=s[i-1];
			p[i]=(1ll*(p[i-1]+1)*qpow(2,v[i+1]-v[i])+mod-1)%mod;
		}
		else
		{
			s[i]=s[i-1]+v[i+1]-v[i];
			p[i]=1ll*p[i-1]*qpow(2,v[i+1]-v[i])%mod;
		}
	}
	// 属于哪块
	auto bel=[](int x){return std::upper_bound(v.begin(),v.end(),x)-v.begin()-1;};
	for(int l,r,k;q--;)
	{
		cin>>l>>r>>k,l--;
		int L=bel(l),R=bel(r);
		int lc1=~L?(t^L&1?l-s[L]:v[L+1]-1-s[L]):0; // l 前缀 1 数量
		int rc1=t^R&1?r-s[R]:v[R+1]-1-s[R]; // r 前缀 1 数量
		int c1=rc1-lc1; // [l,r] 1 数量
		int n0=k-c1; // 需要的 0 的数量
		if(n0<=0) // 不需要 0
		{
			printf("%d\n",(qpow(2,k)+mod-1)%mod);
		}
		else
		{
			int ql=std::max(L,0)-1,qr=R,rc0=r-rc1,mid;
			while(ql+1<qr) // 二分分界点在那一块
			{
				mid=(ql+qr)/2;
				(s[mid]>=rc0-n0?qr:ql)=mid;
			}
			//                                 分界点
			int p0=v[qr+1]-1,t0=n0-(rc0-s[qr]),p1=p0-t0;
			int len=r-p1,l1=k-len;
			printf("%d\n",((1ll*(qpow(2,l1)+mod-1)*qpow(2,len)+ // 前面的 1
							1ll*(R?p[R-1]:0)*qpow(2,r-v[R]+1)+ // r 整块前缀和
							(t^R&1?qpow(2,r-v[R]+1)+mod-1:0) // r 散块前缀和
							-1ll*(qr?p[qr-1]*qpow(2,v[qr]-1-r):0) // 整块前缀和
							-1ll*(t^qr&1?qpow(2,p1-v[qr]+1)+mod-1:0)*qpow(2,p1-r) // r 散块前缀和
			)%mod+mod)%mod);
		}
	}
}

::::

以防有人不知道怎么下数据。