P9055 题解

· · 题解

P9055 题解

Problem Link

题目大意

定义一个序列的价值为 \mathrm{mex} 不小于 i 的子区间数，f(i) 表示将该序列重排后能得到的最大价值。

给定一个由 0\sim m-1 构成的长度为 n 的序列，保证元素出现次数的极差 \le 1，给定 l,r，求 f(l)\sim f(r)。

数据范围：0\le l\le r\le m\le 10^7，n\le 10^9。

思路分析

考虑 f(m) 怎么求，显然把完整的 0\sim m-1 一段一段地排在一起，那么会剩下一些出现次数为 x+1 的元素，每种还剩一个，显然把这些元素堆在开头，然后把整块的 0\sim m-1 重排使得这些开头的元素是该排列的后缀，容易证明此时所有长度 \ge m 的子区间都合法。

对于任意 f(i)，显然 0\sim i-1 一定按照如上方式排列，而对于其他元素：显然插入位置距离 \ge i 的元素对才是合法的，因此如果一个长度为 i 的段中间有元素插入，一定可以把这些元素移到两边而答案不劣。

此时共有 x-1 个插入位置被夹在若干整块中间和 2 个插入位置在两边（特判 S_i 全部为 1 的情况）。

考虑反面考虑，计算一个元素插入后会有多少个一个端点在该元素上的子区间不合法。

显然每次我们会选一个破坏量最小的位置插入，那么我们先插 2(i-1) 个元素进两边，剩余均摊插入每个位置即可。

时间复杂度 \mathcal O(m)。

代码呈现

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN=1e7+5,MOD=998244353;
int a[MAXN],s[MAXN],f[MAXN];
inline void sub(int &x,int y) { x=(x>=y)?x-y:x+MOD-y; }
inline ll S0(int l,int r) { return 1ll*(r-l+1)*(l+r)/2%MOD; }
inline ll S1(int r,int len) { return S0(r-len+1,r); }
inline ll S2(int l,int len) { return S0(l,l+len-1); }
signed main() {
    ios::sync_with_stdio(false);
    int m,l,r,K,n=0; char ch;
    cin>>m>>l>>r>>K;
    for(int i=0;i<m;++i) cin>>ch,a[i]=K+ch-'0',n+=a[i];
    for(int i=m-1;~i;--i) s[i]=a[i]+s[i+1];
    f[0]=S0(1,n);
    for(int i=1,k=a[0];i<=m;++i) {
        int s0=s[i],s1=n-s[i];
        f[i]=S0(1,n);
        sub(f[i],S1(s1,i-1));
        int c1=min(2*(i-1),s0);
        sub(f[i],S2(i,c1/2));
        sub(f[i],S2(i,(c1+1)/2));
        int c2=s0-c1,q=c2/(k+1),re=c2%(k+1);
        sub(f[i],S2(2*i-1,q)*(k+1-re)%MOD); 
        sub(f[i],S2(2*i-1,q+1)*re%MOD);
        k=min(k,a[i]);
    }
    ll ans=0,pw=1;
    for(int i=0;i<=m;++i) {
        if(l<=i&&i<=r) ans^=pw*f[i]%MOD;
        pw=pw*233%MOD;
    }
    cout<<ans<<"\n";
    return 0;
}