HDU 3726 Graph and Queries treap树

时间:2024-04-04 11:34:51

题目来源:HDU 3726 Graph and Queries

题意:见白书

思路:刚学treap 參考白皮书

#include <cstdio>
#include <cstring>
#include <cstdlib>
using namespace std; struct Node
{
Node *ch[2];
int r;
int v;
int s;
Node(int v): v(v) {
ch[0] = ch[1] = NULL; r = rand(); s = 1;
}
bool operator < (const Node& rhs) const{
return r < rhs.r;
}
int cmp(int x) const{
if(x == v) return -1;
return x < v ? 0 : 1;
}
void maintain(){
s = 1;
if(ch[0] != NULL) s += ch[0]->s;
if(ch[1] != NULL) s += ch[1]->s;
}
}; void rotate(Node* &o, int d){
Node* k = o->ch[d^1]; o->ch[d^1] = k->ch[d]; k->ch[d] = o;
o->maintain(); k->maintain(); o = k;
} void insert(Node* &o, int x){
if(o == NULL){
o = new Node(x);
}
else{
int d = (x < o->v ? 0 : 1);
insert(o->ch[d], x);
if(o->ch[d] > o) rotate(o, d^1);
}
o->maintain();
//printf("--------+%d\n", o->s);
} void remove(Node* &o, int x){
int d = o->cmp(x);
if(d == -1){
Node* u = o;
if(o->ch[0] != NULL && o->ch[1] != NULL){
int d2 = o->ch[0] > o->ch[1] ? 1 : 0;
rotate(o, d2); remove(o->ch[d2], x);
}
else{
if(o->ch[0] == NULL) o = o->ch[1];
else o = o->ch[0];
delete u;
}
}
else
remove(o->ch[d], x);
if(o != NULL) o->maintain();
} const int maxn = 20010;
const int maxc = 500010;
int n, m, w[maxn], from[maxn*3], to[maxn*3], removed[maxn*3];
int f[maxn]; Node* root[maxn]; struct Command
{
char type;
int x, p;
Command(){}
Command(char type, int x, int p): type(type), x(x), p(p) { }
}commands[maxc]; int find(int x)
{
if(x != f[x])
return f[x] = find(f[x]);
return f[x];
}
int kth(Node* o, int k){
if(o == NULL || k <= 0 || k > o->s)
return 0;
int s = (o->ch[1] == NULL ? 0 : o->ch[1]->s);
if(k == s+1) return o->v;
else if(k <= s) return kth(o->ch[1], k);
else return kth(o->ch[0], k-s-1);
} void mergeto(Node* &src, Node* &dest){ if(src->ch[0] != NULL) mergeto(src->ch[0], dest);
if(src->ch[1] != NULL) mergeto(src->ch[1], dest);
insert(dest, src->v);
delete src;
src = NULL;
} void add_edge(int x){
int u = find(from[x]), v = find(to[x]);
//printf("-/++++%d %d\n", u, v);
if(u != v){
if(root[u]->s > root[v]->s){
f[v] = u;
//printf("----%d %d\n", root[v]->s, root[u]->s);
mergeto(root[v], root[u]);
//printf("----%d\n", root[u]->s);
}
else{
f[u] = v;
//printf("----%d %d\n", root[u]->s, root[v]->s);
mergeto(root[u], root[v]);
//printf("++++%d\n", root[v]->s);
}
}
} void removetree(Node* &x){
if(x->ch[0] != NULL) removetree(x->ch[0]);
if(x->ch[1] != NULL) removetree(x->ch[1]);
delete x;
x = NULL;
} int query_cnt;
long long query_tol; void query(int x, int k){
query_cnt++;
//printf("%d %d\n", root[find(x)]->s, kth(root[find(x)], k));
query_tol += kth(root[find(x)], k);
} void change_weight(int x, int v){
int u = find(x);
remove(root[u], w[x]);
insert(root[u], v);
w[x] = v;
}
int main()
{
int kase = 0;
while(scanf("%d %d", &n, &m) && (n||m))
{
for(int i = 1; i <= n; i++)
scanf("%d", &w[i]);
for(int i = 1; i <= m; i++)
scanf("%d %d", &from[i], &to[i]);
memset(removed, 0, sizeof(removed));
int c = 0;
while(1)
{
char type[2];
int x, p = 0, v = 0;
scanf("%s", type);
if(type[0] == 'E')
break;
scanf("%d", &x);
if(type[0] == 'D')
removed[x] = 1;
if(type[0] == 'Q')
scanf("%d", &p);
if(type[0] == 'C')
{
scanf("%d", &v);
p = w[x];
w[x] = v;
}
commands[c++] = Command(type[0], x, p);
} for(int i = 1; i <= n; i++)
{
f[i] = i;
if(root[i] != NULL)
removetree(root[i]);
root[i] = new Node(w[i]);
//printf("******%d\n", root[i]->s);
}
for(int i = 1; i <= m; i++)
if(!removed[i])
{
add_edge(i);
//puts("gh");
}
query_tol = query_cnt = 0;
for(int i = c-1; i >= 0; i--){
if(commands[i].type == 'D')
add_edge(commands[i].x);
if(commands[i].type == 'Q')
query(commands[i].x, commands[i].p);
if(commands[i].type == 'C')
change_weight(commands[i].x, commands[i].p);
}
printf("Case %d: %.6lf\n", ++kase, query_tol/(double)query_cnt);
}
return 0;
}