BZOJ2761 [JLOI2011] 不重复数字

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <algorithm>
 4 #include <cstring>
 5 #define rep(i,l,r) for(int i=l; i<=r; i++)
 6 #define clr(x,y) memset(x,y,sizeof(x))
 7 using namespace std;
 8 const int INF = 0x3f3f3f3f;
 9 const int maxn = 50010;
10 struct node{
11     int v,l,r,rnd;
12 }t[maxn];
13 int T,n,x,tot,root;
14 bool flag;
15 inline int read(){
16     int ans = 0, f = 1;
17     char c = getchar();
18     while (!isdigit(c)){
19         if (c == ‘-‘) f = -1;
20         c = getchar();
21     }
22     while (isdigit(c)){
23         ans = ans * 10 + c - ‘0‘;
24         c = getchar();
25     }
26     return ans * f;
27 }
28 void rotl(int &w){
29     int k = t[w].r; t[w].r = t[k].l; t[k].l = w; w = k;
30 }
31 void rotr(int &w){
32     int k = t[w].l; t[w].l = t[k].r; t[k].r = w; w = k;
33 }
34 void insert(int x,int &w){
35     if (!w){
36         w = ++tot; t[w].v = x;
37         t[w].rnd = rand(); t[w].l = t[w].r = 0; return;
38     }
39     if (t[w].v == x){
40         flag = 1;
41         return;
42     }
43     else if (x < t[w].v){
44         insert(x,t[w].l);
45         if (t[t[w].l].rnd < t[w].rnd) rotr(w);
46     }
47     else{
48         insert(x,t[w].r);
49         if (t[t[w].r].rnd < t[w].rnd) rotl(w);
50     }
51 }
52 void work(){
53     n = read(); root = tot = 0;
54     flag = 0; x = read(); insert(x,root); if (!flag) printf("%d",x);
55     rep(i,2,n){
56         flag = 0; x = read(); insert(x,root); 
57         if (!flag) printf(" %d",x);
58     }
59     printf("\n");
60 }
61 int main(){
62     T = read();
63     while (T--) work();
64     return 0;
65 }