分块

动态单点修改

单点修改 \(O(1)\)，区间查询 \(O(\sqrt{n})\)

• 直接暴力分块

#include <bits/stdc++.h>
using namespace std;
using LL = long long;

const int MAXN = 2e5 + 3, B = 450;

int n, Q;
int a[MAXN];
LL sum[MAXN];

int main(){
    cin >> n;
    for(int i = 1; i <= n; i++){
        cin >> a[i];
        sum[i / B] += 1ll * a[i];
    }
    cin >> Q;
    while(Q--){
        int X, Y;
        string opt;
        cin >> opt >> X >> Y;
        if(opt == "mod") sum[X / B] += Y - a[X], a[X] = Y;
        else{
            LL ANS = 0;
            while(X <= Y){
                if(X % B == 0 && X + B - 1 <= Y) ANS += sum[X / B], X = X + B;
                else ANS += a[X], X++;
            }
            cout << ANS << "\n";
        }
    }
    return 0;
}

单点修改 \(O(\sqrt{n})\)，区间查询 \(O(1)\)

• 给每个块内做前缀和
• 给每个块之间做前缀和
• 单点修改时修改前缀和，每个块内 \(O(\sqrt{n})\)，每个块之间 \(O(\sqrt{n})\)
• 区间查询时直接前缀和

动态区间修改

• 加懒惰标记

#include <bits/stdc++.h>
using namespace std;
using LL = long long;

const int MAXN = 3e5 + 3, B = 550;

int n, Q, lb[MAXN], rb[MAXN];
LL a[MAXN], sum[MAXN], lazy[MAXN], MINb[MAXN];

void pushdown(int b){ // 传递懒惰标记
    sum[b] = 0, MINb[b] = 2e16;
    for(int i = lb[b]; i <= rb[b]; i++) a[i] += lazy[b], sum[b] += a[i], MINb[b] = min(MINb[b], a[i]);
    lazy[b] = 0;
}

int main(){
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin >> n >> Q;
    for(int i = 1; i <= n; i++) lb[i / B] = 2e9;
    for(int i = 1; i <= n; i++){
        lb[i / B] = min(lb[i / B], i), rb[i / B] = max(rb[i / B], i); // 暴力算每个块的左端点、右端点
    }
    while(Q--){
        int X, Y, opt;
        LL k;
        cin >> opt >> X >> Y;
        if(opt == 1){
            cin >> k;
            pushdown(X / B), pushdown(Y / B); // 用懒惰标记，这操作只需要再修改区间的左端点、右端点进行
            int l = X, r = Y;
            while(l <= r){
                if(l % B == 0 && l + B - 1 <= r){
                    int b = l / B;
                    sum[b] += k * (rb[b] - lb[b] + 1);
                    MINb[b] += k, lazy[b] += k,  l = l + B;
                }else a[l] += k, sum[l / B] += k, l++;
            }
            pushdown(X / B), pushdown(Y / B);
        }else{
            LL ANS = 0, MIN = 2e16;
            pushdown(X / B), pushdown(Y / B);
            while(X <= Y){
                if(X % B == 0 && X + B - 1 <= Y) ANS += sum[X / B], MIN = min(MIN, MINb[X / B]), X = X + B;
                else ANS += a[X], MIN = min(MIN, a[X]), X++;
            }
            cout << ANS << " " << MIN << "\n";
        }
    }
    return 0;
}

对拍

• 跑很久都不会有重复

#include <bits/stdc++.h>

using namespace std;

int main(int argc, char *argv[]){
    unsigned long long seed = time(0);
    if(argc > 1){
        seed = seed * 32768 + atoi(argv[1]);
    }
    mt19937 rnd(seed);
    cout << rnd() % 20 << "\n";
    return 0;
}