http://www.lydsy.com/JudgeOnline/problem.php?id=2300

终于对了。。。

平衡树又写挂了。。。不要忘记清空原先的root和修改root。。。

#include
using namespace std;
const int N = ;
const double eps = 1e-;
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][], fa[N];
void zig(int x)
{
int y = fa[x];
fa[x] = fa[y]; child[fa[x]][child[fa[x]][] == y] = x;
child[y][] = child[x][]; fa[child[x][]] = y;
fa[y] = x; child[x][] = y;
}
void zag(int x)
{
int y = fa[x];
fa[x] = fa[y]; child[fa[x]][child[fa[x]][] == y] = x;
child[y][] = child[x][]; fa[child[x][]] = y;
fa[y] = x; child[x][] = y;
}
void splay(int x, int t)
{
while(fa[x] != t)
{
int y = fa[x], z = fa[y];
if(z == t)
{
child[y][] == 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][] && x == child[y][]) { zig(y); zig(x); }
else if(y == child[z][] && x == child[y][]) { zag(y); zag(x); }
else if(y == child[z][] && x == child[y][]) { zag(x); zig(x); }
else if(y == child[z][] && x == child[y][]) { zig(x); zag(x); }
}
if(!t) root = x;
}
void add(data t, int k)
{
if(!root) { root = k; return; }
int now = root;
while()
{
if(!child[now][t.x > a[now].x])
{
fa[k] = now; child[now][t.x > a[now].x] = k;
splay(k, ); return;
}
now = child[now][t.x > a[now].x];
}
}
void del(int x)
{
splay(x, );
if(child[x][] * child[x][] == )
{
root = child[x][] + child[x][];
fa[root] = fa[x] = child[x][] = child[x][] = ; return;
}
int now = child[x][];
while(child[now][]) now = child[now][];
fa[child[x][]] = now; child[now][] = child[x][];
root = child[x][]; fa[root] = fa[x] = child[x][] = child[x][] = ;
splay(now, );
}
int Pre(int x)
{
splay(x, );
x = child[x][];
if(!x) return ;
while(child[x][]) x = child[x][];
return x;
}
int Next(int x)
{
splay(x, );
x = child[x][];
if(!x) return ;
while(child[x][]) x = child[x][];
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 ;
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[].x, &a[].y, &m); m += ;
a[].x = n; a[].y = ;
for(int i = ; i <= m; ++i) scanf("%lf%lf", &a[i].x, &a[i].y);
scanf("%d", &Q);
for(int i = ; i <= Q; ++i)
{
scanf("%d", &q[i].opt);
if(q[i].opt == )
{
scanf("%d", &q[i].x);
a[q[i].x + ].cut = ;
}
}
len = ;
for(int i = ; i <= m; ++i) if(!a[i].cut) insert(a[i], i);
for(int i = Q; i; --i)
if(q[i].opt == ) insert(a[q[i].x + ], q[i].x + );
else if(q[i].opt == ) ans[++len] = ans1;
for(int i = len; i; --i) printf("%.2f\n", ans[i]);
// fclose(stdin); fclose(stdout);
return ;
}