题解：P11843 [USACO25FEB] The Best Subsequence G

· · 题解

现在询问了区间 [l,r]，要求拿出来长度为 k 的子序列并且字典序最大。

如果 [l,r] 中 1 的个数大于等于 k，那么就可以直接输出答案了，因为这 k 个数都是 1，一定是字典序最大的，所以此时的答案就是 1+2+2^2+\cdots+2^{k-1}=2^k-1。

如果 [l,r] 中 1 的个数小于 k，我们希望让前面的 1 尽可能多（因为要字典序最大嘛），所以考虑找到一个分界点 p，使得 [l,p] 中只能取 1，而 [p+1,r] 中只能全部取走，目的是接纳一些 0。

随着 p 从 l 取到 r，明显 [l,p] 中 1 的个数越来越多，[p+1,r] 中 0 的个数越来越少。所以可以二分最大分界点 p，使得 p 是满足 [l,p] 中 1 的个数加上 [p+1,r] 的长度大于等于 k 的。

所以我们只需要快速维护一段区间内 1 的个数，一段区间的哈希值（就是按照题意哈希）。

我们需要把之前的全部更新拆成若干个块，这些块的个数是 O(M) 量级的。然后每个块中都是 1 或者 0 了。然后对于每个块而言，维护前缀 1 的个数以及前缀的哈希值，这样整块的 1 的个数或者哈希值就好求了。

然后就是一些散块的值，这些的细节比较多，看看代码吧。

#include<bits/stdc++.h>
#define ll long long
using namespace std;
constexpr ll maxn=2e5+5,modd=1e9+7,maxm=5e5+5;
inline ll pw(ll b){
    //快速幂
    ll ret=1,a=2;
    while(b){
        if(b&1)ret=(ret*a)%modd;
        a=(a*a)%modd;
        b>>=1;
    }
    return ret;
}
ll n,m,q,col[maxm],t1[maxm],hsh[maxm],fir,col1;
/*
col: 每个块的yanse
t1：前缀 1 的个数
hsh：前缀的哈希值
*/
map<ll,ll> mp;
vector<ll> vec;
ll bel(ll x){
    //查询一个下标 x 在哪一个块中
    return upper_bound(vec.begin(),vec.end(),x)-vec.begin()-1;
}
ll query1(ll l,ll r){
    ll L=bel(l),R=bel(r);
    if(L==R)return col[L]*(r-l+1);//如果相等就是区间长度
    else return col[L]*(vec[L+1]-l)+//前面的散块
                t1[R-1]-t1[L]+//中间的整块
                col[R]*(r-vec[R]+1);//后边的散块
}
ll query0(ll l,ll r){
    return r-l+1-query1(l,r);
}
ll queryBlock(ll L,ll R){
    //返回一段连续整块的哈希值
    return (hsh[R-1]-hsh[L]*pw(vec[R]-vec[L+1])%modd+modd)%modd;
}
ll queryHash(ll l,ll r){
    //计算 [l,r] 之间的哈希值
    ll L=bel(l),R=bel(r);
    if(L==R)return col[L]*(pw(r-l+1)-1)%modd;//如果在同一个整块中
    else return (queryHash(l,vec[L+1]-1)*pw(r-(vec[L+1]-1))%modd+//前面的散块
                queryBlock(L,R)*pw(r-(vec[R]-1))%modd+//中间的整块
                queryHash(vec[R],r))%modd;//后面的散块
}
ll getpos(ll L,ll R,ll k){
    ll l=L,r=R,md,ret=L,cnt1=query1(L,R);
    //求出最大下标 p，满足 [l,p] 中 1 的个数加上 [p+1,r] 的长度大于等于 k。
    while(l<=r){
        md=(l+r)>>1;
        if(query0(md,R)+cnt1>=k){
            ret=md;
            l=md+1;
        }else{
            r=md-1;
        }
    }
    return ret;
}
int main(){
    //freopen("1.in","r",stdin);
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>m>>q;
    mp[1]=mp[n+1]=2;
    for(int i=1;i<=m;i++){
        ll l,r;
        cin>>l>>r;
        mp[l]^=1;
        mp[r+1]^=1;
    }
    col1=mp[1]&1;
    for(auto i:mp){
        if(i.second){
            col[vec.size()]=((vec.size()&1)^(col1));
            vec.push_back(i.first);
        }
    }
    //对于每一个块求出前缀 1 的个数和前缀哈希值
    for(int i=0;i<vec.size()-1;i++){
        if(i!=0){
            t1[i]=t1[i-1];
            hsh[i]=hsh[i-1]*pw(vec[i+1]-vec[i])%modd;
        }
        if(col[i]){
            t1[i]+=vec[i+1]-vec[i];
            hsh[i]=(hsh[i]+pw(vec[i+1]-vec[i])-1)%modd;
        }
    }
    while(q--){
        ll l,r,k;
        cin>>l>>r>>k;
        if(query1(l,r)>=k){
            //1 的个数大于等于 k
            cout<<(pw(k)-1+modd)%modd<<"\n";
            continue;
        }
        ll id=getpos(l,r,k);//求出分界点
        ll pre1=query1(l,r)-query1(id,r);
        //前面的 1 拼上后边的哈希值
        cout<<((pw(pre1)-1)*pw(r-id+1)%modd+queryHash(id,r)%modd+modd)%modd<<"\n";
    }
    return 0;
}