JZTXT

模板

发布时间 2023-09-30 16:02:39作者: Unino

前缀和

s[i] = s[i - 1] + a[i];
s[r] - s[l - 1]

二维前缀和

s[i][j] += s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1]
s[i][j] - s[i - 1][j] - s[i][j - 1] + s[i - 1][j - 1]

差分

d[l]++, d[r + 1]--;

二维差分

d[x1][y1]++, d[x2 + 1][y2 + 1]++;
d[x1][y2 + 1]--, d[x2 + 1][y1]--;

二分

while (l <= r) {
    int mid = (l + r) >> 1;
    if (check(mid)) l = mid + 1;
    else r = mid - 1;
}
cout << l << "\n";

离散化

sort(b + 1, b + 1 + tot);
int m = unique(b + 1, b + 1 + tot) - (b + 1);
for (int i = 1; i <= n; i++) {
    int x = lower_bound(b + 1, b + 1 + m, a[i]) - b;
}

sort(b.begin(), b.end());
b.erase(unique(b.begin(), b.end()), b.end());
for (int i = 1; i <= n; i++) {
    int x = lower_bound(b.begin(), b.end(), a[i]) - b.begin();
}

归并排序

void merge_sort(int l, int r) {
    if (r - l < 1) {
        return;
    }
    
    int mid = (l + r) >> 1;
    merge_sort(l, mid);
    merge_sort(mid + 1, r);
    
    int i = l, j = mid + 1;
    int pos = l;
    while (i <= mid && j <= r) {
        if (a[i] <= a[j]) {
            t[pos++] = a[i], ++i;
        } else {
            t[pos++] = a[j], ++j;
            ans += mid - i + 1; // 求逆序对
        }
    }
    while (i <= mid) {
        t[pos++] = a[i], ++i;
    }
    while (j <= r) {
        t[pos++] = a[j], ++j;
    }
    
    for (int i = l; i <= r; i++) {
        a[i] = t[i];
    }
}

快速幂

int power(int a, int b, int p) {
    int res = 1 % p;
    while (b) {
        if (b & 1) res = res * a % p;
        a = a * a % p, b >>= 1;
    }
    return res % p;
}

ST 表

void init() {
    for (int i = 2; i <= n; i++) {
        Log[i] = Log[i >> 1] + 1;
    }

    for (int j = 1; j <= Log[n]; j++) {
        for (int i = 1; i + (1 << j) - 1 <= n; i++) {
            st[i][j] = max(st[i][j - 1], st[i + (1 << (j - 1))][j - 1]);
        }
    }
}

int RMQ(int l, int r) {
    int k = Log[r - l + 1];
    return max(st[l][k], st[r - (1 << k) + 1][k]);
}