2024“钉耙编程”中国大学生算法设计超级联赛(4)

序列更新

给定两个长度为 $n$ 的序列：

$$a_0,a_1,\cdots,a_{n-1}$$

和

$$b_0,b_1,\cdots,b_{n-1}$$

需要依次执行 $q$ 次操作。每次操作给出一个整数 $k$，按下标关系维护序列更新。

输入

第一行包含一个正整数 $T$，表示测试数据组数，满足 $1 \le T \le 2$。

每组数据第一行包含两个正整数 $n,q$，分别表示序列长度和操作次数，满足 $1 \le n,q \le 250000$。

第二行包含 $n$ 个正整数 $a_0,a_1,\cdots,a_{n-1}$，满足 $1 \le a_i \le 10^9$。

第三行包含 $n$ 个正整数 $b_0,b_1,\cdots,b_{n-1}$，满足 $1 \le b_i \le 10^9$。

接下来 $q$ 行，每行包含一个整数 $k$。

分析

按 $k$ 的大小分类处理：

• 当 $k$ 较大时，直接暴力更新。
• 当 $k$ 较小时，预处理对应的余数类，用 $b_i$ 更新 $a_{(i-k) \bmod k}$。

设当前大于阈值 $S$ 的元素数量为 $x$。如果连续若干次操作都没有命中这些元素，其概率可以近似写成 $(1-\frac{x}{n})$ 的幂次，因此期望次数为：

$$\frac{x}{n}\sum_{i\ge 0}(i+1)\left(1-\frac{x}{n}\right)^i \approx \frac{n}{x}$$

令 $p=\frac{x}{n}$，则：

$$ans=p\sum_{i\ge 0}(i+1)(1-p)^i$$

由等比数列求和可得：

$$ans=\frac{1}{p}=\frac{n}{x}$$

在实现上，可以用根号分治平衡两部分复杂度。总复杂度近似为：

$$O\left(nx+\frac{n^2}{x}\right)$$

当 $nx=\frac{n^2}{x}$ 时，取 $x=\sqrt n$ 最优，复杂度约为 $O(n\sqrt n)$。

最优 K 子段

分析

首先二分答案。对于每个候选值 $mid$，在 check 中贪心维护最小值不小于 $mid$ 的最多子段数量。

从左端点开始枚举，通过维护一个前缀集合 set，保证以位置 $i$ 结尾的子段满足：

$$pre_i-set.pre \ge x$$

接着需要估计：对每个 $i$，暴力枚举 set 中满足 $i-set.pos$ 为质数的元素，复杂度是多少。

因为 $1\sim n$ 中质数个数约为 $\frac{n}{\ln n}$，随机命中质数间隔的期望为 $O(\log n)$，所以单次枚举的期望复杂度为 $O(\log n)$。

最终总时间复杂度约为：

$$O(n\log^2 n)$$

序列更新代码

#include
using namespace std;
#define ll long long
#define pb push_back
#define int long long
#define PII pair
#define PI acos(-1)
#define s second
#define f first
#define Bint __int128
#define all(x) x.begin(),x.end()
#define isdigit(x) ((x) >= '0' && (x) n)x-=n;
}
inline void modify(int x,int y){
    fix(x);
    fix(y);
    if(a[x]>=b[y])return ;
    sum+=b[y]-a[x];
    a[x]=b[y];
}
void solve(){
    ca=0,cb=0;
    cin>>n>>q;
    sum=0;
    for(int i=1;i>a[i];
    for(int i=1;i>b[i],c[i]=b[i];
    int s=sqrt(n);
    s=max(s,(int)1);
    sort(c+1,c+1+n);
    for(int i=1;is)B[cb++]=i;
    }
    while(q--){
        int k;cin>>k;
        for(int i=0;is)swap(A[i],A[--ca]);else i++;
        }
        for(int i=0;i>T;
    while(T--){
        solve();
    }
    return 0;
}

最优 K 子段代码

#include
using namespace std;
#define ll long long
#define pb push_back
#define int long long
#define PII pair
#define PI acos(-1)
#define s second
#define f first
#define Bint __int128
#define all(x) x.begin(),x.end()
#define isdigit(x) ((x) >= '0' && (x) b;
void get_primes(int n)
{
    st[1]=1;
    for (int i = 2; i f>=x){
            bool f=0;
            for(auto &[p,pos]:b){
                if(s-p>=x&&!st[i-pos]){
                    f=1;
                    break;
                }
                else if(s-p>n>>k;
    for(int i=1;i>a[i],pre[i]=a[i]+pre[i-1];

    int l=0,r=0;
    for(int i=1;i=0)r+=a[i];
    else l+=a[i];
    while(l>1;
        if(check(mid))l=mid;
        else r=mid-1;
    }
    if(check(l))
    cout>T;
    while(T--){
        solve();
    }
    return 0;
}