主席树裸题 POJ - 2104【K-th Number】

https://cn.vjudge.net/contest/304073#problem/A

题意

给定 n 个数和 m 次询问， 每次查询 [l, r] 区间内第 K 小的数是多少。

分析

这很主席树。主席树，名字源于发明者 HJT （%%%）。主席树算是线段树的变种，被称为可持久化线段树，可以保存和查询更新的历史版本，每一次都会生成一棵新的权值线段树（指线段树的叶子节点保存的是当前值的个数）。

当然我们不可能每次都重新建立新树，通过观察可以发现，每次进行单点更新的时候，发生变化的只有从 根节点 到 当前叶子节点 这一条链上的节点。利用这样的性质，对于每次的更新，我们只需要建立一个新的根节点，然后递归需要新建（更新）的节点。

划分树也可以解决区间第k大问题，但划分树不支持修改，主席树可以（用树状数组维护）。

我们只要建立[1, i]（ i 是 1-n 之间的所有值）的所有树，每当询问 [l, r] 时，只要用 [1, r] 的树减去 [1, l-1] 的树，再找第k小就可以了。

最初只要建立一个空树，也就是不必每个节点都建立一个空树。插入元素时，我们不去修改任何的结点，而是返回一个新的树。因为每个节点都不会被修改，所以可以不断的重复用，因此插入操作的复杂度为 \(O(log(n))\) 。总的复杂度为 \(O((n+m)log(n)log(new\_n))\) 。

代码

裸题的板子还是写的思路清晰一点好。

#include <map> #include <set> #include <list> #include <cmath> #include <ctime> #include <deque> #include <stack> #include <queue> #include <bitset> #include <cctype> #include <cstdio> #include <vector> #include <string> #include <cstdlib> #include <cstring> #include <fstream> #include <iomanip> #include <numeric> #include <iostream> #include <algorithm> using namespace std; typedef long long ll; typedef unsigned long long ull; const double PI = acos(-1.0); const double eps = 1e-6; const int inf = 0x3f3f3f3f; const int mod = 1e9 + 7; const int maxn = 1e5 + 5; int n, m, cnt, x, y, k; int root[maxn], a[maxn]; // root保存的是历史版本根节点 vector<int> v; // 保存去重后的数组 struct node { int l, r, sum; } T[maxn * 40]; // 线段树*4、主席树*40 int getid(int x) { // 获取每次更新的节点的“位置” return lower_bound(v.begin(), v.end(), x) - v.begin() + 1; } void update(int l, int r, int &x, int y, int pos) { T[++cnt] = T[y]; // 继承上一棵树 T[cnt].sum ++; // 权值 x = cnt; if (l == r) return; int mid = (l + r) / 2; if (mid >= pos) update(l, mid, T[x].l, T[y].l, pos); else update(mid + 1, r, T[x].r, T[y].r, pos); } int query(int l, int r, int x, int y, int k) { if (l == r) return l; int mid = (l + r) / 2; int sum = T[T[y].l].sum - T[T[x].l].sum; // 根据所求进行修改 if (sum >= k) return query(l, mid, T[x].l, T[y].l, k); else return query(mid + 1, r, T[x].r, T[y].r, k - sum); } int main() { scanf("%d%d", &n, &m); for (int i = 1; i <= n; i++) { scanf("%d", &a[i]); v.push_back(a[i]); } sort(v.begin(), v.end()); v.erase(unique(v.begin(), v.end()), v.end()); // 去重 int new_n = (int)v.size(); for (int i = 1; i <= n; i++) { update(1, new_n, root[i], root[i - 1], getid(a[i])); } for (int i = 1; i <= m; i++) { scanf("%d%d%d", &x, &y, &k); printf("%d\n", v[query(1, new_n, root[x - 1], root[y], k) - 1]); } return 0; }

HDU - 4417【Super Mario】 主席树 + 二分

https://cn.vjudge.net/contest/304073#problem/F

题意

t 组数据，给定 n 个数和 m 次询问， 每次查询 [l, r] 区间内有多少数比 x 小。

分析

这题的代码和上一题几乎一致，既然需要寻找多少数比 x 小，那么只要在给定的区间内二分找第 k 小的值 temp （满足 temp_max <= x），所得到的就是小于该值的数的数量。

ps：区间端点为 [0, n-1]。

代码

#include <map> #include <set> #include <list> #include <cmath> #include <ctime> #include <deque> #include <stack> #include <queue> #include <bitset> #include <cctype> #include <cstdio> #include <vector> #include <string> #include <cstdlib> #include <cstring> #include <fstream> #include <iomanip> #include <numeric> #include <iostream> #include <algorithm> using namespace std; typedef long long ll; typedef unsigned long long ull; const double PI = acos(-1.0); const double eps = 1e-6; const int inf = 0x3f3f3f3f; const int mod = 1e9 + 7; const int maxn = 1e5 + 5; int n, m, cnt, new_n; int a[maxn]; int root[maxn]; vector<int> v; struct node { int l, r, sum; }T[maxn*40]; void init() { cnt = 0; memset(root, 0, sizeof(root)); for(int i = 0; i < 40*n; i++) { T[i].l = T[i].r = T[i].sum = 0; } } int getid(int x) { return lower_bound(v.begin(), v.end(), x) - v.begin() + 1; } void update(int l, int r, int &x, int y, int pos) { T[++cnt] = T[y]; T[cnt].sum ++; x = cnt; if(l == r) { return ; } int mid = (l+r) / 2; if(mid >= pos) { update(l, mid, T[x].l, T[y].l, pos); } else { update(mid+1, r, T[x].r, T[y].r, pos); } } int query(int l, int r, int x, int y, int k) { if(l == r) { return l; } int mid = (l+r) / 2; int sum = T[T[y].l].sum - T[T[x].l].sum; if(sum >= k) { return query(l, mid, T[x].l, T[y].l, k); } else { return query(mid+1, r, T[x].r, T[y].r, k-sum); } } int solve(int x, int y, int z) { int l = x; int r = y; int res = -1; while(l <= r) { int mid = (l+r) / 2; int temp = v[query(1, new_n, root[x-1], root[y], mid-x)-1]; if(temp <= z) { l = mid + 1; res = max(res, mid-x); } else { r = mid - 1; } } if(v[query(1, new_n, root[x-1], root[y], y-x+1)-1] <= z) { return y-x+1; } return res; } int main() { int t, cas = 1; scanf("%d", &t); while(t--) { init(); scanf("%d%d", &n, &m); for(int i = 1; i <= n; i++) { scanf("%d", &a[i]); v.push_back(a[i]); } sort(v.begin(), v.end()); v.erase(unique(v.begin(), v.end()), v.end()); new_n = (int)v.size(); for(int i = 1; i <= n; i++) { update(1, new_n, root[i], root[i-1], getid(a[i])); } printf("Case %d:\n", cas++); for(int i = 1; i <= m; i++) { int x, y, z; scanf("%d%d%d", &x, &y, &z); int ans = solve(x+1, y+1, z); printf("%d\n", ans); } } return 0; }

转载于:https://www.cnblogs.com/Decray/p/10927674.html