「bzoj - 3922」Karin的弹幕

给出一个长度为 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;
}