UVa 1479 (Treap 名次树) Graph and Queries

这题写起来真累。。

名次树就是多了一个附加信息记录以该节点为根的树的总结点的个数，由于BST的性质再根据这个附加信息，我们可以很容易找到这棵树中第k大的值是多少。

所以在这道题中用一棵名次树来维护一个连通分量。

由于图中添边比较方便，用并查集来表示连通分量就好了，但是删边不太容易实现。

所以，先把所有的边删去，然后逆序执行命令。当然，C命令也要发生一些变化，比如说顺序的情况是从a变成b，那么逆序执行的话应该就是从b变成a。

最后两棵树的合并就是启发式合并，把节点数少的数并到节点数多的数里去。

  1 #include <cstdio>
  2 #include <cstring>
  3 #include <cstdlib>
  4 using namespace std;
  5 
  6 struct Node
  7 {
  8     Node* ch[2];
  9     int r, v, s;
 10     Node(int v):v(v) { ch[0] = ch[1] = NULL; s = 1; r = rand(); }
 11     int cmp(int x)
 12     {
 13         if(x == v) return -1;
 14         return x < v ? 0 : 1;
 15     }
 16     void maintain()
 17     {
 18         s = 1;
 19         if(ch[0] != NULL) s += ch[0]->s;
 20         if(ch[1] != NULL) s += ch[1]->s;
 21     }
 22 };
 23 
 24 void rotate(Node* &o, int d)
 25 {
 26     Node* k = o->ch[d^1]; o->ch[d^1] = k->ch[d]; k->ch[d] = o;
 27     o->maintain(); k->maintain(); o = k;
 28 }
 29 
 30 void insert(Node* &o, int x)
 31 {
 32     if(o == NULL) o = new Node(x);
 33     else
 34     {
 35         int d = x < o->v ? 0 : 1;
 36         insert(o->ch[d], x); if(o->ch[d]->r > o->r) rotate(o, d^1);
 37     }
 38     o->maintain();
 39 }
 40 
 41 void remove(Node* &o, int x)
 42 {
 43     int d = o->cmp(x);
 44     if(d == -1)
 45     {
 46         if(o->ch[0] == NULL) o = o->ch[1];
 47         else if(o->ch[1] == NULL) o = o->ch[0];
 48         else
 49         {
 50             int d2 = o->ch[0]->r < o->ch[1]->r ? 0 : 1;
 51             rotate(o, d2); remove(o->ch[d2], x);
 52         }
 53     }
 54     else remove(o->ch[d], x);
 55     if(o != NULL) o->maintain();
 56 }
 57 
 58 const int maxc = 500000 + 10;
 59 struct Command
 60 {
 61     char type;
 62     int x, p;
 63 }cmd[maxc];
 64 
 65 const int maxn = 20000 + 10;
 66 const int maxm = 60000 + 10;
 67 
 68 int weight[maxn], from[maxm], to[maxm];
 69 bool removed[maxm];
 70 int n, m, query_cnt;
 71 long long query_tot;
 72 
 73 int pa[maxn];
 74 int findset(int x) { return x == pa[x] ? x : pa[x] = findset(pa[x]); }
 75 
 76 Node* root[maxn];
 77 
 78 int kth(Node* o, int k)
 79 {
 80     if(o == NULL || k <= 0 || k > o->s) return 0;
 81     int s = o->ch[1] == NULL ? 0 : o->ch[1]->s;
 82     if(k == s + 1) return o->v;
 83     if(k <= s) return kth(o->ch[1], k);
 84     return kth(o->ch[0], k - s - 1);
 85 }
 86 
 87 void MergeTo(Node* &src, Node* &dest)
 88 {
 89     if(src->ch[0] != NULL) MergeTo(src->ch[0], dest);
 90     if(src->ch[1] != NULL) MergeTo(src->ch[1], dest);
 91     insert(dest, src->v);
 92     delete src;
 93     src = NULL;
 94 }
 95 
 96 void RemoveTree(Node* &o)
 97 {
 98     if(o->ch[0] != NULL) RemoveTree(o->ch[0]);
 99     if(o->ch[1] != NULL) RemoveTree(o->ch[1]);
100     delete o;
101     o = NULL;
102 }
103 
104 void AddEdge(int x)
105 {
106     int u = findset(from[x]);
107     int v = findset(to[x]);
108     if(u != v)
109     {
110         if(root[u]->s < root[v]->s) { pa[u] = v; MergeTo(root[u], root[v]); }
111         else { pa[v] = u; MergeTo(root[v], root[u]); }
112     }
113 }
114 
115 void Query(int x, int k)
116 {
117     query_cnt++;
118     query_tot += kth(root[findset(x)], k);
119 }
120 
121 void ChangeWeight(int x, int v)
122 {
123     int u = findset(x);
124     remove(root[u], weight[x]);
125     insert(root[u], v);
126     weight[x] = v;
127 }
128 
129 int main()
130 {
131     //freopen("in.txt", "r", stdin);
132 
133     int kase = 0;
134     while(scanf("%d%d", &n, &m) == 2 && n)
135     {
136         for(int i = 1; i <= n; i++) scanf("%d", &weight[i]);
137         for(int i = 1; i <= m; i++) scanf("%d%d", &from[i], &to[i]);
138         memset(removed, false, sizeof(removed));
139 
140         int c = 0;
141         for(;;)
142         {
143             char type[5]; scanf("%s", type);
144             if(type[0] == 'E') break;
145             int x, p = 0, v = 0;
146             scanf("%d", &x);
147             if(type[0] == 'D') removed[x] = true;
148             if(type[0] == 'Q') scanf("%d", &p);
149             if(type[0] == 'C')
150             {
151                 scanf("%d", &v);
152                 p = weight[x];
153                 weight[x] = v;
154             }
155             cmd[c++] = (Command) { type[0], x, p };
156         }
157 
158         for(int i = 1; i <= n; i++)
159         {
160             pa[i] = i; if(root[i] != NULL) RemoveTree(root[i]);
161             root[i] = new Node(weight[i]);
162         }
163         for(int i = 1; i <= m; i++) if(!removed[i]) AddEdge(i);
164 
165         query_cnt = query_tot = 0;
166         for(int i = c - 1; i >= 0; i--)
167         {
168             char type = cmd[i].type;
169             int x = cmd[i].x, p = cmd[i].p;
170             if(type == 'D') AddEdge(x);
171             if(type == 'Q') Query(x, p);
172             if(type == 'C') ChangeWeight(x, p);
173         }
174         printf("Case %d: %.6f
", ++kase, query_tot / (double)query_cnt);
175     }
176 
177     return 0;
178 }

代码君