洛谷 P3850 [TJOI2007]书架-白红宇

洛谷 P3850 [TJOI2007]书架

阅读量：4485 次

发布时间：2019-06-08

本文共 3004 字，大约阅读时间需要 10 分钟。

洛谷 P3850 [TJOI2007]书架

Description

Knuth 先生家里有个精致的书架，书架上有 N 本书，如今他想学到更多的知识，于是又买来了 M 本不同的新书。现在他要把新买的书依次插入到书架中，他已经把每本书要插入的位置标记好了，并且相应的将它们放好。由于 Knuth 年龄已大，过几天他已经记不清某些位置上放的到底是什么书了，请问你能帮助他吗？

Input

输入文件的第一行为整数 N，接下来 N 行分别是书架上依次放着的 N 本书的书名（书名由不含空格的字符串构成，长度不超过 10）。下一行将要输入一个整数 M，接下来的 M 行分别为这本书的书名和要插入的位置。下一行将要输入一个整数 Q，接下来共有 Q 次询问，每行都是一个整数表示询问的位置。（书架上位置的编号从 0 开始）

Output

输出 Q 行，每行对应着相应查询位置的书名。

Sample Input

3MathAlgorithmProgram2Picture 2System 13013

Sample Output

MathSystemPicture

Data Size

Q 次询问依次为 0, 1, 3 位置的书，所以答案为：Math、System、Picture

对于 30% 的数据，1⩽N⩽100, 1⩽M⩽10^3, 1⩽Q⩽10^3

对于 100% 的数据，1⩽N⩽200, 1⩽M⩽10^5, 1⩽Q⩽10^4

对于 100%的数据都符合题目中所描述的限制关系，数据保证每次插入的位置均不超过当时书架上书的数量，而且保证 Q 次查询中的每个位置上一定有书。

题解：

第一次用fhq-treap做题，值得纪念。

首先考虑用treap怎么做这题？因为treap树的形态不能改变，所以每次插入元素时就得把插入元素后面所以的元素都往后挪一格。肯定会T的。那么这时fhq-treap的优势就体现出来了！fhq-treap能通过分裂和合并改变树的形态！

fhq-treap有两种分裂方式：按权分裂和按大小分裂。

按权分裂的话fhq-treap就等价于treap，按大小分裂的话fhq-treap就等价于splay（不严谨的说）

我们来讲讲按大小分裂。split(root, pos, x, y)表示把前pos个元素分到x树，之后的元素分到y树。那么假如说我要操作[l, r]这个区间，我就可以写成split(root, r, x, z), split(x, l - 1, x, y)，那么y树就是所要操作的区间。至于split怎么写，大致是如果一个点左子树size + 1 <= pos，就分到x树，否则分到y树，然后递归下去。强烈推荐split函数模拟一遍，你会发现它实际上取的是中序遍历的前pos个元素。又因为BST的中序遍历等价于排序后的序列，所以就等价于取了前pos个元素。
- 注意，按大小分裂时，我们fhq-treap里的权值其实是序列下标！
- 注意，按大小分裂时，我们fhq-treap里的权值其实是序列下标！
- 注意，按大小分裂时，我们fhq-treap里的权值其实是序列下标！

因为只有这样，才能保证中序遍历前pos个元素就是代表着原序列前pos个位置！

#include 
    
     #include 
     
      #include 
      
       #include 
       #define N 100000 + 200 + 5using namespace std;struct T {int l, r, val, dat, size;} t[N];int n, m, q, dex, root, tot, x, y, z;map
        
          mp;int New(int val){    t[++tot].val = val;    t[tot].dat = rand();    t[tot].size = 1;    return tot;}void up(int p) {t[p].size = t[t[p].l].size + t[t[p].r].size + 1;}void split(int p, int size, int &x, int &y){    if(!p) {x = y = 0; return;}    if(t[t[p].l].size + 1 <= size)    {        x = p;        split(t[p].r, size - t[t[p].l].size - 1, t[p].r, y);    }    else    {        y = p;        split(t[p].l, size, x, t[p].l);    }    up(p);}int merge(int x, int y){    if(!x || !y) return x + y;    if(t[x].dat > t[y].dat)    {        t[x].r = merge(t[x].r, y);        up(x); return x;    }    else    {        t[y].l = merge(x, t[y].l);        up(y); return y;    }}void insert(int val, int pos){    split(root, pos - 1, x, y);    root = merge(merge(x, New(val)), y);}string valOfRank(int rank){    split(root, rank, x, z);    split(x, rank - 1, x, y);    string ans = mp[t[y].val];    root = merge(merge(x, y), z);    return ans;}int main(){    cin >> n;    for(int i = 1; i <= n; i++)    {        string t; cin >> t;        mp[++dex] = t, insert(dex, i);    }    cin >> m;    for(int i = 1; i <= m; i++)    {        string t; cin >> t;        int pos; scanf("%d", &pos);        mp[++dex] = t, insert(dex, pos + 1);    }    cin >> q;    for(int i = 1; i <= q; i++)    {        int pos; scanf("%d", &pos);        cout << valOfRank(pos + 1) << endl;    }    return 0;}