第一次寫接近5KB的代碼，故發帖留念.
- generate M：如果集合原來沒有M，則添加M；否則，不操作
- remove M：如果集合存在M，則刪除M；否則，不操作
- query：查出集合各元素之間最小間隔
其中，M （1， 100000）
1
#include <cstdio>
2#include <cstring>
3#include <queue>
4using namespace std;
5
6const int SIZE = 100200;
7
8//線段樹
9struct STREE
10
{
11
int m_left, m_right; //區間的左右端值
12 int m_start, m_end;
13 int m_lChild, m_rChild;
14
}stree[SIZE * 2];
15
16int gMin, gMax, arr[SIZE][2], arr_dif[SIZE], N;
17bool mark[SIZE];
18
19//保存間隔
20bool cmp(const int& a, const int& b)
21{
22 return ( a > b );
23}
24priority_queue<int, vector<int>, greater<int> > PQ;
25
26void Build(int& index, const int& s, const int& e)
27{
28 stree[index].m_start = s;
29 stree[index].m_end = e;
30 stree[index].m_left = stree[index].m_right = -1;
31 if ( s == e )
32
{
33 return;
34
}
35
36 int mid = (s + e) >> 1;
37 int t = index;
38
39 index++;
40 stree[t].m_lChild = index;
41 Build( index, s, mid );
42 index++;
43 stree[t].m_rChild = index;
44 Build( index, mid + 1, e );
45
46}
47void Insert(const int& index, const int& num)
48{
49 if ( gMin < stree[index].m_left && stree[index].m_left < num )
50 gMin = stree[index].m_left;
51 if ( (gMax > stree[index].m_right || gMax == -1) && stree[index].m_right > num )
52 gMax = stree[index].m_right;
53
54 if ( stree[index].m_start == stree[index].m_end )
55 {
56 stree[index].m_left = stree[index].m_right = num;
57 return;
58 }
59
60 int mid = (stree[index].m_start + stree[index].m_end) >> 1;
61 int t;
62
63 if ( num <= mid )
64 {
65 t = stree[index].m_rChild;
66 if ( gMax > stree[t].m_left && stree[t].m_left != -1 )
67 gMax = stree[t].m_left;
68
69 Insert( stree[index].m_lChild, num );
70 }
71 else {
72 t = stree[index].m_lChild;
73 if ( gMin < stree[t].m_right && stree[t].m_right != -1 )
74 gMin = stree[t].m_right;
75 Insert( stree[index].m_rChild, num );
76 }
77
78 if ( stree[index].m_left > num || stree[index].m_left == -1 )
79 stree[index].m_left = num;
80 if ( stree[index].m_right < num )
81 stree[index].m_right = num;
82}
83
84void Delete(const int& index, const int& num)
85{
86 if ( stree[index].m_left == num )
87 {
88 if ( arr[num][0] >= stree[index].m_start )
89 stree[index].m_left = arr[num][0];
90 else if ( arr[num][1] <= stree[index].m_end )
91 stree[index].m_left = arr[num][1];
92 else
93 stree[index].m_left = -1;
94 }
95 if ( stree[index].m_right == num )
96 {
97 if ( arr[num][1] <= stree[index].m_end )
98 stree[index].m_right = arr[num][1];
99 else if ( arr[num][0] >= stree[index].m_start )
100 stree[index].m_right = arr[num][0];
101 else
102 stree[index].m_right = -1;
103 }
104
105 if ( stree[index].m_start == stree[index].m_end )
106 {
107 stree[index].m_left = stree[index].m_right = -1;
108 return;
109 }
110
111 int mid = (stree[index].m_start + stree[index].m_end) >> 1;
112
113 if ( num <= mid )
114 {
115 Delete( stree[index].m_lChild, num );
116 }
117 else {
118 Delete( stree[index].m_rChild, num );
119 }
120}
121
122void Init()
123{
124 memset(arr, 0xff, sizeof(arr));
125 memset(mark, 0, sizeof(mark));
126 memset(arr_dif, 0, sizeof(arr_dif));
127
128 for (int i = 0; i < SIZE * 2; ++i )
129 stree[i].m_left = stree[i].m_right = -1;
130
131 N = 0;
132
133 while ( !PQ.empty() )
134 PQ.pop();
135}
136
137void Remove(const int& num)
138{
139 if ( mark[num] )
140 {
141 Delete( 0, num );
142
143 if ( arr[num][0] != -1 )
144 {
145 arr_dif[num - arr[num][0]]++;
146 if ( arr[num][1] != -1 )
147 arr[arr[num][1]][0] = arr[num][0];
148 }
149 else if ( arr[num][1] != -1 )
150 arr[arr[num][1]][0] = -1;
151 if ( arr[num][1] != -1 )
152 {
153 arr_dif[arr[num][1] - num]++;
154 if ( arr[num][0] != -1 )
155 arr[arr[num][0]][1] = arr[num][1];
156
157 }
158 else if ( arr[num][0] != -1 )
159 arr[arr[num][0]][1] = -1;
160
161 if ( arr[num][0] != -1 && arr[num][1] != -1 )
162 PQ.push( arr[num][1] - arr[num][0] );
163
164 arr[num][0] = arr[num][1] = -1;
165 mark[num] = false;
166 N--;
167 }
168}
169
170void Generate(const int& num)
171{
172 if ( !mark[num] )
173 {
174 gMin = gMax = -1;
175 Insert( 0, num );
176
177 if ( gMin > num )
178 gMin = -1;
179 if ( gMax < num )
180 gMax = -1;
181
182 if ( gMin != -1 )
183 {
184 PQ.push( num - gMin );
185 arr[gMin][1] = num;
186 }
187 if ( gMax != -1 )
188 {
189 PQ.push( gMax - num );
190 arr[gMax][0] = num;
191 }
192
193 arr[num][0] = gMin;
194 arr[num][1] = gMax;
195
196 if ( gMin != -1 && gMax != -1 )
197 arr_dif[gMax - gMin]++;
198 mark[num] = true;
199 N++;
200 }
201}
202
203void Query()
204{
205 if ( N < 2 )
206 {
207 printf("-1\n");
208 return;
209 }
210 int i, t;
211
212 t = PQ.top();
213 while ( arr_dif[t] != 0 )
214 {
215 for ( i = 0; i < arr_dif[t]; ++i )
216 PQ.pop();
217 arr_dif[t] = 0;
218 t = PQ.top();
219 }
220
221 printf("%d\n", t);
222}
223
224int main()
225{
226// freopen("1.txt", "r", stdin);
227
228 int t, n, i, num;
229 char str[20];
230 t = 0;
231 Build( t, 1, 100000 );
232
233 scanf("%d", &t);
234
235 while ( t-- )
236 {
237 Init();
238 scanf("%d", &n);
239
240 for ( i = 0; i < n; ++i )
241 {
242 scanf("%s", str);
243
244 if ( str[0] == 'q' )
245 {
246 Query();
247 }
248 else if ( str[0] == 'r' )
249 {
250 scanf("%d", &num);
251 Remove( num );
252 }
253 else {
254 scanf("%d", &num);
255 Generate( num );
256 }
257 }
258 printf("\n");
259 }
260 return 0;
261}