{ "Class_Array_tree": { "prefix": "Class_Array_tree", "body": [ "", "template ", "class Array_tree {", " public:", " Array_tree() {}", " Array_tree(int n) { this->n = n, tree = vector(n + 1); }", " void add(int id, T key) {", " for (int i = id; i <= n; i += lowbit(i)) tree[i] += key;", " }", "", " T get_sum(int id) {", " T sum = 0;", " for (int i = id; i; i -= lowbit(i)) sum += tree[i];", " return sum;", " }", "", " T get_sum(int l, int r) { return get_sum(r) - get_sum(l - 1); }", "", " private:", " int n;", " vector tree;", " int lowbit(int x) { return x & -x; }", "};", "" ] }, "Class_SGM_Tree": { "prefix": "Class_SGM_Tree", "body": [ "", "class SGM_Tree {", " public:", " class point {", " public:", " ll sum, maxi, mini;", " };", "", " vll a, lazy;", " int n;", " ll sum, maxi, mini;", " vector tree;", "", " SGM_Tree() {}", " SGM_Tree(int n, vi v) {", " // a下标默认从1开始,只需开n个点，不需要n + 1", " this->n = n;", " lazy = vll(n * 4 + 1);", " a.push_back(0);", " for (int i = 1; i <= n; i++) a.push_back(v[i]);", " tree = vector(4 * n + 1), build(1, n, 1);", " }", " SGM_Tree(int n, vll v) {", " // a下标默认从1开始,只需开n个点，不需要n + 1", " this->n = n;", " lazy = vll(n * 4 + 1);", " a.push_back(0);", " for (int i = 1; i <= n; i++) a.push_back(v[i]);", " tree = vector(4 * n + 1), build(1, n, 1);", " }", " SGM_Tree(int n, int* v) {", " // a下标默认从1开始,只需开n个点，不需要n + 1", " this->n = n;", " lazy = vll(n * 4 + 1);", " a.push_back(0);", " for (int i = 1; i <= n; i++) a.push_back(v[i]);", " tree = vector(4 * n + 1), build(1, n, 1);", " }", "", " void push_up(int k) {", " int l = k * 2, r = k * 2 + 1;", " tree[k].sum = tree[l].sum + tree[r].sum;", " tree[k].maxi = max(tree[l].maxi, tree[r].maxi);", " tree[k].mini = min(tree[l].mini, tree[r].mini);", " }", "", " void push_down(int l, int r, int k) {", " if (lazy[k]) {", " int mid = l + r >> 1;", " lazy[k * 2] += lazy[k];", " lazy[k * 2 + 1] += lazy[k];", " tree[k * 2].sum += lazy[k] * (mid - l + 1);", " tree[k * 2 + 1].sum += lazy[k] * (r - mid);", " tree[k * 2].maxi += lazy[k];", " tree[k * 2 + 1].maxi += lazy[k];", " tree[k * 2].mini += lazy[k];", " tree[k * 2 + 1].mini += lazy[k];", " lazy[k] = 0;", " }", " }", "", " void get_updata(int l, int r, int k, ll value) {", " tree[k].sum += value * (r - l + 1);", " tree[k].maxi += value;", " tree[k].mini += value;", " lazy[k] += value;", " }", "", " void get(int k) {", " sum += tree[k].sum;", " maxi = max(maxi, tree[k].maxi);", " mini = min(mini, tree[k].mini);", " }", "", " void build(int l, int r, int k) {", " if (l == r) {", " tree[k].maxi = tree[k].mini = tree[k].sum = a[l];", " return;", " }", " int mid = l + r >> 1;", " build(l, mid, k * 2);", " build(mid + 1, r, k * 2 + 1);", " push_up(k);", " }", "", " void updata(int l, int r, int L, int R, int k, ll value) {", " if (L <= l && r <= R) {", " get_updata(l, r, k, value);", " return;", " }", " push_down(l, r, k);", " int mid = l + r >> 1;", " if (L <= mid) updata(l, mid, L, R, k * 2, value);", " if (R > mid) updata(mid + 1, r, L, R, k * 2 + 1, value);", " push_up(k);", " }", "", " void query(int l, int r, int L, int R, int k) {", " if (L <= l && r <= R) {", " get(k);", " return;", " }", " push_down(l, r, k);", " int mid = l + r >> 1;", " if (mid >= L) query(l, mid, L, R, 2 * k);", " if (mid < R) query(mid + 1, r, L, R, 2 * k + 1);", " }", "", " ll get_sum(int L, int R) {", " sum = 0;", " query(1, n, L, R, 1);", " return sum;", " }", "", " ll get_max(int L, int R) {", " maxi = -inf;", " query(1, n, L, R, 1);", " return maxi;", " }", "", " ll get_min(int L, int R) {", " mini = inf;", " query(1, n, L, R, 1);", " return mini;", " }", "};", "" ] }, "Class_Dsu": { "prefix": "Class_Dsu", "body": [ "", "class Dsu {", " public:", "", " vll fa, num;", "", " Dsu(int n) { fa = vll(n + 1), num = vll(n + 1); }", " int find(int x) {", " if (!fa[x]) return x;", " return fa[x] = find(fa[x]);", " }", "", " bool Dunion(int p, int q) {", " int v = find(p), u = find(q);", " if (v == u) return 0;", " fa[u] = v;", " num[v] += num[u];", " num[u] = num[v];", " return 1;", " }", " ", "};", "", "ll num(int x) { return num[find(x)]; }", "" ] }, "class_Stmap": { "prefix": "Class_StMap", "body": [ "", "class st_map {", " public:", " st_map() {}", " st_map(vll v) {", " this->n = v.size(), this->a = v;", " this->st = vector>(n + 1);", " st_init();", " }", " int query(int l, int r) {", " int len = r - l + 1;", " int k = log(len) / log(2);", " return max(st[l][k], st[r - (1 << k) + 1][k]);", " }", "", " private:", " int n;", " vll a;", " vector> st;", " void st_init() {", " for (int j = 0; j <= 17; j++) {", " for (int i = 1; i + (1 << j) - 1 <= n; i++) {", " if (j == 0)", " st[i][j] = a[i];", " else", " st[i][j] = max(st[i][j - 1], st[i + (1 << j - 1)][j - 1]);", " }", " }", " }", "};", "" ] }, "Class_HJT_tree": { "prefix": "Class_HJT_tree", "body": [ "", "template ", "class HJT_tree {", " //处理数据默认下标从1开始", " public:", " //构造函数", " HJT_tree() {}", " HJT_tree(vector v) {", " base = v, this->n = base.size() - 1;", " tree = vector(n * 32), root.push_back(build(1, n));", " }", "", " void updata(int v, int x, T value) {", " //插入函数(版本，修改位置，修改值)", " root.push_back(insert(root[v], 1, n, x, value));", " }", "", " T query(int v, int x) {", " //查询函数（版本，查询位置）", " return get_se(root[v], 1, n, x, x);", " }", "", " T query(int v, int l, int r) {", " //查询函数（版本，查询区间）", " return get_se(root[v], 1, n, l, r);", " }", "", " private:", " vi root;", " vector base;", " int n, idx = 0;", " struct node {", " int l, r;", " T data;", " };", " vector tree;", " void pushup(int q) { tree[q].data = op(tree[q].l, tree[q].r); }", " T op(int l, int r) { return max(tree[l].data, tree[r].data); }", " T e() { return -inf; }", " int build(int l, int r) {", " int now = ++idx, mid = l + r >> 1;", " if (l != r)", " tree[now].l = build(l, mid), tree[now].r = build(mid + 1, r), pushup(now);", " return now;", " }", " int insert(int old, int l, int r, int x, int value) {", " int now = ++idx, mid = l + r >> 1;", " tree[now] = tree[old];", " if (l == r)", " tree[now].data = value;", " else {", " if (x <= mid)", " tree[now].l = insert(tree[old].l, l, mid, x, value);", " else", " tree[now].r = insert(tree[old].r, mid + 1, r, x, value);", " pushup(now);", " }", " return now;", " }", " T get_se(int v, int l, int r, int L, int R) {", " if (L <= l && r <= R) return tree[v].data;", " ll mid = l + r >> 1;", " T res = e();", " if (L <= mid) res = max(res, get_se(tree[v].l, l, mid, L, R));", " if (R > mid) res = max(res, get_se(tree[v].r, mid + 1, r, L, R));", " return res;", " }", "};", "" ] } }