线段数
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 |
#include <iostream> #include <cstring> #include <algorithm> #include <cstdio> #define ls(x) (x << 1) #define rs(x) (x << 1 | 1) using namespace std; typedef long long LL; const int N = 1e5 + 10; struct node { int l, r; LL v, add; } tr[N << 2]; int n, m; int op, x, y, k; int w[N]; void push_up(int u) { tr[u].v = tr[rs(u)].v + tr[ls(u)].v; } void push_down(int u) { auto &rt = tr[u], &l = tr[ls(u)], &r = tr[rs(u)]; if (rt.add) { l.add += rt.add; l.v += (l.r - l.l + 1) * rt.add; r.add += rt.add; r.v += (r.r - r.l + 1) * rt.add; rt.add = 0; } } void build(int u, int l, int r) { if (l == r) tr[u] = {l, r, w[l], 0}; else { tr[u] = {l, r}; int mid = l + r >> 1; build(ls(u), l, mid), build(rs(u), mid + 1, r); push_up(u); } } void modify(int u, int l, int r, int d) { if (tr[u].l >= l && tr[u].r <= r) { tr[u].add += d; tr[u].v += (tr[u].r - tr[u].l + 1) * d; } else { push_down(u); int mid = tr[u].l + tr[u].r >> 1; if (l <= mid) modify(ls(u), l, r, d); if (r > mid) modify(rs(u), l, r, d); push_up(u); } } LL query(int u, int l, int r) { if (tr[u].l >= l && tr[u].r <= r) return tr[u].v; push_down(u); int mid = tr[u].l + tr[u].r >> 1; LL v = 0; if (l <= mid) v += query(ls(u), l, r); if (r > mid) v += query(rs(u), l, r); return v; } int main() { scanf("%d%d", &n, &m); for (int i = 1; i <= n; ++ i) scanf("%d", &w[i]); build(1, 1, n); while (m --) { scanf("%d%d%d", &op, &x, &y); if (op == 1) { scanf("%d", &k); modify(1, x, y, k); } else printf("%lld\n", query(1, x, y)); } } |
树状数组
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 |
#include <iostream> #include <cstring> #include <algorithm> using namespace std; const int N = 5e5 + 10; int n, m, a, b, c; int t[N]; int lowbit(int x) { return x & -x; } void add(int x, int d) { for (; x < N; x += lowbit(x)) t[x] += d; } int query(int x) { int res = 0; for (; x; x -= lowbit(x)) res += t[x]; return res; } int main() { cin.tie(0)->sync_with_stdio(false); cout.tie(0); cin >> n >> m; for (int i = 1; i <= n; ++ i) { cin >> a; add(i, a); } while (m --) { cin >> a >> b >> c; if (a == 1) add(b, c); else cout << query(c) - query(b - 1) << '\n'; } } |
洛谷P1972 [SDOI2009]HH的项链---树状数组
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 |
#include <bits/stdc++.h> using namespace std; const int N = 1e6 + 10; int n, m; int w[N], res[N], tr[N]; int l, r; int st[N]; // 表示i出现的位置 struct node { int l, r; int pos; bool operator< (const node &x) const { return r < x.r; } } a[N]; int lowbit(int x) { return x & -x; } void add(int x, int d) { for (; x < N; x += lowbit(x)) tr[x] += d; } int query(int x) { int res = 0; for (; x; x -= lowbit(x)) res += tr[x]; return res; } int main() { scanf("%d", &n); for (int i = 1; i <= n; ++ i) scanf("%d", &w[i]); scanf("%d", &m); for (int i = 1; i <= m; ++ i) { scanf("%d%d", &l, &r); a[i] = {l, r, i}; } // 离线操作 sort(a + 1, a + 1 + m); int j = 1; for (int i = 1; i <= m; ++ i) { l = a[i].l, r = a[i].r; for (; j <= r; ++ j) { if (st[w[j]]) add(st[w[j]], -1); // 如果w[j]出现过，那么把w[j]删去 add(j, 1); // 将j加入集合 st[w[j]] = j; } res[a[i].pos] = query(r) - query(l - 1); } for (int i = 1; i <= m; ++ i) printf("%d\n", res[i]); } |
发表回复