某島

… : "…アッカリ～ン . .. . " .. .
August 17, 2022

傳送門

A1, n, ai <= 5000.
A2, n <= 1e5, ai <= 1e9,

。。最好就不要看 A1。。。（A1 dp 寫完浪費時間不說，還容易數組開小導致寫錯。。）

3
1 2 3

1 2 3 -> 0 3 3 -> 0 0 0

Problem C. Tonya and Burenka-179

#include<lastweapon/io>
using namespace lastweapon;

const int PMAX = 31623;
VI P; bitset<PMAX> isC;
#define ii (i*P[j])
void sieve(){
FOR(i, 2, PMAX){
if (!isC[i]) P.PB(i);
for (int j=0;j<SZ(P)&&ii<PMAX;++j){
isC[ii]=1; if (!(i%P[j])) break;
}
}
}
#undef ii

const int N = int(2e5) + 9;
int a[N], n, q;

void solve() {
RD(n, q); REP(i, n) RD(a[i]);

VI fac; int x = n; REP(i, SZ(P)) {
int p = P[i]; if (p*p > x) break;
if (x % p) continue;
x /= p; while (x % p == 0) x /= p;
fac.PB(n/p);
}
if (x != 1) fac.PB(n/x);

vector<vector<LL>> s(SZ(fac));
priority_queue<LL> Q, D;

REP(i, SZ(fac)) {
int p = fac[i]; s[i].resize(p);
REP(j, n) s[i][j%p] += a[j];
REP(j, p) Q.push(s[i][j] * p);
}

auto modify = [&](int x, int d) {
REP(i, SZ(fac)) {
int p = fac[i], j = x % p;
D.push(s[i][j] * p); s[i][j] += d;
Q.push(s[i][j] * p);
}
while (!D.empty() && D.top() == Q.top()) {
D.pop(), Q.pop();
}
};

printf("%lld\n", Q.top()); DO(q) {
int p, v; RD(p, v); --p;
modify(p, v-a[p]); a[p] = v;
printf("%lld\n", Q.top());
}
}

int main() {
#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
#endif
sieve(); Rush solve();
}