Best Multiple-Index Sum after One Change
Autumn Tournament (2020)
Submission name: maxs.cpp
Problem summary
For every k from1to n, a rabbit collects positions k,2k,3k,… . Each independent hypothesis changes one array value a[p] by s. Find the maximum rabbit sum for each hypothesis, then output the sum of those maxima. Hypotheses do not accumulate.
Input
n; n values; m; then m pairs p s.
Output
The sum of the m optimal rabbit totals.
Constraints
1≤n≤50000; 1≤m≤500000; |a[i]|≤10^8; 1≤p≤n; |s|≤10^13.
Worked example
Original statement sample.
Input
6 2 -5 3 2 -1 4 2 3 -4 2 3
Output
12
Solution analysis
- First compute base[k]=a[k]+a[2k]+… for every step k. A multiples sieve performs n/1+n/2+…+n/n additions.
- Changing position p affects exactly rabbits whose step divides p. Precompute affected[p], the largest base sum among these divisors, by sending base[k] to every multiple of k. All affected rabbits receive the same increment s, so their best result is affected[p]+s.
- Also precompute unaffected[p]. Sort rabbit indices by decreasing base sum and scan until finding a k that does not divide p. Only divisors of p can be rejected; there are at most2√p of them. Each query then compares these two precomputed alternatives. In the sample, changing a[3] by−4 gives best4; independently changing a[2] by3 gives best8, totaling12.
Why it works
The divisor and nondivisor groups partition all rabbit steps. Within the divisor group every sum changes by the same s, so its maximum is affected[p]+s; all other sums are unchanged. Taking the larger group maximum therefore gives the exact answer independently for every hypothesis.
Watch out. Never apply hypotheses cumulatively. If every rabbit is affected (possible for n=1), omit the nonexistent unaffected option. Rabbit sums and the final accumulated answer need long long. A negative s can make an unaffected rabbit win.
Commented C++17 solution
An independently written complete program with standard headers.
#include<algorithm>
#include<iostream>
#include<limits>
#include<numeric>
#include<vector>
using namespace std;
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin>>n;
vector<long long>values(n+1);
for(int i=1;i<=n;i++){
cin>>values[i];
}
const long long negativeInfinity=numeric_limits<long long>::lowest()/4;
vector<long long>base(n+1,0);
vector<long long>affected(n+1,negativeInfinity);
for(int step=1;step<=n;step++){
for(int position=step;position<=n;position+=step){
base[step]+=values[position];
}
}
for(int step=1;step<=n;step++){
for(int position=step;position<=n;position+=step){
affected[position]=max(affected[position],base[step]);
}
}
vector<int>order(n);
iota(order.begin(),order.end(),1);
sort(order.begin(),order.end(),[&](int a,int b){
return base[a]>base[b];
});
vector<long long>unaffected(n+1,negativeInfinity);
for(int position=1;position<=n;position++){
for(int step:order){
if(position%step!=0){
unaffected[position]=base[step];
break;
}
}
}
int queries;
cin>>queries;
long long answer=0;
while(queries--){
int position;
long long change;
cin>>position>>change;
// The two alternatives cover all rabbits, without changing base[].
answer+=max(affected[position]+change,unaffected[position]);
}
cout<<answer<<'\n';
}