bzoj4418 [Shoi2013]扇形面积并

传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=4418

【题解】

被题目名称吓死系列。

用一棵线段树维护当前有哪些半径。

那么将扇形差分，每段空白区域相当于查询线段树内第K大。

权值线段树就行啦！

O(nlogn)

# include <stdio.h>

# include <string.h>

# include <iostream>

# include <algorithm>

// # include <bits/stdc++.h>

using namespace std;

typedef long long ll;

typedef long double ld;

typedef unsigned long long ull;

const int M = 5e5 + ;

const int mod = 1e9+;

# define RG register

# define ST static

int n, m, K;

struct pa {

    int r, pos;

    int f;

    pa() {}

    pa(int r, int pos, int f) : r(r), pos(pos), f(f) {}

    friend bool operator <(pa a, pa b) {

        return a.pos < b.pos;

    }

}p[M]; int pn = ;

namespace SMT {

    int sz[M];

    # define ls (x<<)

    # define rs (x<<|)

    inline void edt(int x, int l, int r, int pos, int del) {

        if(l == r) {

            sz[x] += del;

            return ;

        }

        int mid = l+r>>;

        if(pos <= mid) edt(ls, l, mid, pos, del);

        else edt(rs, mid+, r, pos, del);

        sz[x] = sz[ls] + sz[rs];

    }

    inline int query(int x, int l, int r, int rk) {

        if(l == r) return l;

        int mid = l+r>>;

        if(sz[rs] < rk) return query(ls, l, mid, rk-sz[rs]);

        else return query(rs, mid+, r, rk);

    }

    inline int query(int rk) {

        if(sz[] < rk) return ;

        else return query(, , 1e5, rk);

    }

}

int main() {

    cin >> n >> m >> K;

    for (int i=, r, a1, a2; i<=n; ++i) {

        scanf("%d%d%d", &r, &a1, &a2);

        p[++pn] = pa(r, a1, );

        p[++pn] = pa(r, a2, -);

        if(a1 > a2) {

            p[++pn] = pa(r, -m, );

            p[++pn] = pa(r, m, -);

        }

    }

    ll ans = ;

    int lst = -1e9;

    sort(p+, p+pn+);

//    for (int i=1; i<=pn; ++i) printf("pos = %d, r = %d, del = %d\n", p[i].pos, p[i].r, p[i].f);

    for (int i=; i<=pn; ++i) {

        int ps = p[i].pos, j=i;

        if(lst != -1e9) {

            int R = SMT::query(K);// cout << p[i].pos << ' ' << R << endl;

            ans += 1ll * R * R * (p[i].pos - lst);

        }

        while(j+ <= pn && p[j+].pos == p[i].pos) ++j;

        for (int k=i; k<=j; ++k)

            SMT::edt(, , 1e5, p[k].r, p[k].f);

        lst = p[i].pos;

        i = j;

    }

    cout << ans;

    return ;

}