专栏文章

P11843 [USACO25FEB] The Best Subsequence G 题解

SSatellite_system
P11843题解参与者 4已保存评论 3

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
3 条
当前快照
1 份
快照标识符
@min4c8ut
此快照首次捕获于
2025/12/01 20:21
3 个月前
此快照最后确认于
2025/12/01 20:21
3 个月前
查看原文

思路分析：

根据题目中说的：
我们知道，字符串 AA 的字典序大于长度相等的字符串 BB，当且仅当在第一个 Ai≠BiA_i\ne B_i 的位置 ii 上（如果存在），我们有 Ai>BiA_i>B_i。
发现要最大化字典序，一定是前面一段全为 11，后面接一个所求区间的后缀子串，并且是最短的满足条件的后缀子串。于是考虑二分求分割点，要求前半部分 11 的数量加上后半部分长度达到 kk。
nn 很大，但是 mm 不大，考虑把序列离散化分成若干段，每段全为 00 或全为 11，容易证明区间数是 mm 级别的，于是 11 的数量就可以前缀和维护出来。
最后要按位值输出，类似哈希维护前缀位值和即可。
这里赛时代码，已经打好线段树了才想到前缀和，于是就懒得改直接 O(qlog⁡nlog⁡m)O(q\log n\log m) 了，用上述做法，以及有效二分点只有序列分段的点，可以优化成 O(qlog⁡m)O(q\log m)。

AC Code：

CPP
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=4e5+10,mod=1e9+7;
int qpow(int x,int y){
	int res=1;
	while(y){
		if(y&1)res=res*x%mod;
		x=x*x%mod,y>>=1;
	}return res;
}
int n,M,m,q,a[N],p[N],tr[N<<2],h[N<<2];
#define mid (l+r>>1)
#define ls (p<<1)
#define rs (ls|1)
void build(int p,int l,int r){
	if(l==r){
		if(l&1)
			tr[p]=a[l+1]-a[l],
			h[p]=(qpow(2,a[l+1]-a[l])-1+mod)%mod;
		return;
	}
	build(ls,l,mid),build(rs,mid+1,r);
	tr[p]=tr[ls]+tr[rs];
	h[p]=h[ls]*qpow(2,a[r+1]-a[mid+1])%mod+h[rs];
	h[p]%=mod;
}
int query1(int p,int l,int r,int L,int R){
	if(L<=l&&r<=R)return tr[p];
	int res=0;
	if(L<=mid)res+=query1(ls,l,mid,L,R);
	if(mid<R)res+=query1(rs,mid+1,r,L,R);
	return res;
}
int query2(int p,int l,int r,int L,int R){
	if(L<=l&&r<=R)return h[p]*qpow(2,a[R+1]-a[r+1])%mod;
	int res=0;
	if(L<=mid)res+=query2(ls,l,mid,L,R);
	if(mid<R)res+=query2(rs,mid+1,r,L,R);
	return res%mod;
}
int qry(int l,int r){
	if(l>r)return 0;
	int L=upper_bound(a,a+m+2,l)-a-1;
	int R=upper_bound(a,a+m+2,r)-a-1;
	int res=0;
	if(L+1<R)res+=query1(1,0,m,L+1,R-1);
	if(L&1)res+=a[L+1]-l;
	if((L^R)&&(R&1))res+=r-a[R]+1;
	return res;
}
int val(int l,int r){
	if(l>r)return 0;
	int L=upper_bound(a,a+m+2,l)-a-1;
	int R=upper_bound(a,a+m+2,r)-a-1;
	int res=0;
	if(L+1<R)res+=query2(1,0,m,L+1,R-1)*qpow(2,r-a[R]+1)%mod;
	if(L&1)res+=qpow(2,r-l-1)-qpow(2,r-a[L+1]-1)+mod;
	if((L^R)&&(R&1))res+=qpow(2,r-a[R]+1)-1+mod;
	return res%mod;
}
#undef mid
#undef ls
#undef rs
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	cin>>n>>M>>q;
	for(int i=1,l,r;i<=M;i++)
		cin>>p[i]>>p[i+M],p[i+M]++;
	sort(p+1,p+2*M+1);
	a[0]=0;
	for(int i=1;i<=2*M;i++){
		int t=1;
		while(p[i]==p[i+1])t++,i++;
		if(t&1)a[++m]=p[i];
	}
	if(a[m]==n+1)m--;
	else a[m+1]=n+1;
	build(1,0,m);
	while(q--){
		int L,R,k;
		cin>>L>>R>>k;
		int l=L,r=R,x=L-1;
		while(l<=r){
			int mid=l+r>>1;
			if(qry(L,mid)+R-mid>=k)
				l=mid+1,x=mid;
			else r=mid-1;
		}
		cout<<(qpow(2,k)-qpow(2,R-x)+val(x+1,R)+mod)%mod<<'\n';
	}
	return 0;
}

评论

共 3 条评论，欢迎与作者交流。

正在加载评论...