在线转离线。。先构建出最终的图，然后逆着处理。。不过有几个要注意的地方。。。答案超int，要用long long。。逆着处理的时候C操作要反着操作。。求第k大的时候，k可能是0或负数，也可能超过集合元素个数。。
#include #include #include #include #include #include #include #include #include #include #include #include #include #define maxn 20005 #define eps 1e-10 #define mod 1000000009 #define INF 99999999 #define lowbit(x) (x&(-x)) //#define lson o<<1, L, mid //#define rson o<<1 | 1, mid+1, R typedef long long LL; //typedef int LL; using namespace std; int value[maxn], n, m; char s[100]; struct Edge { int u, v, done; }edges[60005]; struct opr { int kk, x, y; }op[1000005]; int opp, cnt; LL ans; int f[maxn], num[maxn]; struct node { int key, v, s; struct node *ch[2]; int cmp(int x) const { if(x == v) return -1; return x s + ch[1]->s + 1; } }*null, *root[maxn]; void read(void) { opp = 0; for(int i = 1; i <= n; i++) scanf("%d", &value[i]); for(int i = 1; i <= m; i++) scanf("%d%d", &edges[i].u, &edges[i].v), edges[i].dOne= 0; while(scanf("%s", s)!=EOF) { if(s[0] == 'E') break; if(s[0] == 'D') op[opp].kk = 0, scanf("%d", &op[opp++].x), edges[op[opp-1].x].dOne= 1; if(s[0] == 'Q') op[opp].kk = 1, scanf("%d%d", &op[opp].x, &op[opp].y), opp++; if(s[0] == 'C') op[opp].kk = 2, scanf("%d%d", &op[opp].x, &op[opp].y), swap(op[opp].y, value[op[opp].x]), opp++; } } void init(void) { int i; ans = cnt = 0; for(i = 0; i s = null->v = 0; for(i = 0; i <= n; i++) { root[i] = new node; root[i] = null; } } int find(int x) { return f[x] == x ? f[x] : find(f[x]); } 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; o->key = rand(), o->v = x; o->s = 1, o->ch[0] = o->ch[1] = null; return; } int d = x v ? 0 : 1; insert(o->ch[d], x); if(o->key ch[d]->key) rotate(o, d^1); o->maintain(); } void remove(node* &o, int x) { int d = o->cmp(x); if(d == -1) { if(o->ch[0] != null && o->ch[1] != null) { int d2 = (o->ch[0]->key > o->ch[1]->key ? 1 : 0); rotate(o, d2), remove(o->ch[d2], x); } else { node *u = o; 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(); } int kth(node *o, int k) { if(o == null || o->s ch[1]->s >= k) return kth(o->ch[1], k); if(o->ch[1]->s + 1 == k) return o->v; return kth(o->ch[0], k - o->ch[1]->s - 1); } void debug(node* o) { printf("FSDF %d\n", o->v); if(o->ch[0] != null) debug(o->ch[0]); if(o->ch[1] != null) debug(o->ch[1]); } void removetree(node* &o, node* &p) { if(o == null) return; if(o->ch[0] != null) removetree(o->ch[0], p); if(o->ch[1] != null) removetree(o->ch[1], p); insert(p, o->v); delete o; } void updata(int a, int v) { int aa = find(a); remove(root[aa], value[a]); value[a] = v; insert(root[aa], value[a]); } void query(int a, int k) { int aa = find(a); ans += kth(root[aa], k); } void merge(int a, int b) { int aa = find(a), bb = find(b); if(aa == bb) return; if(num[aa] > num[bb]) { removetree(root[bb], root[aa]); f[bb] = aa, num[aa] += num[bb], num[bb] = 0; root[bb] = null; } else { removetree(root[aa], root[bb]); f[aa] = bb, num[bb] += num[aa], num[aa] = 0; root[aa] = null; } } void work(void) { int i, aa, bb; for(i = 1; i <= m; i++) if(!edges[i].done) { aa = find(edges[i].u); bb = find(edges[i].v); if(aa != bb) { if(aa > bb) f[aa] = bb, num[bb] += num[aa], num[aa] = 0; else f[bb] = aa, num[aa] += num[bb], num[bb] = 0; } } for(i = 1; i <= n; i++) insert(root[find(i)], value[i]); for(i = opp-1; i >= 0; i--) { if(op[i].kk == 0) merge(edges[op[i].x].u, edges[op[i].x].v); if(op[i].kk == 1) query(op[i].x, op[i].y), cnt++; if(op[i].kk == 2) updata(op[i].x, op[i].y); } } int main(void) { int _ = 0; while(scanf("%d%d", &n, &m), n!=0 || m!=0) { init(); read(); work(); printf("Case %d: %.6f\n", ++_, ans/(double)cnt); } return 0; }
![扫描线三巨头 hdu1928hdu 1255 hdu 1542 [POJ 1151]](https://img.php1.cn/3c972/245b5/42f/19446f78530d3747.jpeg)
京公网安备 11010802041100号