自动搬运

查看原文

来自洛谷，原作者为

	DaiRuiChen007 白鸟白鸟 不要回头望 你要替我飞去那地方 一去那地方 那是你我共同故乡

搬运于2025-08-24 22:44:58，当前版本为作者最后更新于2023-12-25 21:01:37，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

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$ 的情况）。

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

• 如果插在中间，那么会有 $(2i-2)+r+1$ 个区间不合法，其中 $r$ 是这个位置已经被插入的元素数量。
• 如果插在两边，那么会有 $(i-1)+r+1$ 个区间不合法，其中 $r$ 是这个位置已经被插入的元素数量。

显然每次我们会选一个破坏量最小的位置插入，那么我们先插 $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;
}