Irelia

Irelia

逝去的是刀锋,不变的是意志

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

posted on 2019-08-18 15:37:19 | under 题解 |

这里提供两个非主席树,没有其他题解提到,但是复杂度正确,或许比主席树写起来更容易的做法

从原理开始

我们想要求区间第 $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$ 作差即可。

代码如下

// 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$ 小。

代码如下

// 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的复杂度最优,并且可以解决最大异或和等其他问题。