成都网站建设 四川冠辰,什么是网络营销系统,汽修厂做网站有什么好处,wordpress怎样对接dz目录 1 介绍2 训练 1 介绍
本专题用来记录可持久化数据结构相关的题目。
本专题主要讲如下两类数据结构的可持久化#xff1a;
trie的可持久化线段树的可持久化#xff0c;即主席树
可持久化的前提#xff1a;本身的拓扑的结构不变。
解决什么类型的问题#xff1a;可… 目录 1 介绍2 训练 1 介绍
本专题用来记录可持久化数据结构相关的题目。
本专题主要讲如下两类数据结构的可持久化
trie的可持久化线段树的可持久化即主席树
可持久化的前提本身的拓扑的结构不变。
解决什么类型的问题可以保存下来数据结构的所有历史版本。 核心思想只记录每一个版本与前一个版本不同的结点。
2 训练
题目1256最大异或和
C代码如下
#include cstdio
#include cstring
#include iostream
#include algorithmusing namespace std;const int N 600010, M N * 25;int n, m;
int s[N];
int tr[M][2], max_id[M];
int root[N], idx;void insert(int i, int k, int p, int q) {if (k 0) {max_id[q] i;return;}int v s[i] k 1;if (p) tr[q][v^1] tr[p][v^1];tr[q][v] idx;insert(i, k-1, tr[p][v], tr[q][v]);max_id[q] max(max_id[tr[q][0]], max_id[tr[q][1]]);
}int query(int root, int C, int L) {int p root;for (int i 23; i 0; --i) {int v C i 1;if (max_id[tr[p][v^1]] L) p tr[p][v^1];else p tr[p][v];}return C ^ s[max_id[p]];
}int main() {scanf(%d%d, n, m);max_id[0] -1;root[0] idx;insert(0, 23, 0, root[0]);for (int i 1; i n; i) {int x;scanf(%d, x);s[i] s[i-1] ^ x;root[i] idx;insert(i, 23, root[i-1], root[i]);}char op[2];int l, r, x;while (m--) {scanf(%s, op);if (*op A) {scanf(%d, x);n;s[n] s[n-1] ^ x;root[n] idx;insert(n, 23, root[n-1], root[n]);} else {scanf(%d%d%d, l, r, x);printf(%d\n, query(root[r-1], s[n]^x, l-1));}}return 0;
}题目2255第K小数
C代码如下
#include cstdio
#include cstring
#include iostream
#include algorithm
#include vectorusing namespace std;const int N 100010, M 10010;int n, m;
int a[N];
vectorint nums;struct Node {int l, r;int cnt;
}tr[N * 4 N * 17];int root[N], idx;int find(int x) {return lower_bound(nums.begin(), nums.end(), x) - nums.begin();
}int build(int l, int r) {int p idx;if (l r) return p;int mid l r 1;tr[p].l build(l, mid), tr[p].r build(mid 1, r);return p;
}int insert(int p, int l, int r, int x) {int q idx;tr[q] tr[p];if (l r) {tr[q].cnt;return q;}int mid l r 1;if (x mid) tr[q].l insert(tr[p].l, l, mid, x);else tr[q].r insert(tr[p].r, mid 1, r, x);tr[q].cnt tr[tr[q].l].cnt tr[tr[q].r].cnt;return q;
}int query(int q, int p, int l, int r, int k) {if (l r) return r;int cnt tr[tr[q].l].cnt - tr[tr[p].l].cnt;int mid l r 1;if (k cnt) return query(tr[q].l, tr[p].l, l, mid, k);else return query(tr[q].r, tr[p].r, mid 1, r, k - cnt);
}int main() {scanf(%d%d, n, m);for (int i 1; i n; i) {scanf(%d, a[i]);nums.push_back(a[i]);}sort(nums.begin(), nums.end());nums.erase(unique(nums.begin(), nums.end()), nums.end());root[0] build(0, nums.size() - 1);for (int i 1; i n; i) {root[i] insert(root[i-1], 0, nums.size() - 1, find(a[i]));}while (m--) {int l, r, k;scanf(%d%d%d, l, r, k);printf(%d\n, nums[query(root[r], root[l-1], 0, nums.size() - 1, k)]);}return 0;
}
