【HDOJ】3726 Graph and Queries

Treap的基础题目，Treap是个挺不错的数据结构。
  1 /*  */
  2 #include <iostream>
  3 #include <string>
  4 #include <map>
  5 #include <queue>
  6 #include <set>
  7 #include <stack>
  8 #include <vector>
  9 #include <deque>
 10 #include <algorithm>
 11 #include <cstdio>
 12 #include <cmath>
 13 #include <ctime>
 14 #include <cstring>
 15 #include <climits>
 16 #include <cctype>
 17 #include <cassert>
 18 #include <functional>
 19 #include <iterator>
 20 #include <iomanip>
 21 using namespace std;
 22 //#pragma comment(linker,"/STACK:102400000,1024000")
 23 
 24 #define sti                set<int>
 25 #define stpii            set<pair<int, int> >
 26 #define mpii            map<int,int>
 27 #define vi                vector<int>
 28 #define pii                pair<int,int>
 29 #define vpii            vector<pair<int,int> >
 30 #define rep(i, a, n)     for (int i=a;i<n;++i)
 31 #define per(i, a, n)     for (int i=n-1;i>=a;--i)
 32 #define clr                clear
 33 #define pb                 push_back
 34 #define mp                 make_pair
 35 #define fir                first
 36 #define sec                second
 37 #define all(x)             (x).begin(),(x).end()
 38 #define SZ(x)             ((int)(x).size())
 39 #define lson            l, mid, rt<<1
 40 #define rson            mid+1, r, rt<<1|1
 41 
 42 typedef struct {
 43     char c;
 44     int x, y;
 45 } Cmd;
 46 
 47 typedef struct Node {
 48     Node* ch[2];
 49     int r, v, s;
 50     
 51     Node() {}
 52     
 53     Node(int v_) {
 54         ch[0] = ch[1] = NULL;
 55         r = rand();
 56         v = v_;
 57         s = 1;
 58     }
 59     
 60     friend bool operator<(const Node& a, const Node& b) {
 61         return a.r < b.r;
 62     }
 63     
 64     int cmp(int x) const {
 65         if (x == v)    return -1;
 66         return x<v ? 0:1;
 67     }
 68     
 69     void maintain() {
 70         s = 1;
 71         if (ch[0] != NULL)    s += ch[0]->s;
 72         if (ch[1] != NULL)    s += ch[1]->s;
 73     }
 74 
 75 } Node;
 76 
 77 void rotate(Node*& o, int d) {
 78     Node* k = o->ch[d^1];
 79     o->ch[d^1] = k->ch[d];
 80     k->ch[d] = o;
 81     o->maintain();
 82     k->maintain();
 83     o = k;
 84 }
 85 
 86 void insert(Node*& o, int x) {
 87     if (o == NULL) {
 88         o = new Node(x);
 89     } else {
 90         int d = x<o->v ? 0:1;
 91         insert(o->ch[d], x);
 92         if (o->ch[d]->r > o->r)
 93             rotate(o, d^1);
 94     }
 95     o->maintain();
 96 }
 97 
 98 void remove(Node*& o, int x) {
 99     int d = o->cmp(x);
100     
101     if (d == -1) {
102         Node* u = o;
103         if (o->ch[0]!=NULL && o->ch[1]!=NULL) {
104             int d2 = o->ch[0]->r > o->ch[1]->r ? 1:0;
105             rotate(o, d2);
106             remove(o->ch[d2], x);
107         } else {
108             if (o->ch[0] == NULL)
109                 o = o->ch[1];
110             else
111                 o = o->ch[0];
112             delete u;
113         }
114     } else {
115         remove(o->ch[d], x);
116     }
117     if (o != NULL)
118         o->maintain();
119 }
120 
121 const int maxc = 5e5+5;
122 const int maxn = 2e4+5;
123 const int maxm = 6e4+5;
124 Cmd cmd[maxc];
125 Node* rt[maxn];
126 int W[maxn], pre[maxn];
127 int U[maxm], V[maxm];
128 bool mark[maxm];
129 
130 int find(int x) {
131     if (x == pre[x])
132         return x;
133     return pre[x] = find(pre[x]);
134 }
135 
136 void removetree(Node*& x) {
137     if (x->ch[0] != NULL)    removetree(x->ch[0]);
138     if (x->ch[1] != NULL)    removetree(x->ch[1]);
139     delete x;
140     x = NULL;
141 }
142 
143 void mergeto(Node*& src, Node*& des) {
144     if (src->ch[0] != NULL)    mergeto(src->ch[0], des);
145     if (src->ch[1] != NULL)    mergeto(src->ch[1], des);
146     insert(des, src->v);
147     delete src;
148     src = NULL;
149 }
150 
151 void addEdge(int k) {
152     int u = U[k], v = V[k];
153     int fu = find(u), fv = find(v);
154     
155     if (fu != fv) {
156         if (rt[fu]->s < rt[fv]->s) {
157             pre[fu] = fv;
158             mergeto(rt[fu], rt[fv]);
159         } else {
160             pre[fv] = fu;
161             mergeto(rt[fv], rt[fu]);
162         }
163     }
164 }
165 
166 int kth(Node* o, int k) {
167     if (o==NULL || k<=0 || k>o->s)
168         return 0;
169     
170     int s = o->ch[1]==NULL ? 0:o->ch[1]->s;
171     if (k == s+1)
172         return o->v;
173     else if (k <= s)
174         return kth(o->ch[1], k);
175     else
176         return kth(o->ch[0], k-s-1);
177 }
178 
179 int main() {
180     ios::sync_with_stdio(false);
181     #ifndef ONLINE_JUDGE
182         freopen("data.in", "r", stdin);
183         freopen("data.out", "w", stdout);
184     #endif
185     
186     int tt = 0;
187     int n, m, nc;
188     int x, y;
189     char s[3];
190     __int64 tot, ans;
191     
192     while (scanf("%d %d",&n,&m)!=EOF && (n||m)) {
193         rep(i, 1, n+1)
194             scanf("%d", &W[i]);
195         rep(i, 1, m+1)
196             scanf("%d %d", &U[i], &V[i]);
197             
198         memset(mark, false, sizeof(mark));
199         nc = 0;
200         while (scanf("%s", s)!=EOF && s[0]!='E') {
201             cmd[nc].c = s[0];
202             if (s[0] == 'D') {
203                 scanf("%d", &x);
204                 cmd[nc].x = x;
205                 mark[x] = true;
206             } else if (s[0] == 'Q') {
207                 scanf("%d %d", &x, &y);
208                 cmd[nc].x = x;
209                 cmd[nc].y = y;
210             } else if (s[0] == 'C') {
211                 scanf("%d %d", &x, &y);
212                 cmd[nc].x = x;
213                 cmd[nc].y = W[x];
214                 W[x] = y;
215             }
216             ++nc;
217         }
218         
219         
220         rep(i, 1, n+1) {
221             pre[i] = i;
222             if (rt[i] != NULL)
223                 removetree(rt[i]);
224             rt[i] = new Node(W[i]);
225         }
226         
227         rep(i, 1, m+1) {
228             if (!mark[i])
229                 addEdge(i);
230         }
231         
232         ans = tot = 0;
233         per(i, 0, nc) {
234             if (cmd[i].c == 'D') {
235                 addEdge(cmd[i].x);
236             } else if (cmd[i].c == 'Q') {
237                 int fx = find(cmd[i].x);
238                 ++tot;
239                 ans += kth(rt[fx], cmd[i].y);
240             } else if (cmd[i].c == 'C') {
241                 int fx = find(cmd[i].x);
242                 remove(rt[fx], W[cmd[i].x]);
243                 insert(rt[fx], cmd[i].y);
244                 W[cmd[i].x] = cmd[i].y;
245             }
246         }
247         printf("Case %d: %.06lf
", ++tt, 1.0*ans/tot);
248     }
249     
250     #ifndef ONLINE_JUDGE
251         printf("time = %d.
", (int)clock());
252     #endif
253     
254     return 0;
255 }