题解：P11843 [USACO25FEB] The Best Subsequence G

· · 题解

题意

有一段 0,1 序列，给定一个区间和长度，求区间中所有对应长度的子序列中字典序最大的一个。

思路

首先对应 0,1 串的处理，先离散化，然后异或差分，最后前缀和一下就可以得到对应的每段序列了。

考虑贪心选取子序列，如果 1 的个数大于序列长度，那么全选 1 即可，否则选完所有 1 之后再从后往前挑选一些 0 放进去，这样一定是不劣的。

所以我们可以在区间里二分，取 l\sim mid-1 里的 1 以及 mid\sim r 里的所有数，1 的个数可以提前前缀和预处理。

最后输出答案，前面全为 1 的部分直接快速幂即可，后面的部分可以用类似哈希的方法预处理，然后这题就做完了，但是代码不好写。

代码

有点难调，代码写的很屎（尤其是取模这一块），将就着看吧。

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e5+10,Planetary_system=1e9+7;
int n,m,q,nm;
struct node{
    int l,r,x;
}Q[N],M[N];
bool a[N<<2];
int cnt[N<<2];
int H[N<<2];
int ls[N<<2];
int Pow(int k){
    if(k<63) return (1ll<<k)%Planetary_system;
    int x=Pow(k>>1ll);
    if(k&1ll) return ((x*x%Planetary_system)<<1ll)%Planetary_system;
    return x*x%Planetary_system;
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    // freopen("bestsub.in","r",stdin);
    // freopen("bestsub.out","w",stdout);
    cin>>n>>m>>q;
    for(int i=1;i<=m;i++){
        cin>>M[i].l>>M[i].r;
        ls[++nm]=M[i].l;ls[++nm]=M[i].r+1;
    }
    for(int i=1;i<=q;i++){
        cin>>Q[i].l>>Q[i].r>>Q[i].x;
        ls[++nm]=Q[i].l;ls[++nm]=Q[i].r+1;
    }
    ls[++nm]=n+1;
    ls[++nm]=1;
    sort(ls+1,ls+nm+1);
    nm=unique(ls+1,ls+nm+1)-ls-1;
    for(int i=1;i<=m;i++){
        a[lower_bound(ls+1,ls+nm+1,M[i].l)-ls]^=1;
        a[lower_bound(ls+1,ls+nm+1,M[i].r+1)-ls]^=1;
    }
    for(int i=1;i<=nm;i++){
        a[i]^=a[i-1],cnt[i]=cnt[i-1]+a[i-1]*(ls[i]-ls[i-1]);
        H[i]=((H[i-1]*Pow(ls[i]-ls[i-1])%Planetary_system)+a[i-1]*(Pow(ls[i]-ls[i-1])-1+Planetary_system)%Planetary_system)%Planetary_system;
    }
    for(int i=1,l,r,x;i<=q;i++){
        l=Q[i].l,r=Q[i].r,x=Q[i].x;
        int lsl=lower_bound(ls+1,ls+nm+1,l)-ls;
        int lsr=lower_bound(ls+1,ls+nm+1,r+1)-ls;
        if(cnt[lsr]-cnt[lsl]>=x){
            cout<<(Pow(x)-1+Planetary_system)%Planetary_system<<"\n";
            continue;
        }
        int L=l,R=r,ans;
        while(L<=R){
            int mid=(L+R)>>1;
            int lsmid=upper_bound(ls+1,ls+nm+1,mid)-ls-1;
            if(a[lsmid]*(mid-ls[lsmid])+cnt[lsmid]-cnt[lsl]+(r-mid+1)>=x) ans=mid,L=mid+1;
            else R=mid-1;
        }
        int lsans=upper_bound(ls+1,ls+nm+1,ans)-ls-1;
        cout<<((Pow(a[lsans]*(ans-ls[lsans])+cnt[lsans]-cnt[lsl])-1+Planetary_system)%Planetary_system*Pow(r-ans+1)%Planetary_system
            +(H[lsr]
            -(H[lsans]*Pow(ans-ls[lsans])%Planetary_system+a[lsans]*(Pow(ans-ls[lsans])-1+Planetary_system)%Planetary_system)
            *Pow(r-ans+1)%Planetary_system+Planetary_system)%Planetary_system)%Planetary_system
            <<"\n";
    }
    return 0;
}
/*
*/