欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

洛谷P1138 第k小整数

程序员文章站 2022-03-03 09:07:41
...

我偏不用sort

Treap好题啊

看到只有一个人写Treap,而且写的不清楚,那我就来详细地写一下,方便新人学习


第(-1)部分:前置知识

二叉查找树:满足左子树的数据都比根节点小,右子树的数据都比根节点大的二叉树

堆:满足子树中的数据均比根节点大的树,或是满足子树中的数据均比根节点小的树


第零部分:Treap简介 & 程序开头

Treap=Tree+Heap,又称“树堆”。

这是因为Treap维护的数据满足二叉查找树的性质,而随机权值满足堆的性质。

#include <bits/stdc++.h> // 万能头文件

using namespace std;

第一部分:定义Treap

代码中的root代表平衡树的树根,cnt是存Treap的时候用。

结构体treap存储的是一个节点。结构体中的cnt表示某个数字的出现个数,size表示以这个节点为根的子树的大小,val存的是当前数值,rnd是随机权值。son存左右孩子,下标为0时为左儿子,为1时是右儿子。

int cnt, root;

struct treap {
    int cnt, size, val, rnd, son[2];
}t[10010];

第二部分:维护子树大小

可以模仿线段树的操作(如果你不知道线段树是什么也没关系)。一个以x为根的二叉树的大小,应该等于以它左儿子为根的子树大小+右儿子为根的子树大小+1。为什么要+1呢?因为还有x这个节点嘛,也要算上去。

但在Treap里,+1的地方应该改为+t[x].size。为什么呢?

这是因为Treap把值相同的数据合并成了一个,t[x].size记录了这个数据的出现次数。

x为子树的根节点。以后的代码中x都是这个意思,下面将不再赘述。

void upd(int x) {
    t[x].size = t[t[x].son[0]].size + t[t[x].son[1]].size + t[x].cnt;
}

第三部分:旋转

旋转这个比较难理解

旋转这个操作,就是当Treap不能同时满足二叉查找树和堆的性质时,我们做一次旋转,让Treap的结构改变,但存储的数据依然满足二叉查找树和堆的性质。

这个东西可以手动推一下,大家应该都能理解吧(

代码中d=0时左旋,d=1时右旋。

void rotate(int &x, int d) {
    int tmp = t[x].son[d];
    t[x].son[d] = t[tmp].son[d ^ 1];
    t[tmp].son[d ^ 1] = x;
    upd(x); upd(tmp); x = tmp;
}

第四部分:新建节点

这时候cnt就有用处了呢~

看函数内第一行:cnt++,新建出一个空节点

第二行的操作是给这个新建节点它需要维护的数据

第三行是给这个新建节点随机权值

第四行的操作意思是维护的这个数据目前只出现了一次

第五行是因为这个新建节点没有左右子树,所以大小赋值为1

返回值可以让我们知道这个新建节点在t数组中的位置

int newnode(int val) {
    cnt++;
    t[cnt].val = val;
    t[cnt].rnd = rand();
    t[cnt].cnt = 1;
    t[cnt].size = 1;
    return cnt;
}

第五部分:建树

先建一个根节点,维护数据-INF(这里INF取了0x7fffffff,相当于十进制的2147483647,是int最大能存储的值)

再建一个节点,维护数据INF。INF显然比-INF大,所以放在根节点的右儿子处。

最后是建树的标准操作:更新树大小

这里维护的-INF和INF都是虚拟节点,不是我们真正要维护的,为的是其他Treap操作更加方便(似乎也没方便到哪儿去)

void build() {
    root = newnode(-0x7fffffff); 
    t[root].son[1] = newnode(0x7fffffff);
    upd(root);
}

第六部分:插入一个数据

我们可以拿着这个数据从根节点往叶子跑。由于是二叉搜索树,所以不用遍历整个树,同时也不能随便找一个地方就插上了。

我们在往叶子跑的时候,把途中经过的节点的大小都加上1,因为新增了一个元素。

如果我们在往叶子跑的中途遇到了与这个数据相等的节点的时候,我们直接把这个数据的出现次数:节点的cnt值加一。

如果我们的数据跑到了叶子上面,那就……叶上叶(滑稽)。当然,经过的那个叶子结点就变成了非叶子节点。当我们这是后要新建节点的时候,就要进行newnode操作新建节点、进行rotate操作维护……总之模拟即可。

void insert(int &x, int val) {
    if(!x) {
        x = newnode(val);
        return ;
    }
    t[x].size++;
    if(t[x].val == val)t[x].cnt++;
    else {
        int d = t[x].val < val;
        insert(t[x].son[d], val);
        if(t[x].rnd > t[t[x].son[d]].rnd) rotate(x, d);
    }
}

第七部分:求第k小

求第k小很好说吧

如果k小于或等于左子树大小,答案是左子树中的第k小

否则,如果k小于或等于左子树大小+根节点数据出现次数,则答案为根节点数据

否则,答案为右子树中的第(k-根节点数据出现次数-左子树大小)小

其中还有个细节,因为我们之前的建树操作建的是两个虚拟节点,所以我们查询的时候k要+1,因为第1小被-INF占掉了

递归即可。

int kth(int x, int rnk) {
    if(!x) return 0x7fffffff;
    if(rnk <= t[t[x].son[0]].size) {
        return kth(t[x].son[0], rnk);
    } else {
        if(rnk <= t[t[x].son[0]].size + t[x].cnt) {
            return t[x].val;
        } else {
            return kth(t[x].son[1], rnk - t[x].cnt - t[t[x].son[0]].size);
        }
    }
}

第八部分:主程序的开端以及初始化

Treap的部分基本说完了,现在来看主程序吧。

先定义一个a数组并清零(后面会讲为什么),定义m并初始化为0(后面会讲)

定义n,k和题面意义相同。

还有随机数初始化,搞随机权值用的。

int main() {
    int n, k, m = 0, a[30010];
    memset(a, 0, sizeof(a));
    cin >> n >> k;
    build();
    srand(time(NULL));

第九部分:映射

我之前说过不用sort,不用unique,于是用了把数值映射到数组里的方法。a数组就是做这个用的。

当我们遇到一个数据data,就把a[data]++,表示data这个数出现了一次。这里没有定义data[10010],省下了一个数组。

数据的取值范围为0~30000,我们暴力跑一边,如果这个数出现了,m++,在平衡树里插入节点。

大家应该都明白了,我们的m存储的是不同的正整数的数量。

如果m<k,因为相同的数只计算一次,就没有第k大,输出"NO RESULT";否则,直接输出第k大。

    for(int i = 1; i <= n; i++) {
        int data;
        cin >> data;
        a[data]++;
    }
    for(int i = 1; i <= 30000; i++) {
        if(a[i]) {
            m++;
            insert(root, i);
        }
    }
    if(m < k) cout << "NO RESULT" << endl;
    else cout << kth(root, k + 1) << endl;
    return 0;
}

跑的其实挺快(34ms, 948kb

当然,这道题还不是Treap能做的所有事情。Treap还可以查询一个数的排名、删除一个数、查询一个数的前驱后继……有兴趣的可以做一下【模板】普通平衡树

这个题解就结束了呢~