石

· · 题解

拜谢 @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);
        }
    }
}

::::

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