P11843 [USACO25FEB] The Best Subsequence G 题解
Satellite_system
·
·
题解
思路分析：
根据题目中说的：
我们知道，字符串 A 的字典序大于长度相等的字符串 B，当且仅当在第一个 A_i\ne B_i 的位置 i 上（如果存在），我们有 A_i>B_i。
发现要最大化字典序，一定是前面一段全为 1，后面接一个所求区间的后缀子串，并且是最短的满足条件的后缀子串。于是考虑二分求分割点，要求前半部分 1 的数量加上后半部分长度达到 k。
最后要按位值输出，类似哈希维护前缀位值和即可。
这里赛时代码，已经打好线段树了才想到前缀和，于是就懒得改直接 $O(q\log n\log 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;
}
```