A simple Blog for wyx I've been down the bottle hoping.
BZOJ 4561: [JLoi2016]圆的异或并 扫描线+平衡树
发表于: | 分类: Oi | 评论:0 | 阅读:79

开始做去年的省选题,有的题有点思路了,但是还是有的题目一脸懵逼

这题告诉你圆圆之间不相交,然后这题就有了一个优美的性质,就是在不加入新远且没有圆退出的情况下,他们的上下关系是绝对不会改变的

然后……然后就好办了吗,维护一条从左到右的扫描线,然后用一个treap维护一下纵坐标

每次加入一个圆的时候需要计算他被多少个圆包含,把一个下边界看成一个-1,一个上边界看成一个+1

然后看一下和奇偶性就行了

妈的智障我居然把treap删除打错了

#include <cmath>
#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
using namespace std;
#define fir first
#define sec second
#define mp make_pair
const int N = 4e5+5;
typedef long long LL;
typedef double f2;
int n, m, tot, cnt, root;
LL now;
int rnd[N], ls[N], rs[N], tr[N], val[N], id[N];

inline LL read() {
    LL x=0,f=1;char ch = getchar();
    while(ch < '0' || ch > '9'){if(ch == '-')f=-1;ch = getchar();}
    while(ch >='0' && ch <='9'){x=(x<<1)+(x<<3)+ch-'0';ch = getchar();}
    return x*f;
}

struct data {
    LL x,y,r;
    void R() {
        x = read(), y = read(), r = read();
    }
    bool operator < (const data &z) const {
        return x - r < z.x - z.r;
    }
}c[N];

pair <LL,int> x[N];
inline f2 calc(int x,int k) {
    f2 tmp = (c[x].x-now)*(c[x].x-now);
    tmp = sqrt(c[x].r*c[x].r-tmp);
    if(k==1) return c[x].y + tmp;
    else return c[x].y - tmp;
}

inline void updata(int k) { tr[k] = tr[ls[k]] + tr[rs[k]]+ val[k];}
inline void lturn(int &k) { int t = rs[k]; rs[k] = ls[t]; ls[t] = k;updata(k); updata(t); k = t;}
inline void rturn(int &k) { int t = ls[k]; ls[k] = rs[t]; rs[t] = k; updata(k); updata(t); k = t; }
inline void insert(int &x,int p,int k) {
    if(!x) {
        x = ++cnt; rnd[x] = rand();
        tr[x] = val[x] = k; id[x] = p;
        return;
    }
    tr[x] += k;
    if(calc(id[x],val[x]) < calc(p,k) || (calc(id[x],val[x])==calc(p,k) && k > val[x])) {
        insert(ls[x],p,k);
        if(rnd[ls[x]] < rnd[x]) rturn(x);
    }
    else {
        insert(rs[x],p,k);
        if(rnd[rs[x]] < rnd[x]) lturn(x);
    }
}
void del(int &x,int p,int k) {
    if(id[x] == p && val[x] == k) {
        if(!ls[x] || !rs[x]) x = ls[x] + rs[x];
        else if(rnd[ls[x]] < rnd[rs[x]]) rturn(x), del(x,p,k);
        else lturn(x),del(x,p,k);
        return;
    }
    tr[x] -= k;
    if(calc(id[x],val[x]) < calc(p,k) || (calc(id[x],val[x]) == calc(p,k) && k > val[x])) del(ls[x],p,k);
    else del(rs[x],p,k);
}
inline int find(int tt) {
    int x = root, ans = 0;
    while(x) {
        if(calc(id[x],val[x]) > tt) {
            ans += tr[ls[x]] + val[x];
            x = rs[x];
        } 
        else x = ls[x];
    }
    return ans;
}

int main() { srand(150137);
    cin >> n; LL ans = 0;
    for(int i=1;i<=n;++i)  {
        c[i].R();
        x[++tot] = mp(c[i].x-c[i].r,i);
        x[++tot] = mp(c[i].x+c[i].r,-i);
    }
    sort(x+1,x+tot+1);
    for(int i=1;i<=tot;++i) {
        now = x[i].fir;
        if(x[i].sec > 0) {
            int k = find(c[x[i].sec].y);
            if(~k & 1) ans += c[x[i].sec].r * c[x[i].sec].r;
            else ans -= c[x[i].sec].r * c[x[i].sec].r;
            insert(root,x[i].sec,1);
            insert(root,x[i].sec,-1);
        }
        else {
            del(root,-x[i].sec,1);
            del(root,-x[i].sec,-1);
        }
    }
    cout << ans << endl;
}
Title - Artist
0:00

站点地图 网站地图
Copyright © 2015-2017 A simple Blog for wyx
Powered by Typecho自豪的采用Sgreen主题

TOP