【模板】可持久化线段树 1
传送门
题目描述
输入格式
输出格式
样例
输入 #1
5 10
59 46 14 87 41
0 2 1
0 1 1 14
0 1 1 57
0 1 1 88
4 2 4
0 2 5
0 2 4
4 2 1
2 2 2
1 1 5 91
输出 #1
59
87
41
87
88
46
数据范围
代码
#include<bits/stdc++.h> using namespace std; const int N = 1000010; struct node { int l, r; int v; } tr[N << 5]; int n, m; int a[N]; int root[N << 5], idx; void build(int &p, int l, int r) { p = ++idx; if(l == r) { tr[p].v = a[l]; return ; } int mid = l + r >> 1; build(tr[p].l, l, mid), build(tr[p].r, mid + 1, r); } void modify(int &p, int q, int l, int r, int x, int v) { p = ++idx; tr[p] = tr[q]; if(l == r) { tr[p].v = v; return ; } int mid = l + r >> 1; if(x <= mid) modify(tr[p].l, tr[q].l, l, mid, x, v); else modify(tr[p].r, tr[q].r, mid + 1, r, x, v); } int query(int p, int l, int r, int x) { if(l == r) return tr[p].v; int mid = l + r >> 1; if(x <= mid) return query(tr[p].l, l, mid, x); return query(tr[p].r, mid + 1, r, x); } void solve() { cin >> n >> m; for (int i = 1; i <= n; i++) cin >> a[i]; build(root[0], 1, n); int id, op, loc, val; for (int i = 1; i <= m; i++) { cin >> id >> op >> loc; if(op == 1) { cin >> val; modify(root[i], root[id], 1, n, loc, val); } else { root[i] = ++idx; tr[root[i]] = tr[root[id]]; cout << query(root[id], 1, n, loc) << endl; } } } signed main() { cin.tie(0), cout.tie(0), ios_base::sync_with_stdio(false); int _ = 1; while(_--) { solve(); } return 0; }
【模板】可持久化线段树 2
传送门
题目描述
输入格式
输出格式
样例
输入 #1
5 5
25957 6405 15770 26287 26465
2 2 1
3 4 1
4 5 1
1 2 2
4 4 1
输出 #1
6405
15770
26287
25957
26287
数据范围
代码
#include <iostream> #include <cstring> #include <algorithm> using namespace std; const int N = 200010; int n, m; int a[N], b[N]; struct node { int l, r; int v; } tr[N << 5]; int root[N], idx; void pushup(int p) { tr[p].v = tr[tr[p].l].v + tr[tr[p].r].v; } void build(int &p, int l, int r) { p = ++idx; if(l == r) return ; int mid = l + r >> 1; build(tr[p].l, l, mid), build(tr[p].r, mid + 1, r); } void modify(int &p, int q, int l, int r, int x, int v) { p = ++idx; tr[p] = tr[q]; if(l == r) { tr[p].v += v; return ; } int mid = l + r >> 1; if(x <= mid) modify(tr[p].l, tr[q].l, l, mid, x, v); else modify(tr[p].r, tr[q].r, mid + 1, r, x, v); pushup(p); } int query(int p, int q, int l, int r, int k) { if(l == r) return r; // 这是当前这段区间，r树-（l-1）树所维护的区间的左树值的个数 int cnt = tr[tr[p].l].v - tr[tr[q].l].v; int mid = l + r >> 1; if(k <= cnt) return query(tr[p].l, tr[q].l, l, mid, k); return query(tr[p].r, tr[q].r, mid + 1, r, k - cnt); } int main() { cin >> n >> m; for (int i = 1; i <= n; i++) cin >> a[i], b[i] = a[i]; sort(a + 1, a + 1 + n); int len = unique(a + 1, a + 1 + n) - a - 1; for (int i = 1; i <= n; i++) b[i] = lower_bound(a + 1, a + 1 + len, b[i]) - a; build(root[0], 1, len); for (int i = 1; i <= n; i++) modify(root[i], root[i - 1], 1, len, b[i], 1); while(m--) { int l, r, k; cin >> l >> r >> k; cout << a[query(root[r], root[l - 1], 1, len, k)] << endl; } return 0; }
