题解 P3834 【【模板】可持久化线段树 1(主席树)】

Ireliaღ

2019-08-18 15:37:19

Solution

**这里提供两个非主席树,没有其他题解提到,但是复杂度正确,或许比主席树写起来更容易的做法** ## 从原理开始 我们想要求区间第$k$小,需要用一种可持久化数据结构,版本$i$维护从$a_1$到$a_i$所有数的出现次数,这样来求出区间第$k$小。那么,“这种”数据结构需要满足哪些性质? 1. 资瓷可持久化(废话,题目在那) 2. 资瓷查询全局第$k$小(显然) 3. **不同版本树的形态相似**(为性质$4$提供条件) 4. **可以从两个版本的树根开始同时在树上走路,并在“相同地位”的节点上对$size$进行作差,来得到指定区间内的信息。**(重点!) 那么,我们~~很容易~~根据以上性质想到以下数据结构 * 值域线段树(标准主席树做法) * 二叉搜索树(可以看普通平衡树P3369) * 0-1字典树(普通平衡树P3369中有几篇题解) * Leafy Search Tree(也有人叫它Finger Tree,但好像是个~~美丽的~~误会,按照原理完全可以实现,但是我太菜没写明白) ## 本题解法 可持久化值域线段树(主席树)做法很多题解都写了,这里不再多讲。重点讲下面的两种做法。 ### 可持久化二叉搜索树 因为二叉搜索树满足**中序遍历即有序序列**的性质,所以我们可以使用可持久化BST来解决静态区间第$k$小的问题,只需要在递归不同版本的“相同地位”节点时,对两个$size$作差即可。 代码如下 ```cpp // luogu-judger-enable-o2 // luogu-judger-enable-o2 #include <iostream> using std::cin; using std::cout; const int MAXN = 2e5 + 5; int n, m; int a[MAXN]; struct Node{ int val, cnt, siz; Node *ch[2]; Node() {} Node(int val) : val(val) { cnt = 1; siz = 1; ch[0] = ch[1] = NULL; } }pool[MAXN << 5]; int ncnt = 0; Node *NewNode(int val) { pool[ncnt] = Node(val); return &pool[ncnt++]; } Node *NewNode(void) { return &pool[ncnt++]; } Node *rt[MAXN]; void Update(Node *now) { now->siz = now->cnt + (now->ch[0] ? now->ch[0]->siz : 0) + (now->ch[1] ? now->ch[1]->siz : 0); } Node *Copy(Node *now) { Node *ret = NewNode(); *ret = *now; return ret; } void Insert(Node *&now, int k) { if (!now) { now = NewNode(k); return; } now = Copy(now); if (k < now->val) Insert(now->ch[0], k); else if (k == now->val) now->cnt++; else Insert(now->ch[1], k); Update(now); } int Kth(Node *now1, Node *now2, int k) { int ls1 = ((now1 && now1->ch[0]) ? now1->ch[0]->siz : 0); int ls2 = ((now2 && now2->ch[0]) ? now2->ch[0]->siz : 0); int ls = ls2 - ls1; int ncnt = (now2 ? now2->cnt : 0) - (now1 ? now1->cnt : 0); if (k <= ls) return Kth((now1 ? now1->ch[0] : NULL), (now2 ? now2->ch[0] : NULL), k); else if (k <= ls + ncnt) return now2->val; else return Kth((now1 ? now1->ch[1] : NULL), (now2 ? now2->ch[1] : NULL), k - ls - ncnt); } void Init() { cin >> n >> m; for (int i = 1; i <= n; i++) cin >> a[i]; } void Work() { for (int i = 1; i <= n; i++) { rt[i] = rt[i - 1]; Insert(rt[i], a[i]); } int x, y, k; for (int i = 1; i <= m; i++) { cin >> x >> y >> k; cout << Kth(rt[x - 1], rt[y], k) << "\n"; } } int main() { std::ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); Init(); Work(); return 0; } ``` 虽然这份代码可以切掉本题,~~并且跑的比很多主席树要快得多~~,但是由于我们需要满足性质$3$,无法对BST做出平衡措施,所以**出题人可以通过恶意构造单调增/减的序列把可持久化BST的时间和空间卡成$n^2$**。 然而,介于绝大多数人求静态区间第$k$小都用主席树,出题人很难想到卡BST,所以我到现在没因为使用BST代替主席树翻车过。 时间复杂度单次查询$O(log(n))$,预处理$O(nlog(n))$(非恶意数据) ### 可持久化0-1字典树 0-1字典树,顾名思义,把二进制数当做字符串存入字典树中,这样通过维护节点的$size$,可以求出全局第$k$小,**并且跑的比绝大多数平衡树都要快**。这样,性质已经满足,我们可以通过可持久化来求出区间第$k$小。 代码如下 ```cpp // luogu-judger-enable-o2 #include <iostream> using std::cin; using std::cout; typedef unsigned int U; const int MAXN = 2e5 + 5; int n, m; int a[MAXN]; struct Node{ int siz; Node *ch[2]; }pool[MAXN << 6]; Node *NewNode() { static int cnt = 0; pool[cnt].siz = 0; pool[cnt].ch[0] = NULL; pool[cnt].ch[1] = NULL; return &pool[cnt++]; } Node *rt[MAXN]; void Update(Node *now) { now->siz = (now->ch[0] ? now->ch[0]->siz : 0) + (now->ch[1] ? now->ch[1]->siz : 0); } Node *Copy(Node *now) { Node *ret = NewNode(); *ret = *now; return ret; } void Insert(Node *&now, U num, int base) {//base为父边的数位 if (!now) now = NewNode(); else now = Copy(now); if (base == 0) { now->siz++; return; } int f = (num & (1U << base - 1)) ? 1 : 0; Insert(now->ch[f], num, base - 1); Update(now); } U Kth(Node *now1, Node *now2, int k, U num, int base) {//num为收集下来的数字 if (base == 0) return num; int ls1 = ((now1 && now1->ch[0]) ? now1->ch[0]->siz : 0); int ls2 = ((now2 && now2->ch[0]) ? now2->ch[0]->siz : 0); int ls = ls2 - ls1; if (k <= ls) return Kth(now1 ? now1->ch[0] : NULL, now2 ? now2->ch[0] : NULL, k, num, base - 1); else return Kth(now1 ? now1->ch[1] : NULL, now2 ? now2->ch[1] : NULL, k - ls, num + (1U << base - 1), base - 1); } void Init() { cin >> n >> m; for (int i = 1; i <= n; i++) cin >> a[i]; } void Work() { rt[0] = new Node(); for (int i = 1; i <= n; i++) { rt[i] = rt[i - 1]; Insert(rt[i], a[i], 32); } int x, y, k; for (int i = 1; i <= m; i++) { cin >> x >> y >> k; cout << Kth(rt[x - 1], rt[y], k, 0, 32) << "\n"; } } int main() { std::ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); Init(); Work(); return 0; } ``` 时间复杂度稳定每次$O(log(maxnum))$,预处理$O(nlog(maxnum))$ 这里我比较推荐利用可持久化Trie来解决静态区间第$k$小以及类似问题,因为Trie的复杂度最优,并且可以解决最大异或和等其他问题。