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

序列更新

给定两个长度为n 的序列$ 𝑎_0,𝑎_1,…,𝑎_{𝑛−1}$ 和 $𝑏_0,𝑏_1,…,𝑏_{𝑛−1}$

你需要依次执行q次操作，每次操作将会给出一个整数$k(0≤𝑘<𝑛)$，对于每个$ 𝑖 (0≤𝑖<𝑛)$，你需要将 $𝑎𝑖$ 更新为 $max⁡(𝑎_𝑖,𝑏_{𝑖+𝑘}\ mod\ 𝑛)。$为了证明你确实维护了a序列，请在每次操作之后输出 $\sum_{i=0}^{i<n}a_i $的值。

$Input$

第一行包含一个正整数 $T (1≤𝑇≤2)$，表示测试数据的组数。

每组数据第一行包含两个正整数$ 𝑛,𝑞 (1≤𝑛,𝑞≤250,000)$，分别表示序列的长度以及操作的次数。

第二行包含 $𝑛 $个正整数 $𝑎_0,𝑎_1,…,𝑎_{𝑛−1} (1≤𝑎𝑖≤10^9)$。

第三行包含 $𝑛$ 个正整数 $𝑏0,𝑏1,…,𝑏𝑛−1(1≤𝑏𝑖≤10^9)。$

接下来 𝑞行，每行一个整数 𝑘 (0≤𝑘<𝑛)，依次描述每次操作。

输入数据保证每个 𝑎𝑖,𝑏𝑖 都是在 $[1,10^9]$均匀随机生成得到（样例除外），且每个 k 都是在 $[0,𝑛)$均匀随机生成得到（样例除外）。

$Output$

对于每组数据输出 𝑞 行，其中第 𝑖 行输出一个整数，即在第 𝑖 次操作完毕之后 $\sum_{i=0}^{i<n}a_i$的值。

$Sample Input$

1 5 5 1 5 3 6 8 2 5 4 7 3 3 2 4 1 0

$Sample Output$

29 31 33 35 36

$分析$:

常规考虑基本都是$o(n^2)$无解。唯一指向性的线索就是$a_i$只会单调递增以及$a_i,b_i,k$都是均匀随机生成。

考虑在$b_i$之间设置一个阙值$S$：

当$a_i \le S$,对于每个$k$都依次去用$b_{(i+k)\%n}$尝试更新$a_i$，直到大于$S$。

当$a_i >S$,则存起来，后用$b_i$去更新$a_{(i-k)\%k}$

对于第二种期望次数为设为x次（即有x个数大于S）

对于第一种：即为连续$i$次每个数都不超过$S$的概率为$（1-\frac{x}{n}）$让$a_i>x$的期望次数$\frac{x}{n}\sum_{i>=0}^{无穷次}(i+1)(1- \frac{x}{n})^i\approx\frac{n}{x}$

$证明：$

$设p=\frac{x}{n}$

原式为$ans=p*\sum_{i>=0}^{\infty}(i+1)(i-p)^i= p*(1*(1-p)^0+2*(1-p)^1+3*(1-p)^2....+(i+1)*(1-p)^i)$

上式两边同时$×(1-p)$得：$ans*(1-p)=p*(1*(1-p)^1+2*(1-p)^2+3*(1-p)^3....+(i+1)*(1-p)^{i+1})$

$ans*(1-p)=p*((1-p)^1+(1-p)^2+(1-p)^3....+(1-p)^{i+1})-正无穷小$

正无穷小$\approx0$,原式由等比数列求和化简可得：$ans=\frac{1}{1-p}=\frac{n}{x}+1$,其中1可以忽略不计只需要保证$x>=1$即可

总时间复杂度为$o(n*x+\frac{n^2}{x})$

当$n*x=\frac{n^2}{x}$时即$x=\sqrt{n}$时间复杂度最优为$o(n\sqrt{n})$

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define int long long
#define PII pair<int, int>
#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) <= '9')
#define double long double
#define ULL unsigned long long
const int N = 2e5 + 7, P = 998244353;
const int M = 1e6 + 7, inf = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-6;


int n,q,a[N],b[N],c[N],A[N],B[N],ca,cb,sum;
inline void fix(int&x){
  while(x<=0)x+=n;
  while(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<=n;i++)cin>>a[i];
	for(int i=1;i<=n;i++)cin>>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;i<=n;i++){
		sum+=a[i];
		if(a[i]<=s)A[ca++]=i;
		if(b[i]>s)B[cb++]=i;
	}
	while(q--){
		int k;cin>>k;
		for(int i=0;i<ca;){
			modify(A[i],A[i]+k);
			if(a[A[i]]>s)swap(A[i],A[--ca]);else i++;
		}
		for(int i=0;i<cb;i++){
			modify(B[i]-k,B[i]);
		}
	}
    return ;
}
signed main(){
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    int T=1;
    cin>>T;
    while(T--){
        solve();
    }
    return 0;
}

最优 K 子段

分析：

首先对最小值二分答案。那么在$check$中贪心维护最小值$>=mid$的最多子段数量。

从左端点开始枚举，通过维护一个前缀$set$去保证以位置$i$结尾的子段可以$pre[i]-set.pre>=x。$

那么对于每一个$i$暴力枚举$set$中的元素满足$i-set.pos$为质数的时间复杂度为多少？

因为起初数组元素是均匀分布，那么其$x-前缀$也满足均匀分布，那么其位置$set.pos$也满足均匀分布

因为$1-n$的质数个数$\approx\frac{n}{ln}$,为质数概率$\frac{1}{ln}$，期望为$ln\approx logn$

$所以单次枚举时间复杂度O(logn)，总时间复杂度O(log(n*log+n*log))\approx O(nlog^2)$

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define int long long
#define PII pair<int, int>
#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) <= '9')
#define double long double
#define ULL unsigned long long
const int N = 2e5 + 7, P = 998244353;
const int M = 1e6 + 7, inf = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-6;

int n,a[N],k,pre[N];
int primes[1000009],cnt;
bool st[1000009];
set<PII>b;
void get_primes(int n)
{
	st[1]=1;
    for (int i = 2; i <= n; i ++ )
    {
        if (!st[i]) primes[cnt ++ ] = i;
        for (int j = 0; primes[j] <= n / i; j ++ )
        {
            st[primes[j] * i] = true;
            if (i % primes[j] == 0) break;
        }
    }
}
bool check(int x){
	b.clear();
	b.insert(PII{0,0});
	int res=0;
	for(int i=1;i<=n;i++){
		int s=pre[i];
		if(pre[i]-b.begin()->f>=x){
			bool f=0;
			for(auto &[p,pos]:b){
				if(s-p>=x&&!st[i-pos]){
					f=1;
					break;
				}
				else if(s-p<x)break;
			}
			if(f){
			res++;
			b.clear();
			if(res==k)return 1;
			}
		}
		b.insert(PII{pre[i],i});
	}
	return 0;
}
void solve(){
	cin>>n>>k;
	for(int i=1;i<=n;i++)cin>>a[i],pre[i]=a[i]+pre[i-1];

	int l=0,r=0;
	for(int i=1;i<=n;i++)
	if(a[i]>=0)r+=a[i];
	else l+=a[i];
	while(l<r){
		int mid=l+r+1>>1;
		if(check(mid))l=mid;
		else r=mid-1;
	}
	if(check(l))
	cout<<l<<"\n";
	else cout<<"impossible\n";
}
signed main(){
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    int T=1;
    cin>>T;
    while(T--){
        solve();
    }
    return 0;
}