前缀和
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]);
}
标签:sort,end,int,res,mid,merge,模板
From: https://www.cnblogs.com/unino/p/template.html