首页 > 代码库 > bzoj2300
bzoj2300
http://www.lydsy.com/JudgeOnline/problem.php?id=2300
终于对了。。。
平衡树又写挂了。。。不要忘记清空原先的root和修改root。。。
#include<bits/stdc++.h> using namespace std; const int N = 200010; const double eps = 1e-8; struct query { int x, opt; } q[N]; struct data { double x, y; int cut; } a[N]; int m, Q, len; double ans[N]; double ans1, n; namespace splaytree { int root; int child[N][2], fa[N]; void zig(int x) { int y = fa[x]; fa[x] = fa[y]; child[fa[x]][child[fa[x]][1] == y] = x; child[y][0] = child[x][1]; fa[child[x][1]] = y; fa[y] = x; child[x][1] = y; } void zag(int x) { int y = fa[x]; fa[x] = fa[y]; child[fa[x]][child[fa[x]][1] == y] = x; child[y][1] = child[x][0]; fa[child[x][0]] = y; fa[y] = x; child[x][0] = y; } void splay(int x, int t) { while(fa[x] != t) { int y = fa[x], z = fa[y]; if(z == t) { child[y][0] == x ? zig(x) : zag(x); break; } // child[y][0] == x ? zig(x) : zag(x); // child[z][0] == x ? zig(x) : zag(x); else if(y == child[z][0] && x == child[y][0]) { zig(y); zig(x); } else if(y == child[z][1] && x == child[y][1]) { zag(y); zag(x); } else if(y == child[z][0] && x == child[y][1]) { zag(x); zig(x); } else if(y == child[z][1] && x == child[y][0]) { zig(x); zag(x); } } if(!t) root = x; } void add(data t, int k) { if(!root) { root = k; return; } int now = root; while(1) { if(!child[now][t.x > a[now].x]) { fa[k] = now; child[now][t.x > a[now].x] = k; splay(k, 0); return; } now = child[now][t.x > a[now].x]; } } void del(int x) { splay(x, 0); if(child[x][0] * child[x][1] == 0) { root = child[x][0] + child[x][1]; fa[root] = fa[x] = child[x][0] = child[x][1] = 0; return; } int now = child[x][1]; while(child[now][0]) now = child[now][0]; fa[child[x][0]] = now; child[now][0] = child[x][0]; root = child[x][1]; fa[root] = fa[x] = child[x][0] = child[x][1] = 0; splay(now, 0); } int Pre(int x) { splay(x, 0); x = child[x][0]; if(!x) return 0; while(child[x][1]) x = child[x][1]; return x; } int Next(int x) { splay(x, 0); x = child[x][1]; if(!x) return 0; while(child[x][0]) x = child[x][0]; return x; } double slope(int x, int y) { return (a[y].y - a[x].y) / (a[y].x - a[x].x); } double sqr(double x) { return x * x; } double dis(int x, int y) { if(!x || !y) return 0; return sqrt(sqr(a[x].x - a[y].x) + sqr(a[x].y - a[y].y)); } void insert(data t, int x) { add(t, x); int pre = Pre(x), nxt = Next(x); ans1 += dis(x, pre) + dis(x, nxt) - dis(nxt, pre); if(!pre || !nxt) return; splay(pre, x); splay(nxt, x); if(slope(pre, x) - slope(x, nxt) <= eps) { ans1 -= dis(x, pre) + dis(x, nxt) - dis(pre, nxt); del(x); return; } int ppre = Pre(pre), nnxt = Next(nxt); while(ppre && slope(x, pre) - slope(pre, ppre) >= eps) { ans1 -= dis(pre, x) + dis(pre, ppre) - dis(x, ppre); del(pre); pre = ppre; ppre = Pre(pre); } while(nnxt && slope(x, nxt) - slope(nxt, nnxt) <= eps) { ans1 -= dis(nxt, x) + dis(nxt, nnxt) - dis(x, nnxt); del(nxt); nxt = nnxt; nnxt = Next(nxt); } } } using namespace splaytree; int main() { // freopen("defense1.in", "r", stdin); // freopen("defense.out", "w", stdout); scanf("%lf%lf%lf%d", &n, &a[2].x, &a[2].y, &m); m += 3; a[3].x = n; a[3].y = 0; for(int i = 4; i <= m; ++i) scanf("%lf%lf", &a[i].x, &a[i].y); scanf("%d", &Q); for(int i = 1; i <= Q; ++i) { scanf("%d", &q[i].opt); if(q[i].opt == 1) { scanf("%d", &q[i].x); a[q[i].x + 3].cut = 1; } } len = 0; for(int i = 1; i <= m; ++i) if(!a[i].cut) insert(a[i], i); for(int i = Q; i; --i) if(q[i].opt == 1) insert(a[q[i].x + 3], q[i].x + 3); else if(q[i].opt == 2) ans[++len] = ans1; for(int i = len; i; --i) printf("%.2f\n", ans[i]); // fclose(stdin); fclose(stdout); return 0; }
bzoj2300
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。