【模版】Data-structure
Heartlessly
2018-01-19 21:15:02
## $BinaryIndexTree$
```cpp
struct BinaryIndexTree {
LL ind[maxN];
inline void add(LL x, LL p) { for (; x <= n; x += x & -x) ind[x] += p; }
inline LL query(LL x) { LL res = 0; for (; x; x -= x & -x) res += ind[x]; return res; }
} tr;
```
------------
## $BinaryIndexTree \to sum$
```cpp
struct BinaryIndexTree {
LL ind1[maxN], ind2[maxN];
inline void add(LL x, LL p) { for (int i = x; i <= n; i += i & -i) ind1[i] += p, ind2[i] += x * p; }
inline LL ask(LL x) { LL res = 0; for (int i = x; i; i -= i & -i) res += (x + 1) * ind1[i] - ind2[i]; return res; }
inline void update(LL l, LL r, LL x) { add(l, x), add(r + 1, -x); }
inline LL query(LL l, LL r) { return ask(r) - ask(l - 1); }
} tr;
```
------------
## $ST-table \to max$
```cpp
struct STtable {
int st[32][maxN], lg[maxN];
inline void init() {
lg[0] = -1;
for (int i = 1; i <= n; i++) st[0][i] = a[i], lg[i] = lg[i >> 1] + 1;
for (int i = 1; i <= lg[n] + 1; i++)
for (int j = 1; j + (1 << i) - 1 <= n; j++)
st[i][j] = max(st[i - 1][j], st[i - 1][j + (1 << i - 1)]);
}
inline int query(int l, int r) {
int k = lg[r - l + 1];
return max(st[k][l], st[k][r - (1 << k) + 1]);
}
} rmq;
```
------------
## $ST-table \to min$
```cpp
struct STtable {
int st[32][maxN], lg[maxN];
inline void init() {
lg[0] = -1;
for (int i = 1; i <= n; i++) st[0][i] = a[i], lg[i] = lg[i >> 1] + 1;
for (int i = 1; i <= lg[n] + 1; i++)
for (int j = 1; j + (1 << i) - 1 <= n; j++)
st[i][j] = min(st[i - 1][j], st[i - 1][j + (1 << i - 1)]);
}
inline int query(int l, int r) {
int k = lg[r - l + 1];
return min(st[k][l], st[k][r - (1 << k) + 1]);
}
} rmq;
```
------------
## $SegmentTree \rightarrow sum$
```cpp
struct SegmentTree {
LL seg[maxN << 2], lazy[maxN << 2];
inline LL lson(LL x) { return x << 1; }
inline LL rson(LL x) { return x << 1 | 1; }
inline void pushUp(LL x) { seg[x] = seg[lson(x)] + seg[rson(x)]; }
void build(int x, int l, int r, int a[]) {
if (l == r) { seg[x] = a[l]; return; }
int mid = l + r >> 1;
build(lson(x), l, mid, a), build(rson(x), mid + 1, r, a);
pushUp(x);
}
inline void modify(LL x, LL l, LL r, LL p) { lazy[x] += p, seg[x] += p * (r - l + 1); }
inline void pushDown(LL x, LL l, LL r) {
LL mid = l + r >> 1;
modify(lson(x), l, mid, lazy[x]), modify(rson(x), mid + 1, r, lazy[x]);
lazy[x] = 0;
}
void update(LL ql, LL qr, LL p, LL l = 1, LL r = n, LL x = 1) {
if (ql <= l && qr >= r) { modify(x, l, r, p); return; }
pushDown(x, l, r);
LL mid = l + r >> 1;
if (ql <= mid) update(ql, qr, p, l, mid, lson(x));
if (qr > mid) update(ql, qr, p, mid + 1, r, rson(x));
pushUp(x);
}
LL query(LL ql, LL qr, LL l = 1, LL r = n, LL x = 1) {
if (ql <= l && qr >= r) return seg[x];
pushDown(x, l, r);
LL res = 0, mid = l + r >> 1;
if (ql <= mid) res += query(ql, qr, l, mid, lson(x));
if (qr > mid) res += query(ql, qr, mid + 1, r, rson(x));
return res;
}
} tr;
```
------------
## $SegmentTree \rightarrow max$
```cpp
struct SegmentTree {
LL seg[maxN << 2], lazy[maxN << 2];
inline LL lson(LL x) { return x << 1; }
inline LL rson(LL x) { return x << 1 | 1; }
inline void pushUp(LL x) { seg[x] = max(seg[lson(x)], seg[rson(x)]); }
void build(int x, int l, int r, int a[]) {
if (l == r) { seg[x] = a[l]; return; }
int mid = l + r >> 1;
build(lson(x), l, mid, a), build(rson(x), mid + 1, r, a);
pushUp(x);
}
inline void modify(LL x, LL l, LL r, LL p) { lazy[x] += p, seg[x] += p; }
inline void pushDown(LL x, LL l, LL r) {
LL mid = l + r >> 1;
modify(lson(x), l, mid, lazy[x]), modify(rson(x), mid + 1, r, lazy[x]);
lazy[x] = 0;
}
void update(LL ql, LL qr, LL p, LL l = 1, LL r = n, LL x = 1) {
if (ql <= l && qr >= r) { modify(x, l, r, p); return; }
pushDown(x, l, r);
LL mid = l + r >> 1;
if (ql <= mid) update(ql, qr, p, l, mid, lson(x));
if (qr > mid) update(ql, qr, p, mid + 1, r, rson(x));
pushUp(x);
}
LL query(LL ql, LL qr, LL l = 1, LL r = n, LL x = 1) {
if (ql <= l && qr >= r) return seg[x];
pushDown(x, l, r);
LL res = 0, mid = l + r >> 1;
if (ql <= mid) res = max(res, query(ql, qr, l, mid, lson(x)));
if (qr > mid) res = max(res, query(ql, qr mid + 1, r, rson(x)));
return res;
}
} tr;
```
------------
## $SegmentTree \rightarrow min$
```cpp
struct SegmentTree {
LL seg[maxN << 2], lazy[maxN << 2];
inline LL lson(LL x) { return x << 1; }
inline LL rson(LL x) { return x << 1 | 1; }
inline void pushUp(LL x) { seg[x] = min(seg[lson(x)], seg[rson(x)]); }
void build(int x, int l, int r, int a[]) {
if (l == r) { seg[x] = a[l]; return; }
int mid = l + r >> 1;
build(lson(x), l, mid, a), build(rson(x), mid + 1, r, a);
pushUp(x);
}
inline void modify(LL x, LL l, LL r, LL p) { lazy[x] += p, seg[x] += p; }
inline void pushDown(LL x, LL l, LL r) {
LL mid = l + r >> 1;
modify(lson(x), l, mid, lazy[x]), modify(rson(x), mid + 1, r, lazy[x]);
lazy[x] = 0;
}
void update(LL ql, LL qr, LL p, LL l = 1, LL r = n, LL x = 1) {
if (ql <= l && qr >= r) { modify(x, l, r, p); return; }
pushDown(x, l, r);
LL mid = l + r >> 1;
if (ql <= mid) update(ql, qr, p, l, mid, lson(x));
if (qr > mid) update(ql, qr, p, mid + 1, r, rson(x));
pushUp(x);
}
LL query(LL ql, LL qr, LL l = 1, LL r = n, LL x = 1) {
if (ql <= l && qr >= r) return seg[x];
pushDown(x, l, r);
LL res = 0, mid = l + r >> 1;
if (ql <= mid) res = min(res, query(ql, qr, l, mid, lson(x)));
if (qr > mid) res = min(res, query(ql, qr, mid + 1, r, rson(x)));
return res;
}
} tr;
```
------------
## $ChairmanTree \to Kth-lower$
```cpp
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
template < class T > inline void read(T &x) {
x = 0;
char c = getchar();
bool f = 0;
for (; !isdigit(c); c = getchar()) f ^= c == '-';
for (; isdigit(c); c = getchar()) x = (x << 3) + (x << 1) + (c ^ 48);
x = f ? -x : x;
}
const int maxN = 5e5 + 10;
int n, m, len, l, r, k, a[maxN], b[maxN];
struct ChairmanTree {
int cnt, root[maxN], lson[maxN << 5], rson[maxN << 5], sum[maxN << 5];
inline int build(int l, int r) {
int now = ++cnt, mid = l + r >> 1;
if (l != r) lson[now] = build(l, mid), rson[now] = build(mid + 1, r);
return now;
}
inline int update(int pre, int l, int r, int x) {
int now = ++cnt, mid = l + r >> 1;
lson[now] = lson[pre], rson[now] = rson[pre], sum[now] = sum[pre] + 1;
if (l != r)
if (x <= mid) lson[now] = update(lson[pre], l, mid, x);
else rson[now] = update(rson[pre], mid + 1, r, x);
return now;
}
inline void init() {
root[0] = build(1, len);
for (int i = 1; i <= n; i++) {
int tmp = lower_bound(b + 1, b + len + 1, a[i]) - b;
root[i] = update(root[i - 1], 1, len, tmp);
}
}
inline int query(int ql, int qr, int l, int r, int k) {
if (l == r) return b[l];
int x = sum[lson[qr]] - sum[lson[ql]], mid = l + r >> 1;
if (k <= x) return query(lson[ql], lson[qr], l, mid, k);
else return query(rson[ql], rson[qr], mid + 1, r, k - x);
}
inline int kth(int l, int r, int k) { return query(root[l - 1], root[r], 1, len, k); }
} tr;
int main() {
read(n), read(m);
for (int i = 1; i <= n; i++) read(a[i]), b[i] = a[i];
sort(b + 1, b + n + 1), len = unique(b + 1, b + n + 1) - b - 1;
tr.init();
for (int i = 1; i <= m; i++) {
read(l), read(r), read(k);
printf("%d\n", tr.kth(l, r, k));
}
return 0;
}
```
------------
## $ChairmanTree \to Kth-upper$
```cpp
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
template < class T > inline void read(T &x) {
x = 0;
char c = getchar();
bool f = 0;
for (; !isdigit(c); c = getchar()) f ^= c == '-';
for (; isdigit(c); c = getchar()) x = (x << 3) + (x << 1) + (c ^ 48);
x = f ? -x : x;
}
const int maxN = 5e5 + 10;
int n, m, len, l, r, k, a[maxN], b[maxN];
struct ChairmanTree {
int cnt, root[maxN], lson[maxN << 5], rson[maxN << 5], sum[maxN << 5];
inline int build(int l, int r) {
int now = ++cnt, mid = l + r >> 1;
if (l != r) lson[now] = build(l, mid), rson[now] = build(mid + 1, r);
return now;
}
inline int update(int pre, int l, int r, int x) {
int now = ++cnt, mid = l + r >> 1;
lson[now] = lson[pre], rson[now] = rson[pre], sum[now] = sum[pre] + 1;
if (l != r)
if (x <= mid) lson[now] = update(lson[pre], l, mid, x);
else rson[now] = update(rson[pre], mid + 1, r, x);
return now;
}
inline void init() {
root[0] = build(1, len);
for (int i = 1; i <= n; i++) {
int tmp = lower_bound(b + 1, b + len + 1, a[i]) - b;
root[i] = update(root[i - 1], 1, len, tmp);
}
}
inline int query(int ql, int qr, int l, int r, int k) {
if (l == r) return b[l];
int x = sum[rson[qr]] - sum[rson[ql]], mid = l + r >> 1;
if (k <= x) return query(rson[ql], rson[qr], mid + 1, r, k);
else return query(lson[ql], lson[qr], l, mid, k - x);
}
inline int kth(int l, int r, int k) { return query(root[l - 1], root[r], 1, len, k); }
} tr;
int main() {
read(n), read(m);
for (int i = 1; i <= n; i++) read(a[i]), b[i] = a[i];
sort(b + 1, b + n + 1), len = unique(b + 1, b + n + 1) - b - 1;
tr.init();
for (int i = 1; i <= m; i++) {
read(l), read(r), read(k);
printf("%d\n", tr.kth(l, r, k));
}
return 0;
}
```