给出一个长度为 n n n 的序列 { a n } {a_n} {an}，支持操作：
0 p v：使 a p : = a p + v a_p:=a_p+v ap:=ap+v；1 x_0 d：求 max x 0 ⩽ p ⩽ n , d ∣ ( p − x 0 ) { a p } max_{x_0leqslant pleqslant n,dmid(p-x_0)}{a_p} maxx0⩽p⩽n,d∣(p−x0){ap}。
1 ⩽ n , m ⩽ 7 × 1 0 4 1leqslant n,mleqslant7times10^4 1⩽n,m⩽7×104，在任意时刻 ∣ a i ∣ ⩽ 2 31 − 1 |a_i|leqslant2^{31}-1 ∣ai∣⩽231−1， 1 ⩽ x 0 , d ⩽ n 1leqslant x_0,dleqslant n 1⩽x0,d⩽n。
常见 trick 题，我直接对 d d d 阈值分治。
如果 d d d 比阈值大，直接暴力跑。
如果 d d d 比阈值小，也好搞，开阈值个线段树，保存等差数列即可。
注意两边的复杂度不同阶，调调阈值大概会快很多。
#include using namespace std;#define cmin(x, ...) x = min({x, __VA_ARGS__})#define cmax(x, ...) x = max({x, __VA_ARGS__})#define fors(i, l, r, ...) for(int i = (l), i##end = (r), ##__VA_ARGS__; i <= i##end; i++)#define dfors(i, r, l, ...) for(int i = (r), i##end = (l), ##__VA_ARGS__; i >= i##end; i--)const int THRESHOLD = 20;int n, m, a[70100];struct segtree { int mx[280100], _l[70100], _r[70100], ton[70100]; void decl(const int d) { int x = 0; fors(i, 1, d) { for(int j = i; j <= n; j += d) ton[_l[j] = ++x] = j; for(int j = i; j <= n; j += d) _r[j] = x; } } void build(int x, int l, int r) { if(l == r) { mx[x] = a[ton[l]]; return; } int mid = (l+r)/2; build(x*2, l, mid), build(x*2+1, mid+1, r); mx[x] = max(mx[x*2], mx[x*2+1]); } void impl(int p, int v, int x, int l, int r) { if(l == r) { mx[x] += v; return; } int mid = (l+r)/2; if(mid >= p) impl(p, v, x*2, l, mid); else impl(p, v, x*2+1, mid+ 1, r); mx[x] = max(mx[x*2], mx[x*2+1]); } int get(int p, int q, int x, int l, int r) { if(l > q || r < p) return numeric_limits::min(); if(l >= p && r <= q) return mx[x]; int mid = (l+r)/2; return max(get(p, q, x*2, l, mid), get(p, q, x*2+1, mid+1, r)); } void add(int p, int v) { impl(_l[p], v, 1, 1, n); } int operator()(const int x) { return get(_l[x], _r[x], 1, 1, n); }} segs[THRESHOLD+1];signed main() { ios::sync_with_stdio(0), cin.tie(0); cin >> n; fors(i, 1, n) cin >> a[i]; fors(i, 1, THRESHOLD) segs[i].decl(i), segs[i].build(1, 1, n); cin >> m; for(int o, x, d; m--;) { cin >> o >> x >> d; if(o == 0) { a[x] += d; fors(i, 1, THRESHOLD) segs[i].add(x, d); } else { if(d > THRESHOLD) { int ans = numeric_limits::min(); for(int i = x; i <= n; i += d) cmax(ans, a[i]); cout << ans << "n"; } else cout << segs[d](x) << "n"; } } return 0;}