题解 P3997 【[SHOI2013]扇形面积并】

LPA20020220 · 2018-09-12 21:24:50 · 题解

显然一份区域的贡献为覆盖其上的扇形半径的第k大的平方。所以我们可以按扇形的半径从大到小排序， 每次等于一个区间赋值的操作， 如果一个段被覆盖k次就产生贡献。（貌似比扫描线常数更小， 而且还好写...貌似突然rk1了？？）

维护一个区间最大最小值判断是否应该递归计算。 另外， 将贡献过的区间的size赋值为0， 避免重复计算。

代码如下：

    #include <cstdio>
    #include <cstring>
    #include <cmath>
    #include <cctype>
    #include <algorithm>
    #include <cstdlib>
    #define R register
    #define IN inline
    #define W while
    #define gc getchar()
    #define MX 2000500
    #define ll long long
    bool neg;
    template <class T>
    IN void in(T &x)
    {
        x = 0; R char c = gc;
        for (; !isdigit(c); c = gc)
        if(c == '-') neg = true;
        for (;  isdigit(c); c = gc)
        x = (x << 1) + (x << 3) + c - 48;
        if(neg) neg = false, x = -x;
    }
    int q, seg, kth, tar; struct Node {int siz, mn, mx, tag;} tree[MX << 2];
    struct opt {int h, lef, rig;} req[100005];
    IN bool operator < (const opt &x, const opt &y) {return x.h > y.h;}
    namespace SGT
    {
        #define ls (now << 1)
        #define rs (now << 1 | 1)
        IN void pushup(R int now)
        {
            tree[now].mn = std::min(tree[ls].mn, tree[rs].mn);
            tree[now].mx = std::max(tree[ls].mx, tree[rs].mx);
            tree[now].siz = tree[ls].siz + tree[rs].siz;
        }
        IN void pushdown(R int now)
        {
            if(tree[now].tag)
            {
                if(ls) tree[ls].mn += tree[now].tag, tree[ls].mx += tree[now].tag, tree[ls].tag += tree[now].tag;
                if(rs) tree[rs].mn += tree[now].tag, tree[rs].mx += tree[now].tag, tree[rs].tag += tree[now].tag;
                tree[now].tag = 0;
            }
        }
        void build(R int now, R int lef, R int rig)
        {
            if(lef == rig) return tree[now].siz = 1, void();
            int mid = lef + rig >> 1;
            build(ls, lef, mid), build(rs, mid + 1, rig);
            pushup(now);
        }
        int query(R int now, R int lef, R int rig, R int lb, R int rb)
        {
            if(lef > rig) return 0;
            if(tree[now].mn >= kth) return 0;
            if(lef >= lb && rig <= rb)
            {
                if(tree[now].mx < tar) {tree[now].tag += 1, tree[now].mx++, tree[now].mn++; return 0;}
                if(tree[now].mn == tar) {int ret = tree[now].siz; tree[now].siz = 0; tree[now].mx = tree[now].mn = kth; return ret;}
                int ret = 0, mid = lef + rig >> 1;
                pushdown(now);
                if(ls) ret += query(ls, lef, mid, lb, rb); if(rs) ret += query(rs, mid + 1, rig, lb, rb);
                pushup(now); return ret;
            }
            int mid = lef + rig >> 1, ret = 0; pushdown(now);
            if(lb <= mid) ret += query(ls, lef, mid, lb, rb);
            if(rb > mid) ret += query(rs, mid + 1, rig, lb, rb);
            pushup(now); return ret;
        }
        #undef ls
        #undef rs
    }
    ll ans, sum;
    int main(void)
    {

        in(q), in(seg), in(kth); tar = kth - 1;
        SGT::build(1, 1, seg << 1);
        for (R int i = 1; i <= q; ++i) in(req[i].h), in(req[i].lef), in(req[i].rig), req[i].lef += 1 + seg, req[i].rig += seg;
        std::sort(req + 1, req + 1 + q);
        for (R int i = 1; i <= q; ++i)
        {
            sum = 0;
            if(req[i].rig < req[i].lef)
            {
                sum += SGT::query(1, 1, seg << 1, req[i].lef, seg << 1);
                sum += SGT::query(1, 1, seg << 1, 1, req[i].rig);
                ans += 1ll * req[i].h * req[i].h * sum;
            }
            else
            {
                sum += SGT::query(1, 1, seg << 1, req[i].lef, req[i].rig);
                ans += 1ll * req[i].h * req[i].h * sum;
            }
        }
        printf("%lld", ans);
    }