19 条题解
-
11
鬼子进村
#include <bits/stdc++.h> #define int long long using namespace std; const int MAXN = 50000; int n, m; stack<int> sta; bool flag[MAXN + 5]; // 树状数组 int t[MAXN + 5]; int lowbit(int x) { return x & (-x); } // 第x个数加k void update(int x, int k) { for (int i = x; i <= n; i += lowbit(i)) t[i] += k; } // 返回前x个数的和 int query(int x) { int res = 0; for (int i = x; i >= 1; i -= lowbit(i)) res += t[i]; return res; } int getPos(int now) { if (now == 0) return 0; // 二分查找第一个前缀和大于等于now的位置 // 可优化（详见：http://wiki.33dai.cn/ds/fenwick/#tricks） int l = 1; int r = n; int ans = n + 1; while (l <= r) { int mid = (l + r) / 2; if (query(mid) >= now) { ans = mid; r = mid - 1; } else l = mid + 1; } return ans; } signed main() { ios::sync_with_stdio(false); cin.tie(0); cin >> n >> m; while (m--) { char op; int x; cin >> op; if (op == 'D') { cin >> x; // 摧毁 x assert(!flag[x]); // 如果x已经被摧毁了，会报RE flag[x] = true; sta.push(x); update(x, 1); } else if (op == 'Q') { cin >> x; if (flag[x]) { cout << 0 << "\n"; continue; } int now = query(x); int l = getPos(now); int r = getPos(now + 1); cout << r - l - 1 << "\n"; } else if (op == 'R') { x = sta.top(); sta.pop(); flag[x] = false; update(x, -1); } } return 0; } -
9
33DAI LV 5 (1/1) @ 2023-2-2 8:28:04
P3919 【模板】可持久化线段树 1（可持久化数组）
#include <bits/stdc++.h> using namespace std; const int MAXN = 1000000; const int MAXM = 1000000; struct Node { int val; int lc, rc; //左孩子节点编号、右孩子节点编号 } t[4 * MAXN + MAXM * 35 + 5]; int cnt = 0; //节点数量，节点编号从1开始 int rt[MAXM + 5]; //每个版本的根节点在哪儿 int n, m, a[MAXN + 5]; //对区间 l, r 建树，返回建好后的树的根节点编号 int build(int l, int r) { int root = ++cnt; if (l == r) { t[root].val = a[l]; return root; } int mid = (l + r) / 2; t[root].lc = build(l, mid); t[root].rc = build(mid + 1, r); return root; } //在now这个子树（对应区间[l,r]）中找到loc位置的值 int query(int now, int l, int r, int loc) { if (l == r) return t[now].val; int mid = (l + r) / 2; if (loc <= mid) return query(t[now].lc, l, mid, loc); else return query(t[now].rc, mid + 1, r, loc); } //在基于v这个子树（对应区间[l,r]）的 //now树（对应区间[l,r]）中 把loc位置改成val void update(int v, int now, int l, int r, int loc, int val) { if (l == r) { t[now].val = val; return; } t[now].lc = t[v].lc; t[now].rc = t[v].rc; int mid = (l + r) / 2; if (loc <= mid) { t[now].lc = ++cnt; update(t[v].lc, t[now].lc, l, mid, loc, val); } else { t[now].rc = ++cnt; update(t[v].rc, t[now].rc, mid + 1, r, loc, val); } } int main() { ios::sync_with_stdio(false); cin.tie(0); cin >> n >> m; for (int i = 1; i <= n; i++) cin >> a[i]; rt[0] = build(1, n); for (int i = 1; i <= m; i++) { int v, op, loc, value; cin >> v >> op >> loc; if (op == 1) { cin >> value; rt[i] = ++cnt; update(rt[v], rt[i], 1, n, loc, value); } else { rt[i] = ++cnt; t[rt[i]].lc = t[rt[v]].lc; t[rt[i]].rc = t[rt[v]].rc; cout << query(rt[i], 1, n, loc) << "\n"; } } return 0; } -
3
P1502 窗口的星星
#include <bits/stdc++.h> #define int long long using namespace std; int T; int n, W, H; const int MAXN = 10000 + 4; struct SQ { int x, y, xx, yy, val; } a[MAXN]; //矩形 int tempTot; //离散化点数 int temp[MAXN * 2]; //每个矩形两个y struct Line { int x, l, r, val; }; int bTot; Line b[MAXN * 2]; //边，一个矩形两条边 bool cmp(Line a, Line b) { if (a.x != b.x) return a.x < b.x; return a.val > b.val; } struct SegTree { int maxX[MAXN * 2 * 4], lazy[MAXN * 2 * 4]; void up(int now, int l, int r) { if (l == r) return; maxX[now] = max(maxX[now * 2], maxX[now * 2 + 1]); } void down(int now, int l, int r) { maxX[now * 2] += lazy[now]; maxX[now * 2 + 1] += lazy[now]; lazy[now * 2] += lazy[now]; lazy[now * 2 + 1] += lazy[now]; lazy[now] = 0; } void build(int now, int l, int r) { maxX[now] = 0; lazy[now] = 0; if (l == r) return; int mid = (l + r) / 2; build(now * 2, l, mid); build(now * 2 + 1, mid + 1, r); up(now, l, r); } void add(int now, int l, int r, int x, int y, int z) { if (x <= l && r <= y) { maxX[now] += z; lazy[now] += z; return; } down(now, l, r); int mid = (l + r) / 2; if (x <= mid) add(now * 2, l, mid, x, y, z); if (y > mid) add(now * 2 + 1, mid + 1, r, x, y, z); up(now, l, r); } } tree; signed main() { ios::sync_with_stdio(false); cin.tie(0); cin >> T; while (T--) { cin >> n >> H >> W; tempTot = 0; for (int i = 1; i <= n; i++) { int x, y, l; cin >> x >> y >> l; a[i].x = x; a[i].y = y; a[i].xx = x + H - 1; a[i].yy = y + W - 1; a[i].val = l; temp[++tempTot] = a[i].y; temp[++tempTot] = a[i].yy; } sort(temp + 1, temp + tempTot + 1); tempTot = unique(temp + 1, temp + tempTot + 1) - temp - 1; bTot = 0; for (int i = 1; i <= n; i++) { a[i].y = lower_bound(temp + 1, temp + tempTot + 1, a[i].y) - temp; a[i].yy = lower_bound(temp + 1, temp + tempTot + 1, a[i].yy) - temp; b[++bTot] = (Line){a[i].x, a[i].y, a[i].yy, a[i].val}; b[++bTot] = (Line){a[i].xx, a[i].y, a[i].yy, -a[i].val}; } sort(b + 1, b + bTot + 1, cmp); int ans = 0; tree.build(1, 1, tempTot); for (int i = 1; i <= bTot; i++) { ans = max(ans, tree.maxX[1]); tree.add(1, 1, tempTot, b[i].l, b[i].r, b[i].val); } cout << ans << "\n"; } return 0; } -
2
配对统计
#include <bits/stdc++.h> using namespace std; #define int long long const int MAXN = 300005; int t[4 * MAXN]; int n, nn, m, js = 1; struct ANS { int id, l, r; } ans[MAXN]; // id,l,r bool cmp_ans(const ANS &a, const ANS &b) { if (a.r != b.r) return a.r < b.r; else return a.l < b.l; } struct edge { int id, val; } a[MAXN]; // id,val bool cmp_a(const edge &a, const edge &b) { if (a.val != b.val) return a.val < b.val; else return a.id < b.id; } struct GOOD { int l, r; void add_GOOD(int a, int b) { l = min(a, b); r = max(a, b); } } good[MAXN * 2]; // l,r bool cmp_good(const GOOD &a, const GOOD &b) { if (a.r != b.r) return a.r < b.r; else return a.l < b.l; } int query(int now, int l, int r, int x, int y) // l、r线段树区间，x、y目标 { if (x <= l && r <= y) return t[now]; else { int mid = (l + r) / 2; int res = 0; if (x <= mid) res += query(now * 2, l, mid, x, y); if (y > mid) res += query(now * 2 + 1, mid + 1, r, x, y); return res; } } void update(int now, int l, int r, int x) { if (l == r) { t[now]++; return; } else { int mid = (l + r) / 2; if (x <= mid) update(now * 2, l, mid, x); else update(now * 2 + 1, mid + 1, r, x); t[now] = t[now * 2] + t[now * 2 + 1]; } } signed main() { ios::sync_with_stdio(false); cin.tie(0); cin >> n >> m; for (int i = 1; i <= n; i++) { cin >> a[i].val; a[i].id = i; } sort(a + 1, a + 1 + n, cmp_a); for (int i = 2; i < n; i++) { int left = a[i].val - a[i - 1].val; int right = a[i + 1].val - a[i].val; if (left < right) { good[++js].add_GOOD(a[i].id, a[i - 1].id); // 左边差更小，只有左边的一对 } else if (left == right) { good[++js].add_GOOD(a[i].id, a[i - 1].id); good[++js].add_GOOD(a[i].id, a[i + 1].id); } // 两边差更小，有两对 else { good[++js].add_GOOD(a[i].id, a[i + 1].id); // 右边差更小，只有右边的一对 } } assert(n == 1); if(n == 1) { cout << 0 << "\n"; return 0; } if (n != 1) { good[1].add_GOOD(a[1].id, a[2].id); // 首位 good[++js].add_GOOD(a[n].id, a[n - 1].id); // 末尾 } sort(good + 1, good + 1 + js, cmp_good); //------------------------------------ for (int i = 1; i <= m; i++) { int l, r; cin >> l >> r; // l、r区间和 ans[i] = ((ANS){i, l, r}); } sort(ans + 1, ans + 1 + m, cmp_ans); int da = 0; for (int i = 1, j = 1; i <= m; i++) { int id = ans[i].id; int l = ans[i].l; int r = ans[i].r; // cout << "r:" << r << endl; while (j <= js && good[j].r <= r) { // cout << "i:" << i << " j:" << j << " good[j].r" << good[j].r << endl; update(1, 1, n, good[j].l); j++; } // cout << "id" << id << ":" << query(1, 1, n, l, r) << endl; da += query(1, 1, n, l, r) * id; } cout << da; return 0; } `` -
2
P1637 三元上升子序列
#include <bits/stdc++.h> #define int long long using namespace std; const int MAXN = 30000; const int MAXAI = 100000; int n; int a[MAXN + 5]; int dp[MAXN + 5][5]; // dp[i][j] a[i]结尾的长度为j的LIS数量 // 树状数组：query[x]：k=1~i-1 a[k] 小于等于 x 的 dp[k][j-1] 之和 int t[MAXAI + 5]; int lowbit(int x) { return x & (-x); } // 第x个数加k void update(int x, int k) { for (int i = x; i <= MAXAI; i += lowbit(i)) t[i] += k; } // 返回前x个数的和 int query(int x) { int res = 0; for (int i = x; i >= 1; i -= lowbit(i)) res += t[i]; return res; } signed main() { ios::sync_with_stdio(false); cin.tie(0); cin >> n; for (int i = 1; i <= n; i++) { cin >> a[i]; dp[i][1] = 1; } /* 暴力枚举做法 for (int j = 2; j <= 3; j++) { for (int i = 1; i <= n; i++) { dp[i][j] = 0; for (int k = 1; k < i; k++) if (a[k] < a[i]) dp[i][j] += dp[k][j - 1]; } } */ for (int j = 2; j <= 3; j++) { // 树状数组初始化（可以用时间戳优化，见：http://wiki.33dai.cn/ds/fenwick/#tricks） for (int i = 1; i <= MAXAI; i++) t[i] = 0; for (int i = 1; i <= n; i++) { dp[i][j] = query(a[i] - 1); update(a[i], dp[i][j - 1]); } } int ans = 0; for (int i = 1; i <= n; i++) ans += dp[i][3]; cout << ans << "\n"; return 0; } -
2
区间
使用封装了的线段树完成的例子
#include <bits/stdc++.h> using namespace std; const int MAXN = 1000000 + 5; int n, m; struct Seg { int l, r, len; }; bool cmp(Seg a, Seg b) { return a.len < b.len; } Seg a[MAXN / 2]; vector<int> temp; struct SegTree { int maxX[4 * MAXN], lazy[4 * MAXN]; void up(int now) { maxX[now] = max(maxX[now * 2], maxX[now * 2 + 1]); } void down(int now, int l, int r) { if (l == r) return; int mid = (l + r) / 2; maxX[now * 2] = maxX[now * 2] + lazy[now]; maxX[now * 2 + 1] = maxX[now * 2 + 1] + lazy[now]; lazy[now * 2] += lazy[now]; lazy[now * 2 + 1] += lazy[now]; lazy[now] = 0; } void build(int now, int l, int r) { lazy[now] = 0; if (l == r) { maxX[now] = 0; return; } int mid = (l + r) / 2; build(now * 2, l, mid); build(now * 2 + 1, mid + 1, r); up(now); } void add(int now, int l, int r, int x, int y, int z) { if (x <= l && r <= y) { lazy[now] = lazy[now] + z; maxX[now] = maxX[now] + z; return; } down(now, l, r); int mid = (l + r) / 2; if (x <= mid) add(now * 2, l, mid, x, y, z); if (y >= mid + 1) add(now * 2 + 1, mid + 1, r, x, y, z); up(now); } int query(int now, int l, int r, int x, int y) { if (x <= l && r <= y) return maxX[now]; down(now, l, r); int mid = (l + r) / 2; int res = 0; if (x <= mid) res = max(res, query(now * 2, l, mid, x, y)); if (y >= mid + 1) res = max(res, query(now * 2 + 1, mid + 1, r, x, y)); return res; } } tree; int main() { ios::sync_with_stdio(false); cin.tie(0); cin >> n >> m; for (int i = 1; i <= n; i++) { cin >> a[i].l >> a[i].r; a[i].len = a[i].r - a[i].l + 1; temp.push_back(a[i].l); temp.push_back(a[i].r); } sort(temp.begin(), temp.end()); for (int i = 1; i <= n; i++) { a[i].l = lower_bound(temp.begin(), temp.end(), a[i].l) - temp.begin() + 1; a[i].r = lower_bound(temp.begin(), temp.end(), a[i].r) - temp.begin() + 1; } sort(a + 1, a + n + 1, cmp); int nn = n; n = 2 * n; // 线段：a[1]~a[nn] // 端点：1~n // 线段树维护：每个端点被覆盖的次数 tree.build(1, 1, n); // 初始每个端点被覆盖的次数都是 0 // 使用 a[p]~a[q] 这些线段 // 可以使得被覆盖次数最多的那个点，覆盖的次数达到m // 并且 a[p]~a[q-1] 不行 int ans = -1; for (int p = 1, q = 0; p <= nn;) { // 找到q while (q < nn && tree.query(1, 1, n, 1, n) < m) { // 加入一条新线段 q++; tree.add(1, 1, n, a[q].l, a[q].r, 1); } if (tree.query(1, 1, n, 1, n) != m) break; // a[p]~a[q] 这些线段做到了！！！！ if (ans == -1 || a[q].len - a[p].len < ans) ans = a[q].len - a[p].len; // p++ tree.add(1, 1, n, a[p].l, a[p].r, -1); p++; } cout << ans << "\n"; return 0; } -
2
中位数
对顶堆写法
#include <bits/stdc++.h> using namespace std; const int MAXN = 1000000; int n; int a[MAXN + 5]; // ql（大的优先） < qr（小的优先） priority_queue<int> ql; priority_queue<int> qr; int main() { ios::sync_with_stdio(false); cin.tie(0); cin >> n; for (int i = 1; i <= n; i++) cin >> a[i]; if (n % 2 == 0) n--; ql.push(a[1]); cout << ql.top() << "\n"; for (int i = 2; i <= n; i += 2) { // 放入a[i],a[i+1] if (a[i] <= ql.top()) ql.push(a[i]); else qr.push(-a[i]); if (a[i + 1] <= ql.top()) ql.push(a[i + 1]); else qr.push(-a[i + 1]); // 保证左边比右边多 if (ql.size() < qr.size()) { ql.push(-qr.top()); qr.pop(); } // 保证数量相差1 while (ql.size() - qr.size() > 1) { qr.push(-ql.top()); ql.pop(); } cout << ql.top() << "\n"; } return 0; }线段树写法
先离散化
a[]，然后用线段树维护每个数出现了几次，update(1,1,n,x,1)来给x的出现次数加1。然后在线段树上 dfs 找到第 名是谁实现中位数。#include <bits/stdc++.h> using namespace std; const int MAXN = 500000; int n, m; int a[MAXN + 5]; int temp[MAXN + 5]; // 线段树：单点修改、区间查询（区间和） int t[4 * MAXN + 5]; // 当前做到了树上的now号节点，当前节点对应的区间为 [l,r] // 需要给第x个数加y void update(int now, int l, int r, int x, int y) { if (l == r) { t[now] += y; return; } int mid = (l + r) / 2; // 左子树 now*2,l,mid // 右子树 now*2+1,mid+1,r if (x <= mid) update(now * 2, l, mid, x, y); else update(now * 2 + 1, mid + 1, r, x, y); t[now] = t[now * 2] + t[now * 2 + 1]; } int query(int now, int l, int r, int x, int y) { //[l,r] 是 [x,y] 的子区间 if (x <= l && r <= y) return t[now]; int mid = (l + r) / 2; // 左子树 now*2,l,mid // 右子树 now*2+1,mid+1,r int res = 0; if (x <= mid) res += query(now * 2, l, mid, x, y); if (y > mid) res += query(now * 2 + 1, mid + 1, r, x, y); return res; } int dfs(int now, int l, int r, int k) { if (l == r) return l; int mid = (l + r) / 2; if (t[now * 2] >= k) return dfs(now * 2, l, mid, k); else return dfs(now * 2 + 1, mid + 1, r, k - t[now * 2]); } int main() { ios::sync_with_stdio(false); cin.tie(0); cin >> n; for (int i = 1; i <= n; i++) { cin >> a[i]; temp[i] = a[i]; } sort(temp + 1, temp + n + 1); for (int i = 1; i <= n; i++) a[i] = lower_bound(temp + 1, temp + n + 1, a[i]) - temp; // 找中位数 update(1, 1, n, a[1], 1); int k = 1; cout << temp[a[1]] << '\n'; if (n % 2 == 0) n--; for (int i = 2; i <= n; i += 2) { update(1, 1, n, a[i], 1); update(1, 1, n, a[i + 1], 1); k++; cout << temp[dfs(1, 1, n, k)] << "\n"; // 找到排名为k的数是几 } return 0; }树状数组写法
下面给出的查第 大数的写法是单次 的，如果想要 实现，可以查看 http://wiki.33dai.cn/ds/fenwick/#tricks
#include <bits/stdc++.h> using namespace std; const int MAXN = 500000; int n, m; int a[MAXN + 5]; int temp[MAXN + 5]; // 树状数组 int t[MAXN + 5]; int lowbit(int x) { return x & (-x); } // 第x个数加k void update(int x, int k) { for (int i = x; i <= n; i += lowbit(i)) t[i] += k; } // 返回前x个数的和 int query(int x) { int res = 0; for (int i = x; i >= 1; i -= lowbit(i)) res += t[i]; return res; } int main() { ios::sync_with_stdio(false); cin.tie(0); cin >> n; for (int i = 1; i <= n; i++) { cin >> a[i]; temp[i] = a[i]; } sort(temp + 1, temp + n + 1); for (int i = 1; i <= n; i++) a[i] = lower_bound(temp + 1, temp + n + 1, a[i]) - temp; // 找中位数 update(a[1], 1); int k = 1; cout << temp[a[1]] << '\n'; if (n % 2 == 0) n--; for (int i = 2; i <= n; i += 2) { update(a[i], 1); update(a[i + 1], 1); k++; // 找到排名为k的数是几 int l = 1; int r = n; int ans = -1; while (l <= r) { int mid = (l + r) / 2; if (query(mid) >= k) { ans = mid; r = mid - 1; } else l = mid + 1; } cout << temp[ans] << "\n"; } return 0; } -
1
P4145 上帝造题的七分钟 2 / 花神游历各国
#include <bits/stdc++.h> #define int long long using namespace std; const int MAXN = 500000 + 5; int n, m; int a[MAXN]; //线段树 bool flag[MAXN << 2]; int t[MAXN << 2]; void up(int now) { t[now] = t[now * 2] + t[now * 2 + 1]; flag[now] = flag[now * 2] && flag[now * 2 + 1]; } void build(int now, int l, int r) { if (l == r) { t[now] = a[l]; flag[now] = t[now] == 1 || t[now] == 0; return; } int mid = (l + r) / 2; build(now * 2, l, mid); build(now * 2 + 1, mid + 1, r); up(now); } void update(int now, int l, int r, int x, int y) { if (flag[now]) return; if (l == r) { t[now] = sqrt(t[now]); flag[now] = t[now] == 1 || t[now] == 0; return; } int mid = (l + r) / 2; if (x <= mid) update(now * 2, l, mid, x, y); if (y > mid) update(now * 2 + 1, mid + 1, r, x, y); up(now); } int query(int now, int l, int r, int x, int y) { if (x <= l && r <= y) return t[now]; int res = 0; int mid = (l + r) / 2; if (x <= mid) res += query(now * 2, l, mid, x, y); if (y > mid) res += query(now * 2 + 1, mid + 1, r, x, y); return res; } signed main() { ios::sync_with_stdio(false); cin.tie(0); cin >> n; for (int i = 1; i <= n; i++) cin >> a[i]; build(1, 1, n); cin >> m; while (m--) { int op, l, r; cin >> op >> l >> r; if (l > r) swap(l, r); if (op == 0) update(1, 1, n, l, r); else cout << query(1, 1, n, l, r) << "\n"; } return 0; } -
1
HH的项链
#include <bits/stdc++.h> #define int long long using namespace std; const int MAXN = 1000000; const int MAXM = 1000000; const int MAXAI = 1000000; int n, m; int a[MAXN + 5]; // 存每个位置为右端点的询问<询问的左端点,询问的编号> vector<pair<int, int>> q[MAXN + 5]; int ans[MAXM + 5]; // pos[i]：i这个种类最新出现的位置 int pos[MAXAI + 5]; // 树状数组 int t[MAXN + 5], treeN; int lowbit(int x) { return x & (-x); } // 第x个数加k void update(int x, int k) { for (int i = x; i <= treeN; i += lowbit(i)) t[i] += k; } // 返回前x个数的和 int query(int x) { int res = 0; for (int i = x; i >= 1; i -= lowbit(i)) res += t[i]; return res; } signed main() { ios::sync_with_stdio(false); cin.tie(0); cin >> n; for (int i = 1; i <= n; i++) { cin >> a[i]; pos[a[i]] = -1; } cin >> m; for (int i = 1; i <= m; i++) { int l, r; cin >> l >> r; ans[i] = 0; q[r].push_back(make_pair(l, i)); } treeN = n; for (int r = 1; r <= n; r++) { if (pos[a[r]] != -1) update(pos[a[r]], -1); pos[a[r]] = r; update(r, 1); for (int i = 0; i < q[r].size(); i++) { int l = q[r][i].first; int id = q[r][i].second; ans[id] = query(r) - query(l - 1); } } for (int i = 1; i <= m; i++) cout << ans[i] << "\n"; return 0; } -
1
园丁的烦恼
#include <bits/stdc++.h> #define int long long using namespace std; const int MAXN = 500000; const int MAXM = 500000; int n, m; int ans[MAXM + 5]; // 第i个矩形的答案 struct OP { // op==0：加入一个树 (x,y) // op>0: 需要查询 (1,1)~(x,y) 有多少树，把答案乘w后加入ans[op] int op, x, y, w; }; bool operator<(const OP &a, const OP &b) { if (a.x != b.x) return a.x < b.x; if (a.y != b.y) return a.y < b.y; return a.op < b.op;//优先加树再询问 } vector<OP> o; // 离散化y的辅助数组 vector<int> temp; // 树状数组 int t[MAXN + MAXM * 4 + 5], treeN; int lowbit(int x) { return x & (-x); } // 第x个数加k void update(int x, int k) { for (int i = x; i <= treeN; i += lowbit(i)) t[i] += k; } // 返回前x个数的和 int query(int x) { int res = 0; for (int i = x; i >= 1; i -= lowbit(i)) res += t[i]; return res; } signed main() { ios::sync_with_stdio(false); cin.tie(0); cin >> n >> m; for (int i = 1; i <= n; i++) { int x, y; cin >> x >> y; x++, y++; o.push_back((OP){0, x, y, 0}); temp.push_back(y); } for (int i = 1; i <= m; i++) { ans[i] = 0; int x, y, xx, yy; cin >> x >> y >> xx >> yy; x++, y++, xx++, yy++; o.push_back((OP){i, xx, yy, 1}); o.push_back((OP){i, x - 1, yy, -1}); o.push_back((OP){i, xx, y - 1, -1}); o.push_back((OP){i, x - 1, y - 1, 1}); temp.push_back(yy); temp.push_back(y - 1); } // 对y离散化 sort(temp.begin(), temp.end()); treeN = 0; for (int i = 0; i < o.size(); i++) { o[i].y = lower_bound(temp.begin(), temp.end(), o[i].y) - temp.begin(); // 让y离散化后从1开始 o[i].y += 1; treeN = max(treeN, o[i].y); } // 按x坐标排序所有操作，然后依次处理 sort(o.begin(), o.end()); for (int i = 0; i < o.size(); i++) { //cout << o[i].op << " " << o[i].x << " " << o[i].y << " " << o[i].w << ": "; if (o[i].op == 0) { update(o[i].y, 1); //cout << "add (" << o[i].x << "," << o[i].y << ")\n"; } else { ans[o[i].op] += o[i].w * (query(o[i].y)); //cout << "ans[" << o[i].op << "]+=" << o[i].w << "*" << query(o[i].y) << "\n"; } } for (int i = 1; i <= m; i++) cout << ans[i] << "\n"; return 0; } -
1
扫描线
#include <bits/stdc++.h> #define int long long using namespace std; const int MAXN = 100000 + 5; int n; struct SQ { int x, y, xx, yy; }; struct Seg { int x, l, r, t; }; bool cmp(Seg a, Seg b) { return a.x < b.x; } SQ a[MAXN]; int vtot; int v[MAXN * 2]; int btot; Seg b[MAXN * 2]; struct SegTree { int sum[8 * MAXN], cnt[8 * MAXN]; void up(int now, int l, int r) { if (cnt[now]) { sum[now] = v[r + 1] - v[l]; } else if (l == r) sum[now] = 0; else sum[now] = sum[now * 2] + sum[now * 2 + 1]; } void add(int now, int l, int r, int x, int y, int z) { if (x <= l && r <= y) { cnt[now] += z; up(now, l, r); return; } int mid = (l + r) / 2; if (x <= mid) add(now * 2, l, mid, x, y, z); if (y >= mid + 1) add(now * 2 + 1, mid + 1, r, x, y, z); up(now, l, r); } } tree; signed main() { ios::sync_with_stdio(false); cin.tie(0); cin >> n; for (int i = 1; i <= n; i++) { cin >> a[i].x >> a[i].y >> a[i].xx >> a[i].yy; v[++vtot] = a[i].y; v[++vtot] = a[i].yy; } sort(v + 1, v + vtot + 1); vtot = unique(v + 1, v + vtot + 1) - v - 1; for (int i = 1; i <= n; i++) { a[i].y = lower_bound(v + 1, v + vtot + 1, a[i].y) - v; a[i].yy = lower_bound(v + 1, v + vtot + 1, a[i].yy) - v; b[++btot] = (Seg){a[i].x, a[i].y, a[i].yy, 1}; b[++btot] = (Seg){a[i].xx, a[i].y, a[i].yy, -1}; } sort(b + 1, b + 2 * n + 1, cmp); int ans = 0; for (int i = 1; i <= 2 * n; i++) { if (i > 1) ans += tree.sum[1] * (b[i].x - b[i - 1].x); tree.add(1, 1, vtot, b[i].l, b[i].r - 1, b[i].t); } cout << ans << endl; return 0; } -
1
最大数
使用封装了的线段树完成的例子
#include <bits/stdc++.h> using namespace std; const int MAXN = 200000 + 5; int D; struct SegTree { int sum[MAXN * 4], maxx[MAXN * 4]; void build(int o, int l, int r) { if (l == r) { sum[o] = maxx[o] = 0; return; } int mid = (l + r) >> 1; build(o * 2, l, mid); build(o * 2 + 1, mid + 1, r); sum[o] = sum[o * 2] + sum[o * 2 + 1]; maxx[o] = max(maxx[o * 2], maxx[o * 2 + 1]); } int query_max(int o, int l, int r, int ql, int qr) { if (l > qr || r < ql) return -1; if (ql <= l && r <= qr) return maxx[o]; int mid = (l + r) >> 1; return max(query_max(o * 2, l, mid, ql, qr), query_max(o * 2 + 1, mid + 1, r, ql, qr)); } int query_sum(int o, int l, int r, int ql, int qr) { if (l > qr || r < ql) return 0; if (ql <= l && r <= qr) return sum[o]; int mid = (l + r) >> 1; return query_sum(o * 2, l, mid, ql, qr) + query_sum(o * 2 + 1, mid + 1, r, ql, qr); } void update(int o, int l, int r, int x, int t) { if (l == r) { maxx[o] = sum[o] = t; return; } int mid = (l + r) >> 1; if (x <= mid) update(o * 2, l, mid, x, t); // 左右分别更新 else update(o * 2 + 1, mid + 1, r, x, t); sum[o] = sum[o * 2] + sum[o * 2 + 1]; maxx[o] = max(maxx[o * 2], maxx[o * 2 + 1]); } } st; int m, cnt, t, n; int a[MAXN]; int main() { ios::sync_with_stdio(false); cin.tie(0); cin >> m >> D; n = m; st.build(1, 1, n); cnt = t = 0; while (m--) { char op; int x; cin >> op >> x; if (op == 'A') { cnt++; st.update(1, 1, n, cnt, (t + x) % D); } else if (op == 'Q') { t = st.query_max(1, 1, n, cnt - x + 1, cnt); cout << t << "\n"; } } return 0; } -
1
P1966 [NOIP2013 提高组] 火柴排队
离散化+归并排序求逆序对的代码
#include <bits/stdc++.h> using namespace std; const int MODNUM = 100000000 - 3; int n; int a[100005]; int b[100005]; int rnk[100005]; int temp[100005]; long long ans; void mergeSort(int l, int r) { if (l == r) return; int mid = (l + r) / 2; mergeSort(l, mid); mergeSort(mid + 1, r); int pl = l, pr = mid + 1, pt = l; while (pl <= mid && pr <= r) { if (rnk[b[pl]] <= rnk[b[pr]]) temp[pt++] = b[pl++]; else { ans = (ans + mid - pl + 1) % MODNUM; temp[pt++] = b[pr++]; } } while (pl <= mid) temp[pt++] = b[pl++]; while (pr <= r) temp[pt++] = b[pr++]; for (int i = l; i <= r; i++) b[i] = temp[i]; } int main() { ios::sync_with_stdio(false); cin.tie(0); cin >> n; //输入并离散化 a for (int i = 1; i <= n; i++) { cin >> a[i]; temp[i] = a[i]; } sort(temp + 1, temp + n + 1); for (int i = 1; i <= n; i++) a[i] = lower_bound(temp + 1, temp + n + 1, a[i]) - temp; //输入并离散化 b for (int i = 1; i <= n; i++) { cin >> b[i]; temp[i] = b[i]; } sort(temp + 1, temp + n + 1); for (int i = 1; i <= n; i++) b[i] = lower_bound(temp + 1, temp + n + 1, b[i]) - temp; //求 a 数组中每个数的排名 rnk //rnk[i] 表示 i 在 a 数组中排第几 for (int i = 1; i <= n; i++) rnk[a[i]] = i; //以 a 对应排名算逆序对 ans = 0; mergeSort(1, n); cout << ans << '\n'; return 0; }离散化+树状数组求逆序对
#include <bits/stdc++.h> using namespace std; const int MODNUM = 100000000 - 3; int n; int a[100005]; int b[100005]; int rnk[100005]; int temp[100005]; // 树状数组，统计每个数出现了几次 int t[100005]; int lowbit(int x) { return x & (-x); } // 第x个数加k void update(int x, int k) { for (int i = x; i <= n; i += lowbit(i)) t[i] += k; } // 返回前x个数的和 int query(int x) { int res = 0; for (int i = x; i >= 1; i -= lowbit(i)) res += t[i]; return res; } int main() { ios::sync_with_stdio(false); cin.tie(0); cin >> n; // 输入并离散化 a for (int i = 1; i <= n; i++) { cin >> a[i]; temp[i] = a[i]; } sort(temp + 1, temp + n + 1); for (int i = 1; i <= n; i++) a[i] = lower_bound(temp + 1, temp + n + 1, a[i]) - temp; // 输入并离散化 b for (int i = 1; i <= n; i++) { cin >> b[i]; temp[i] = b[i]; } sort(temp + 1, temp + n + 1); for (int i = 1; i <= n; i++) b[i] = lower_bound(temp + 1, temp + n + 1, b[i]) - temp; // 求 a 数组中每个数的排名 rnk // rnk[i] 表示 i 在 a 数组中排第几 for (int i = 1; i <= n; i++) rnk[a[i]] = i; // 把 b[] 的每个数改为它正确的排名 for (int i = 1; i <= n; i++) b[i] = rnk[b[i]]; // 求 b[] 的逆序对 long long ans = 0; for (int i = 1; i <= n; i++) { update(b[i], 1); // 目前一共有i个数，小于等于b[i]的有query(b[i])个 ans = (ans + i - query(b[i])) % MODNUM; } cout << ans << "\n"; return 0; } -
1
逆序对（树状数组写法）
#include <bits/stdc++.h> using namespace std; const int MAXN = 500000; int n; int a[MAXN + 5]; int temp[MAXN + 5]; // 树状数组，统计每个数出现了几次 int t[MAXN + 5]; int lowbit(int x) { return x & (-x); } // 第x个数加k void update(int x, int k) { for (int i = x; i <= n; i += lowbit(i)) t[i] += k; } // 返回前x个数的和 int query(int x) { int res = 0; for (int i = x; i >= 1; i -= lowbit(i)) res += t[i]; return res; } int main() { ios::sync_with_stdio(false); cin.tie(0); cin >> n; for (int i = 1; i <= n; i++) { cin >> a[i]; temp[i] = a[i]; } sort(temp + 1, temp + n + 1); for (int i = 1; i <= n; i++) a[i] = lower_bound(temp + 1, temp + n + 1, a[i]) - temp; long long ans = 0; for (int i = 1; i <= n; i++) { update(a[i], 1); // 目前一共有i个数，小于等于a[i]的有query(a[i])个 ans += i - query(a[i]); } cout << ans << "\n"; return 0; } -
1
线段树
P3374 【模板】树状数组 1
单点修改、区间查询（区间和）
#include <bits/stdc++.h> using namespace std; const int MAXN = 500000; int n, m; int a[MAXN + 5]; // 线段树：单点修改、区间查询（区间和） int t[4 * MAXN + 5]; // 基于a[]建线段树 void build(int now, int l, int r) { if (l == r) { t[now] = a[l]; return; } int mid = (l + r) / 2; build(now * 2, l, mid); build(now * 2 + 1, mid + 1, r); t[now] = t[now * 2] + t[now * 2 + 1]; } // 当前做到了树上的now号节点，当前节点对应的区间为 [l,r] // 需要给第x个数加y void update(int now, int l, int r, int x, int y) { if (l == r) { t[now] += y; return; } int mid = (l + r) / 2; // 左子树 now*2,l,mid // 右子树 now*2+1,mid+1,r if (x <= mid) update(now * 2, l, mid, x, y); else update(now * 2 + 1, mid + 1, r, x, y); t[now] = t[now * 2] + t[now * 2 + 1]; } int query(int now, int l, int r, int x, int y) { //[l,r] 是 [x,y] 的子区间 if (x <= l && r <= y) return t[now]; int mid = (l + r) / 2; // 左子树 now*2,l,mid // 右子树 now*2+1,mid+1,r int res = 0; if (x <= mid) res += query(now * 2, l, mid, x, y); if (y > mid) res += query(now * 2 + 1, mid + 1, r, x, y); return res; } int main() { ios::sync_with_stdio(false); cin.tie(0); cin >> n >> m; for (int i = 1; i <= n; i++) { cin >> a[i]; } build(1, 1, n); while (m--) { int op, x, y; cin >> op; if (op == 1) { cin >> x >> y; // a[x]+=y update(1, 1, n, x, y); } else { cin >> x >> y; // cout sum(a[x]~a[y]) cout << query(1, 1, n, x, y) << "\n"; } } return 0; }P3372 【模板】线段树 1
【线段树1】
区间修改（加法），区间查询（和）
#include <bits/stdc++.h> #define int long long using namespace std; const int MAXN = 100000; int n, m; int a[MAXN + 5]; // 线段树：单点修改、区间查询（区间和） int t[4 * MAXN + 5], lazy[4 * MAXN + 5]; // 基于a[]建线段树 void build(int now, int l, int r) { if (l == r) { t[now] = a[l]; return; } int mid = (l + r) / 2; build(now * 2, l, mid); build(now * 2 + 1, mid + 1, r); t[now] = t[now * 2] + t[now * 2 + 1]; } void down(int now, int l, int r) { int mid = (l + r) / 2; // 左子树 now*2,l,mid // 右子树 now*2+1,mid+1,r lazy[now * 2] += lazy[now]; t[now * 2] += (mid - l + 1) * lazy[now]; lazy[now * 2 + 1] += lazy[now]; t[now * 2 + 1] += (r - mid) * lazy[now]; lazy[now] = 0; } // 当前做到了树上的now号节点，当前节点对应的区间为 [l,r] // 需要给 [x,y] 这些数都加 z void update(int now, int l, int r, int x, int y, int z) { if (x <= l && r <= y) { t[now] += (r - l + 1) * z; lazy[now] += z; return; } int mid = (l + r) / 2; // 左子树 now*2,l,mid // 右子树 now*2+1,mid+1,r down(now, l, r); // 把之前欠的结清 if (x <= mid) update(now * 2, l, mid, x, y, z); if (y > mid) update(now * 2 + 1, mid + 1, r, x, y, z); t[now] = t[now * 2] + t[now * 2 + 1]; } int query(int now, int l, int r, int x, int y) { //[l,r] 是 [x,y] 的子区间 if (x <= l && r <= y) return t[now]; int mid = (l + r) / 2; // 左子树 now*2,l,mid // 右子树 now*2+1,mid+1,r down(now, l, r); // 把之前欠的结清 int res = 0; if (x <= mid) res += query(now * 2, l, mid, x, y); if (y > mid) res += query(now * 2 + 1, mid + 1, r, x, y); return res; } signed main() { ios::sync_with_stdio(false); cin.tie(0); cin >> n >> m; for (int i = 1; i <= n; i++) { cin >> a[i]; } build(1, 1, n); while (m--) { int op, x, y, z; cin >> op; if (op == 1) { cin >> x >> y >> z; update(1, 1, n, x, y, z); } else { cin >> x >> y; // cout sum(a[x]~a[y]) cout << query(1, 1, n, x, y) << "\n"; } } return 0; }【标记永久化】
#include <bits/stdc++.h> #define int long long using namespace std; const int MAXN = 100000; int n, m; int a[MAXN + 5]; // 线段树：单点修改、区间查询（区间和） int t[4 * MAXN + 5], lazy[4 * MAXN + 5]; // 基于a[]建线段树 void build(int now, int l, int r) { if (l == r) { t[now] = a[l]; return; } int mid = (l + r) / 2; build(now * 2, l, mid); build(now * 2 + 1, mid + 1, r); t[now] = t[now * 2] + t[now * 2 + 1]; } // 当前做到了树上的now号节点，当前节点对应的区间为 [l,r] // 需要给 [x,y] 这些数都加 z void update(int now, int l, int r, int x, int y, int z) { t[now] += (min(y, r) - max(x, l) + 1) * z; if (x <= l && r <= y) { lazy[now] += z; return; } int mid = (l + r) / 2; // 左子树 now*2,l,mid // 右子树 now*2+1,mid+1,r if (x <= mid) update(now * 2, l, mid, x, y, z); if (y > mid) update(now * 2 + 1, mid + 1, r, x, y, z); } int query(int now, int l, int r, int x, int y, int lazySum) { //[l,r] 是 [x,y] 的子区间 if (x <= l && r <= y) return t[now] + (r - l + 1) * lazySum; int mid = (l + r) / 2; // 左子树 now*2,l,mid // 右子树 now*2+1,mid+1,r int res = 0; lazySum += lazy[now]; if (x <= mid) res += query(now * 2, l, mid, x, y, lazySum); if (y > mid) res += query(now * 2 + 1, mid + 1, r, x, y, lazySum); return res; } signed main() { ios::sync_with_stdio(false); cin.tie(0); cin >> n >> m; for (int i = 1; i <= n; i++) { cin >> a[i]; } build(1, 1, n); while (m--) { int op, x, y, z; cin >> op; if (op == 1) { cin >> x >> y >> z; update(1, 1, n, x, y, z); } else { cin >> x >> y; // cout sum(a[x]~a[y]) cout << query(1, 1, n, x, y, 0) << "\n"; } } return 0; }【标记永久化+动态开点】
#include <bits/stdc++.h> #define int long long using namespace std; const int MAXN = 100000; int n, m; int a[MAXN + 5]; // 线段树：单点修改、区间查询（区间和） struct Node { // 左右子节点 lc,rc // 区间和: sum，加法懒标记：lazy int lc, rc, sum, lazy; }; int tot; // 节点数量 Node t[4 * MAXN + 5]; // 基于a[] 建线段树，返回根节点 int build(int l, int r) { int now = ++tot; if (l == r) { t[now].sum = a[l]; return; } int mid = (l + r) / 2; t[now].lc = build(l, mid); t[now].rc = build(mid + 1, r); t[now].sum = t[t[now].lc].sum + t[t[now].rc].sum; return now; } // 当前做到了树上的now号节点，当前节点对应的区间为 [l,r] // 需要给 [x,y] 这些数都加 z void update(int now, int l, int r, int x, int y, int z) { t[now].sum += (min(y, r) - max(x, l) + 1) * z; if (x <= l && r <= y) { t[now].lazy += z; return; } int mid = (l + r) / 2; // 左子树 now*2,l,mid // 右子树 now*2+1,mid+1,r if (!t[now].lc) t[now].lc = ++tot; if (!t[now].rc) t[now].rc = ++tot; if (x <= mid) update(t[now].lc, l, mid, x, y, z); if (y > mid) update(t[now].rc, mid + 1, r, x, y, z); } int query(int now, int l, int r, int x, int y, int lazySum) { //[l,r] 是 [x,y] 的子区间 if (x <= l && r <= y) return t[now].sum + (r - l + 1) * lazySum; int mid = (l + r) / 2; // 左子树 now*2,l,mid // 右子树 now*2+1,mid+1,r int res = 0; if (!t[now].lc) t[now].lc = ++tot; if (!t[now].rc) t[now].rc = ++tot; lazySum += t[now].lazy; if (x <= mid) res += query(t[now].lc, l, mid, x, y, lazySum); if (y > mid) res += query(t[now].rc, mid + 1, r, x, y, lazySum); return res; } signed main() { ios::sync_with_stdio(false); cin.tie(0); cin >> n >> m; for (int i = 1; i <= n; i++) { cin >> a[i]; } int root = build(1, n); while (m--) { int op, x, y, z; cin >> op; if (op == 1) { cin >> x >> y >> z; update(root, 1, n, x, y, z); } else { cin >> x >> y; // cout sum(a[x]~a[y]) cout << query(root, 1, n, x, y, 0) << "\n"; } } return 0; }P3373 【模板】线段树 2
【线段树2】
#include <bits/stdc++.h> #define int long long using namespace std; const int MAXN = 100000; int n, m, p; int a[MAXN + 5]; // 线段树：单点修改、区间查询（区间和） int t[4 * MAXN + 5]; int lazyAdd[4 * MAXN + 5], lazyMul[4 * MAXN + 5]; // 基于a[]建线段树 void build(int now, int l, int r) { lazyAdd[now] = 0; lazyMul[now] = 1; if (l == r) { t[now] = a[l]; return; } int mid = (l + r) / 2; build(now * 2, l, mid); build(now * 2 + 1, mid + 1, r); t[now] = t[now * 2] + t[now * 2 + 1]; t[now] %= p; } void down(int now, int l, int r) { int mid = (l + r) / 2; // 左子树 now*2,l,mid // 右子树 now*2+1,mid+1,r int add = lazyAdd[now]; int mul = lazyMul[now]; lazyMul[now * 2] *= mul; lazyMul[now * 2] %= p; lazyAdd[now * 2] *= mul; lazyAdd[now * 2] %= p; t[now * 2] *= mul; t[now * 2] %= p; lazyAdd[now * 2] += add; lazyAdd[now * 2] %= p; t[now * 2] += (mid - l + 1) * add; t[now * 2] %= p; lazyMul[now * 2 + 1] *= mul; lazyMul[now * 2 + 1] %= p; lazyAdd[now * 2 + 1] *= mul; lazyAdd[now * 2 + 1] %= p; t[now * 2 + 1] *= mul; t[now * 2 + 1] %= p; lazyAdd[now * 2 + 1] += add; lazyAdd[now * 2 + 1] %= p; t[now * 2 + 1] += (r - mid) * add; t[now * 2 + 1] %= p; lazyAdd[now] = 0; lazyMul[now] = 1; } // 当前做到了树上的now号节点，当前节点对应的区间为 [l,r] // 需要给 [x,y] 这些数都加 z void update_add(int now, int l, int r, int x, int y, int z) { if (x <= l && r <= y) { t[now] += (r - l + 1) * z; t[now] %= p; lazyAdd[now] += z; lazyAdd[now] %= p; return; } int mid = (l + r) / 2; // 左子树 now*2,l,mid // 右子树 now*2+1,mid+1,r down(now, l, r); // 把之前欠的结清 if (x <= mid) update_add(now * 2, l, mid, x, y, z); if (y > mid) update_add(now * 2 + 1, mid + 1, r, x, y, z); t[now] = t[now * 2] + t[now * 2 + 1]; t[now] %= p; } void update_mul(int now, int l, int r, int x, int y, int z) { if (x <= l && r <= y) { t[now] *= z; t[now] %= p; lazyMul[now] *= z; lazyMul[now] %= p; lazyAdd[now] *= z; lazyAdd[now] %= p; return; } int mid = (l + r) / 2; // 左子树 now*2,l,mid // 右子树 now*2+1,mid+1,r down(now, l, r); // 把之前欠的结清 if (x <= mid) update_mul(now * 2, l, mid, x, y, z); if (y > mid) update_mul(now * 2 + 1, mid + 1, r, x, y, z); t[now] = t[now * 2] + t[now * 2 + 1]; t[now] %= p; } int query(int now, int l, int r, int x, int y) { //[l,r] 是 [x,y] 的子区间 if (x <= l && r <= y) return t[now]; int mid = (l + r) / 2; // 左子树 now*2,l,mid // 右子树 now*2+1,mid+1,r down(now, l, r); // 把之前欠的结清 int res = 0; if (x <= mid) res += query(now * 2, l, mid, x, y); if (y > mid) res += query(now * 2 + 1, mid + 1, r, x, y); return res % p; } signed main() { ios::sync_with_stdio(false); cin.tie(0); cin >> n >> m >> p; for (int i = 1; i <= n; i++) { cin >> a[i]; } build(1, 1, n); while (m--) { int op, x, y, z; cin >> op; if (op == 1) { cin >> x >> y >> z; update_mul(1, 1, n, x, y, z); } else if (op == 2) { cin >> x >> y >> z; update_add(1, 1, n, x, y, z); } else if (op == 3) { cin >> x >> y; // cout sum(a[x]~a[y]) cout << query(1, 1, n, x, y) << "\n"; } } return 0; } -
1
树状数组1
#include <bits/stdc++.h> using namespace std; const int MAXN = 500000; int n, m; int a[MAXN + 5]; int t[MAXN + 5]; int lowbit(int x) { return x & (-x); } // 第x个数加k void update(int x, int k) { for (int i = x; i <= n; i += lowbit(i)) t[i] += k; } // 返回前x个数的和 int query(int x) { int res = 0; for (int i = x; i >= 1; i -= lowbit(i)) res += t[i]; return res; } int main() { ios::sync_with_stdio(false); cin.tie(0); cin >> n >> m; for (int i = 1; i <= n; i++) { cin >> a[i]; update(i, a[i]); } while (m--) { int op, x, y; cin >> op; if (op == 1) { cin >> x >> y; // a[x]+=y update(x, y); } else { cin >> x >> y; // cout sum(a[x]~a[y]) cout << query(y) - query(x - 1) << "\n"; } } return 0; } -
0
P4137 Rmq Problem / mex - 线段树做法
rt[n]是一棵权值线段树，用来记录前n个数（a[1],a[2],...,a[n]）的情况：[x,x]节点记录数字x的最后出现的位置。[l,r]节点记录数字l,l+1,...,r的最后出现位置的最小值。- 通过这个就能知道
[l,r]是否存在 “最后出现位置小于某个数” 的数字。
- 通过这个就能知道
当询问
L R到来时，是在问第L个数到第R个数（a[L],a[L+1],...,a[R]）中，最小的没出现过的数字是谁。rt[R]中记录了前R个数的情况，所有 “没出现在第L个数到第R个数中” 的数字必然是 “最后出现位置小于L” 的数字。找到满足这个条件（最后出现位置小于L）的最小的数字即可。这是在线的做法，如果把询问离线下来可以不用可持久化线段树处理。
#include <bits/stdc++.h> using namespace std; const int MAXN = 2e5 + 10; // n数组a长度,m询问个数 int n, m, maxai, minai; // a原数组，root森林里的根 int a[MAXN], root[MAXN]; int tot; struct Tree { // last: // 单点时：当前点最后一次出现的位置 // 区间时：所有最后一次出现的位置的最小值 int lc, rc, last; } tree[MAXN * 32]; // 更新，上一棵的roor是pre，当前区间[l,r]，把 x 的值改为 y int update(int pre, int l, int r, int x, int y) { int now = ++tot; if (l == r) { tree[now].last = y; return now; } // 更新链 int mid = (l + r) / 2; if (x > mid) { tree[now].lc = tree[pre].lc; tree[now].rc = update(tree[pre].rc, mid + 1, r, x, y); } else { tree[now].rc = tree[pre].rc; tree[now].lc = update(tree[pre].lc, l, mid, x, y); } tree[now].last = min(tree[tree[now].lc].last, tree[tree[now].rc].last); return now; } // 查询 u 的 [l,r] 区间上第一个last小于x的数 int query(int u, int l, int r, int x) { if (l == r) return l; if (u == 0) return l; // 左边最小的last值 int temp = tree[tree[u].lc].last; int mid = (l + r) / 2; if (temp < x) { // 左边有小于x的数就去左边找 return query(tree[u].lc, l, mid, x); } else { // 否则去右边找 return query(tree[u].rc, mid + 1, r, x); } } int main() { ios::sync_with_stdio(false); cin.tie(0); cin >> n >> m; maxai = -1; minai = 0; for (int i = 1; i <= n; i++) { cin >> a[i]; maxai = max(maxai, a[i]); } maxai++; // 建空树,0号节点做一个自循环空树 tree[0].lc = 0; tree[0].rc = 0; tree[0].last = 0; tot = 1; root[0] = 1; // 一人一棵权值线段树 for (int i = 1; i <= n; i++) { root[i] = update(root[i - 1], minai, maxai, a[i], i); } // 处理询问 while (m--) { int l, r, k; cin >> l >> r; cout << query(root[r], minai, maxai, l) << "\n"; } return 0; } -
0
树状数组2
#include <bits/stdc++.h> using namespace std; const int MAXN = 500000; int n, m; int a[MAXN + 5]; int t[MAXN + 5]; int lowbit(int x) { return x & (-x); } // 第x个数加k void update(int x, int k) { for (int i = x; i <= n; i += lowbit(i)) t[i] += k; } // 返回前x个数的和 int query(int x) { int res = 0; for (int i = x; i >= 1; i -= lowbit(i)) res += t[i]; return res; } int main() { ios::sync_with_stdio(false); cin.tie(0); cin >> n >> m; for (int i = 1; i <= n; i++) { cin >> a[i]; if (i == 1) update(i, a[i]); else update(i, a[i] - a[i - 1]); } while (m--) { int op, x, y, k; cin >> op; if (op == 1) { cin >> x >> y >> k; // a[x]~a[y] +=y update(x, k); update(y + 1, -k); } else { cin >> x; // cout a[x] cout<<query(x)<<"\n"; } } return 0; } -
-7
P3834 【模板】可持久化线段树 2
不离散化做权值线段树做法
#include <bits/stdc++.h> using namespace std; const int MAXN = 2e5 + 10; // n数组a长度,m询问个数 int n, m, maxai, minai; // a原数组，root森林里的根 int a[MAXN], root[MAXN]; int tot; struct Tree { int lc, rc, cnt; } tree[MAXN * 32]; // 更新，上一棵的roor是pre，当前区间[l,r]，要插入x int update(int pre, int l, int r, int x) { int now = ++tot; // 继承上一棵 tree[now].cnt = tree[pre].cnt + 1; if (l == r) return now; // 更新链 int mid = (l + r) / 2; if (x > mid) { tree[now].lc = tree[pre].lc; tree[now].rc = update(tree[pre].rc, mid + 1, r, x); } else { tree[now].rc = tree[pre].rc; tree[now].lc = update(tree[pre].lc, l, mid, x); } return now; } // 查询第x小值,[u,v]目标区间,[l,r]当前区间m int query(int u, int v, int l, int r, int x) { if (l == r) return l; int temp = tree[tree[v].lc].cnt - tree[tree[u].lc].cnt; int mid = (l + r) / 2; if (x <= temp) return query(tree[u].lc, tree[v].lc, l, mid, x); else return query(tree[u].rc, tree[v].rc, mid + 1, r, x - temp); } int main() { scanf("%d%d", &n, &m); maxai = -1'000'000'001; minai = 1'000'000'001; for (int i = 1; i <= n; i++) { scanf("%d", &a[i]); maxai = max(maxai, a[i]); minai = min(minai, a[i]); } // 建空树,0号节点做一个自循环空树 tree[0].lc = 0; tree[0].rc = 0; tree[0].cnt = 0; tot = 1; root[0] = 1; // 一人一棵权值线段树 for (int i = 1; i <= n; i++) root[i] = update(root[i - 1], minai, maxai, a[i]); // 处理询问 for (int i = 1; i <= m; i++) { int l, r, k; scanf("%d%d%d", &l, &r, &k); printf("%d\n", query(root[l - 1], root[r], minai, maxai, k)); } return 0; }离散化做权值线段树做法
#include <bits/stdc++.h> using namespace std; const int MAXN = 2e5 + 10; //n数组a长度,m询问个数,nn数组t长度,tot点的个数,离散化后的长度 int n, m, nn, tot; //a原数组->映射关系，t离散后的数，root森林里的根 int a[MAXN], t[MAXN], root[MAXN]; struct Tree { int l, r, cnt; } tree[MAXN * 32]; //建树[l,r] int build(int l,int r){ int now=++tot; int mid=(l+r)/2; if(l<r){ tree[now].l=build(l,mid); tree[now].r=build(mid+1,r); } return now; } //更新，上一棵的roor是pre，当前区间[l,r]，要插入x int update(int pre,int l,int r,int x){ int now=++tot; //继承上一棵 tree[now].cnt=tree[pre].cnt+1; tree[now].l=tree[pre].l; tree[now].r=tree[pre].r; //更新链 if(l<r){ int mid=(l+r)/2; if(x>mid) tree[now].r=update(tree[pre].r,mid+1,r,x); else tree[now].l=update(tree[pre].l,l,mid,x); } return now; } // 查询第x小值,[u,v]目标区间,[l,r]当前区间m int query(int u,int v,int l,int r,int x){ if(l==r) return l; int temp=tree[tree[v].l].cnt-tree[tree[u].l].cnt; int mid=(l+r)/2; if(x<=temp) return query(tree[u].l,tree[v].l,l,mid,x); else return query(tree[u].r,tree[v].r,mid+1,r,x-temp); } int main() { scanf("%d%d", &n, &m); for (int i = 1; i <= n; i++) scanf("%d", &a[i]),t[i] = a[i]; //离散化 sort(t + 1, t + n + 1); nn = unique(t + 1, t + n + 1) - t - 1; for (int i = 1; i <= n; i++) a[i] = lower_bound(t + 1, t + nn + 1, a[i]) - t; //建空树 tot=0; root[0]=build(1,nn); //一人一棵权值线段树 for(int i=1;i<=n;i++){ root[i]=update(root[i-1],1,nn,a[i]); } //处理询问 for(int i=1;i<=m;i++){ int l,r,k; scanf("%d%d%d",&l,&r,&k); printf("%d\n",t[query(root[l-1],root[r],1,nn,k)]); } return 0; }
- 1