poj 3481 SBT Double Queue

缘起

【1】中讲解了SBT的模板. 这里自然需要用oj检验一下板子的性能. 所以选择了 poj 3481 来练手.

传送门

分析

题意就是一家银行的服务软件将会收到3种指令

  1. 1 K P, 意思是将编号为K的客户以P的优先级加入等待队列（下简称队列），其中K,P都是正整数，K<=10^6, P<=10^7
  2. 2, 意思是服务掉整个队列中优先级最高的客户，并将此客户从队列中移除
  3. 3, 意思是服务掉整个队列中优先级最低的客户, 并将此客户从队列中移除.

加入的客户不会重复（不论是K还是P）. 然后要求在指令是2或者3的时候，输出此次服务的客户的K值.

算法的瓶颈显然是快速求出最大值和最小值. 所以SBT登场. 此题是SBT的裸题. 关于SBT的详解，参见【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
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
#include "stdafx.h"
#include <iostream>
#pragma warning(disable:4996)
#define LOCAL
using namespace std;

const int N = 1000000+5;

struct SBTNode
{
	int left, right, size, k, p; // k是客户的编号, p是客户的优先级
} sbt[N];

int tot, root;

void leftrotate(int &x)
{
	int r = sbt[x].right; 
	sbt[r].size=sbt[x].size;
	sbt[x].size = sbt[sbt[r].left].size+ sbt[sbt[x].left].size+1;
	sbt[x].right = sbt[r].left;
	sbt[r].left = x;
	x = r;
}

void rightrotate(int &x)
{
	int l = sbt[x].left;
	sbt[l].size=sbt[x].size;
	sbt[x].size = sbt[sbt[l].right].size+ sbt[sbt[x].right].size+1;
	sbt[x].left = sbt[l].right;
	sbt[l].right = x;
	x = l; 
}

void maintain(int &x, bool flag)
{ 
	if (!flag)
	{
		if (sbt[sbt[x].left].left && sbt[sbt[sbt[x].left].left].size > sbt[sbt[x].right].size)
		{
			rightrotate(x); 
		}
		else if(sbt[sbt[x].left].right && sbt[sbt[sbt[x].left].right].size > sbt[sbt[x].right].size)
		{
			leftrotate(sbt[x].left); 
			rightrotate(x); 
		}
		else return; 
	}
	else
	{
		if (sbt[sbt[sbt[x].right].right].size > sbt[sbt[x].left].size)
		{
			leftrotate(x);
		}
		else if(sbt[sbt[sbt[x].right].left].size > sbt[sbt[x].left].size)
		{
			rightrotate(sbt[x].right);
			leftrotate(x); 
		}
		else return;
	}
	maintain(sbt[x].right, true); 
	maintain(sbt[x].left, false);
	maintain(x, true);
	maintain(x, false);
}

void insert(int &x, int k, int p) 
{
	if (!x) 
	{
		x = ++tot;
		sbt[x].left = 0;
		sbt[x].right = 0;
		sbt[x].size = 1;
		sbt[x].k = k;
		sbt[x].p = p;
		return;
	}
	sbt[x].size++;
	if (p < sbt[x].p) 
	{
		insert(sbt[x].left, k, p);
	}
	else 
	{
		insert(sbt[x].right, k, p);
	}
	maintain(x, p >= sbt[x].p); 
}

int getmin(int &x) // 这里和【1】中给的板子略有变通，因为题目需要找到最值之后删除节点
{
	int y;
	if (sbt[x].left)
	{
		int t = x;
		while(sbt[t].left)
		{
			y = t;
			t = sbt[t].left;
		}
		sbt[y].left = sbt[t].right;
		return sbt[t].k;
	}
	int t = sbt[x].k;
	x = sbt[x].right;
	return t;
}

int getmax(int &x)
{
	int y;
	if (sbt[x].right) // 如果x有右子树
	{
		int t = x; // x不需要动（传入的x是根节点）
		while(sbt[t].right)
		{
			y = t;
			t = sbt[t].right;
		}
		sbt[y].right = sbt[t].left; // sbt[x]没有右子树了
		return sbt[t].k;
	}
	int t = sbt[x].k; // 如果没有的话, x就是最大节点, 直接删掉sbt[x]即可
	x = sbt[x].left;
	return t;
}

int main()
{
#ifdef LOCAL
	freopen("d:\\data.in","r",stdin);
	//freopen("d:\\my.out", "w", stdout);
#endif
	int code, k,p;
	while(~scanf("%d", &code) && code)
	{
		if (code == 1)
		{
			scanf("%d%d", &k, &p);
			insert(root, k, p);
		}
		else if (code == 2)
		{
			if (!sbt[root].size) puts("0"); // 如果是空队列, 打印0
			else
			{
				printf("%d\n", getmax(root));
			}
		}
		else
		{
			if (!tot) puts("0");
			else
			{
				printf("%d\n", getmin(root));
			}
		}
	}
	return 0;
}

ac情况

Status Accepted
Time 204ms
Memory 1736kB
Length 2571
Lang C++
Submitted 2019-06-05 11:29:51
Shared
RemoteRunId 20294313

参考

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