CF1718C Tonya and Burenka-179

Alex_Wei · 2022-08-17 12:07:37 · 题解

CF1718C Tonya and Burenka-179

根据经典结论，在长为 n 的环上从任意位置开始每步跳 k 个位置，路径形成长度为 L = \dfrac n {\gcd(n, k)} 的环，环上每个节点模 \gcd(n, k) 同余。因此对于给定 (s, k)，其贡献即 \gcd(n, k)\sum\limits_{i \equiv s\pmod {\gcd(n, k)}} a_i。

一个朴素的想法是对 n 的所有不等于 n 的约数 d 以及所有 j\in [0, d)，求出 f(j, d) = d\sum\limits_{i\equiv j\pmod d} a_j。则 \max f 即答案。

因为单点修改时需要对所有 d 修改 f(p\bmod d, d)，所以时间复杂度 \mathcal{O}(nd(n)\log n)，无法通过。

但我们注意到，若当前环长为 P 且 P 不是质数，那么考虑 P 的某个真因数 D 以及所有长度为 D 的 \dfrac P D 个子环。由于这些子环的贡献的平均值等于当前环的贡献，所以存在长为 D 的子环不劣于当前环。因此只需考虑所有质数环长，即只需对使得 \dfrac n d 为质数的 d 维护 f(j, d)。

时间复杂度 \mathcal{O}(n\omega(n)\log n)，可以通过。

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
constexpr int N = 2e5 + 5;
int n, q, a[N], d[8];
ll f[8][N];
multiset<ll> s;
void solve() {
  s.clear();
  cin >> n >> q;
  for(int i = 1; i <= n; i++) cin >> a[i];
  int tmp = n, cnt = 0;
  for(int i = 2; i <= tmp; i++)
    if(tmp % i == 0) {
      d[++cnt] = n / i;
      while(tmp % i == 0) tmp /= i;
    }
  for(int i = 1; i <= cnt; i++) {
    for(int j = 0; j < d[i]; j++) f[i][j] = 0;
    for(int j = 1; j <= n; j++) f[i][j % d[i]] += a[j];
    for(int j = 0; j < d[i]; j++) s.insert(d[i] * f[i][j]);
  }
  cout << *s.rbegin() << "\n";
  for(int i = 1; i <= q; i++) {
    int p, x;
    cin >> p >> x;
    for(int j = 1; j <= cnt; j++) {
      s.erase(s.find(d[j] * f[j][p % d[j]]));
      f[j][p % d[j]] += x - a[p];
      s.insert(d[j] * f[j][p % d[j]]);
    }
    cout << *s.rbegin() << "\n";
    a[p] = x;
  }
}
int main() {
  ios::sync_with_stdio(0);
  int T = 1;
  cin >> T;
  while(T--) solve();
  return 0;
}