序列更新
给定两个长度为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(nlog+nlog))\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;
}