2019.1.30更新:加入了$LateX$,简化了$Split$函数

这题我觉得就是个无旋Treap的板子,为什么没有无旋Treap的题解

无旋$Treap$随便搞搞就过了这道题,我来发一个题解

前置知识:无旋Treap

无旋$Treap$的详细介绍我博客里面有,这里先简单介绍一下。无旋$Treap$的主要操作是分裂和合并,分裂时可以分裂出任意大小的子树,这样,它就成了除了$Splay$之外,支持区间指定位置插入的常用数据结构。

关于本题

这道题是让我们指定位置插入和单点查询,那么我们二叉搜索树的性质由原序列顺序保持,这样中序遍历就是原序列。

操作(1):插入

加入我们想把一个元素插入后,让它在序列的第$k$个位置,那么我们分裂出大小为$k-1$的子树,把它与新结点合并,再和剩余部分合并,就$OK$了,代码如下

void Insert(Node *x, int k) {
    Node *t1, *t2;
    Split(root, k - 1, t1, t2);//分出k - 1个元素存在t1中,剩余存在t2中
    root = Merge(t1, Merge(x, t2));//新结点插进去,原样拼回去
}

操作(2):单点查询

既然它按照原序列保持二叉搜索树性质,那么我们就可以把它当做查询第$k$小。先拆出大小为$k - 1$的子树,再在剩余部分拆出大小为$1$的子树,取这个结点的$val$,再原样拼回去,代码如下

string FindKth(int pos) {
    Node *lt, *tmp;
    Split(root, pos - 1, lt, tmp);//第一次拆
    Node *rt, *midt;
    Split(tmp, 1, midt, rt);//第二次拆
    string res = midt->name;//存答案
    root = Merge(lt, Merge(midt, rt));//拼回去
    return res;
}

完整代码

// luogu-judger-enable-o2
#include <string>
#include <iostream>

const int MAXN = 205;
const int MAXM = 1e5 + 5;
const int MAXQ = 1e4 + 5;

using std::cin;
using std::cout;
using std::string;

int Rand() {
   static int seed = 39444;
   return seed = (((seed ^ 810872ll) + 1433223ll) * 19260817ll) % 2147483647;
}

struct Node{
   int key, siz;
   string name;
   Node *child[2];
   Node(string name):name(name), key(Rand()), siz(1) {
       child[0] = child[1] = NULL;
   }
   Node():key(Rand()), siz(1) {
       child[0] = child[1] = NULL;
   }
};

Node *root = NULL;

//Node book[MAXN];

int n, m, q;

void Update(Node *now) {
   now->siz = 1;
   now->siz += now->child[0] ? now->child[0]->siz : 0;
   now->siz += now->child[1] ? now->child[1]->siz : 0;
}

void Split(Node *now, int k, Node *&t1, Node *&t2) {
   if (!now) {
       t1 = t2 = NULL; return;
   } 
   if (!k) {
       t1 = NULL; t2 = now; return;
   }
   if (k >= now->size) {
       t1 = now; t2 = NULL; return;
   }
   int ls = now->child[0] ? now->child[0]->size : 0;
   if (ls >= k) {
       Node *temp;
       Split(now->child[0], k, t1, temp);
       t2 = now; t2->child[0] = temp; 
       t2->Update(); return;
   } else {
       Node *temp;
       Split(now->child[1], k - ls - 1, temp, t2);
       t1 = now; t1->child[1] = temp;
       t1->Update(); return;
   }
}

Node *Merge(Node *a, Node *b) {
   if (!a) return b;
   if (!b) return a;
   if (a->key < b->key) {
       a->child[1] = Merge(a->child[1], b);
       Update(a);
       return a;
   } else {
       b->child[0] = Merge(a, b->child[0]);
       Update(b);
       return b;
   }
}

void Insert(Node *x, int k) {
   Node *t1, *t2;
   Split(root, k - 1, t1, t2);
   root = Merge(t1, Merge(x, t2));
}

string FindKth(int pos) {
   Node *lt, *tmp;
   Split(root, pos - 1, lt, tmp);
   Node *rt, *midt;
   Split(tmp, 1, midt, rt);
   string res = midt->name;
   root = Merge(lt, Merge(midt, rt));
   return res;
}

int main() {
   cin >> n;
   string temp;
//    for (int i = 1; i <= n; i++) cin >> (book + i)->name;
//    for (int i = 1; i <= n; i++) Insert(book + i, i);
   for (int i = 1; i <= n; i++) {
       cin >> temp;
       Insert(new Node(temp), i);
   }
   cin >> m;
   int pos;
   for (int i = 1; i <= m; i++) {
       cin >> temp >> pos; pos++;
       Insert(new Node(temp), pos);
   }
   cin >> q;
   for (int i = 1; i <= q; i++) {
       cin >> pos; pos++;
       cout << FindKth(pos) << '\n';
   }
   return 0;
}