poj 1442 Black Box treap

缘起

【1】给出了treap的板子，自然找一道题来测下板子的性能. 于是选择了 poj 1442

传送门

分析

题意就是有一个队列，对其给出两种操作 ADD GET ，顾名思义，ADD就是往队列中加元素，GET就是从队列中取元素. 下面给出了一次对队列的操作

1 ADD(3) 0 3
2 GET 1 3 3
3 ADD(1) 1 1, 3
4 GET 2 1, 3 3
5 ADD(-4) 2 -4, 1, 3
6 ADD(2) 2 -4, 1, 2, 3
7 ADD(8) 2 -4, 1, 2, 3, 8
8 ADD(-1000) 2 -1000, -4, 1, 2, 3, 8
9 GET 3 -1000, -4, 1, 2, 3, 8 1
10 GET 4 -1000, -4, 1, 2, 3, 8 2
11 ADD(2) 4 -1000, -4, 1, 2, 2, 3, 8

即第一次进行的操作是ADD, 此时i的值是0, 加入的是3.

第二次进行的操作是GET， 此时i自增1，队列是3, 所以求出排名为1的的是3

要求给出一些ADD每次要加入到数组中的数列和GET的位置。求出每次在GET是的第i大的值。一开始黑盒是空的,i也是0,后面每Get一次,i就自增一次
Sample Input
7 4//表示插入(ADD)7个数(有可能相同哦,但是每个数的绝对值不超过20亿,插入的元素个数不超过3万个)以及询问(GET)四次
3 1 -4 2 8 -1000 2//插入的7个数
1 2 6 6//表示询问(GET)依次发生在第一次ADD之后、第二次ADD之后、第六次ADD之后、第六次ADD之后（所以数字一定是非降序的）
Sample Output
3
3
1
2

显然这是裸的kth问题，直接爆treap就可以水过. 如果对treap不太了解的话，参考【1】

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
#include "stdafx.h"
#include <iostream>
#include <cstdlib>
#include <ctime>
#pragma warning(disable:4996)
//#define LOCAL
using namespace std;

const int MAX_N = 30005;

struct TreapNode
{
	int lSon,rSon,size,cnt,val,priority;
} treap[MAX_N];

int tot;

void update(int k)
{
	treap[k].size = treap[treap[k].lSon].size + treap[treap[k].rSon].size+ treap[k].cnt;
}

void leftrotate(int &k) 
{
	int r = treap[k].rSon;
	treap[k].rSon = treap[r].lSon;
	treap[r].lSon = k;
	treap[r].size = treap[k].size;
	update(k);
	k = r;
}

void rightrotate(int &k) 
{
	int l = treap[k].lSon;
	treap[k].lSon = treap[l].rSon;
	treap[l].rSon = k;
	treap[l].size = treap[k].size;
	update(k);
	k = l;
}

void insert(int &k, int x) 
{
	if (!k) 
	{
		k = ++tot;
		treap[k].cnt = treap[k].size = 1;
		treap[k].val = x;
		treap[k].lSon = treap[k].rSon = 0;
		treap[k].priority = rand();
		return;
	}
	treap[k].size++;
	if (x < treap[k].val)
	{
		insert(treap[k].lSon, x);
		if (treap[treap[k].lSon].priority < treap[k].priority)
		{
			rightrotate(k); 
		}
	}
	else if (x > treap[k].val)
	{
		insert(treap[k].rSon, x);
		if (treap[treap[k].rSon].priority <treap[k].priority) leftrotate(k);
	}
	else
	{
		treap[k].cnt++; 
	}
}

int query(int k, int x) 
{
	if (!k) return 0;  
	if (x<=treap[treap[k].lSon].size) return query(treap[k].lSon, x);
	else if (x > treap[k].cnt+ treap[treap[k].lSon].size) return query(treap[k].rSon, x - treap[k].cnt- treap[treap[k].lSon].size);
	else return treap[k].val;
}



int main()
{
#ifdef LOCAL
	freopen("d:\\data.in","r",stdin);
	freopen("d:\\my.out", "w", stdout);
#endif
	srand((int)(time(0)));
	int m,n,root = 0, kth = 0;
	scanf("%d%d",&m,&n);
	int a[MAX_N];
	for(int i =  0; i< m;scanf("%d", a+i),i++); 
	int b[MAX_N];
	for (int i = 0; i< n; scanf("%d", b+i),i++);
	bool flag = true; // i要不要+1?
	for (int i = 0, j=0; i<m;) // 这里写的比较丑
	{
		if (flag)
		{
			insert(root, a[i]);
		}
		if (i+1 == b[j])
		{
			printf("%d\n", query(root, ++kth));
			j++;
			if (j&&b[j]==b[j-1])
			{
				flag = false;
			}
			else
			{
				flag = true;
			}
		}
		else
		{
			flag = true;
		}
		if (flag)
		{
			i++;
		}
	}
	return 0;
}

ac情况

Status Accepted
Time 235ms
Memory 1096kB
Length 2107
Lang C++
Submitted 2019-06-05 18:07:37
Shared
RemoteRunId 20295190

参考

【1】https://yfsyfs.github.io/2019/06/04/Treap/