20分,求助
查看原帖
20分,求助
486001
Knighthood楼主2022/11/20 15:37

为什么20啊?(迷惑

#include<iostream>
#include<algorithm>
#include<vector>

using namespace std;

#define middle(a, b) ((a + b) >> 1)

const int N = 40005;

int pos[N], root;

class Input{
public:
    int a, b, h;
}in[N];

class Line{
public:
    int x, Y1, y2, f;

    Line(int a, int b, int c, int d){
        x = a, Y1 = b, y2 = c, f = d;
    }

    Line(){
        x = Y1 = y2 = 0;
    }

}line[N << 1];

class Segment_tree{

#define l(k) t[k].l
#define r(k) t[k].r
#define lc(k) t[k].lc
#define rc(k) t[k].rc
#define s(k) t[k].sum
#define z(k) t[k].lazy_tag

private:
    int tot = 0;
    class Tree{
    public:
        int l, r, lc, rc, lazy_tag;
        long long sum;

        Tree(){
            l = r = lc = rc = lazy_tag = 0;
            sum = 0ll;
        }

        Tree(int a, int b){
            l = a, r = b, lc = rc = lazy_tag = 0;
            sum = 0ll;
        }

    };

    vector<Tree> t;

    void Build(int &k, int l, int r){
        if(!k)
            k = ++tot;
        t[k] = Tree(l, r);
        if(l + 1 == r)
            return;
        int mid = middle(l, r);
        Build(lc(k), l, mid);
        Build(rc(k), mid, r);
    }

public:

    Segment_tree(int n){
        t.resize(2 * n + 5);
        Build(root, 1, n);
    }

    void Modify(int k, int l, int r, int add){
//        cout << k << " Pr \n";
        if(l <= pos[l(k)] && pos[r(k)] <= r){
            z(k) += add;
            s(k) = z(k) ? pos[r(k)] - pos[l(k)] : 0;
            return;
        }
        int mid = middle(l(k), r(k));
        if(lc(k) && l <= pos[mid])
            Modify(lc(k), l, r, add);
        if(rc(k) && r > pos[mid])
            Modify(rc(k), l, r, add);
        s(k) = z(k) ? pos[r(k)] - pos[l(k)] : s(lc(k)) + s(rc(k));
//        cout << k << ' ' << s(k) << ' ' << z(k) << '\n';
    }

    long long Ask(){return s(root);}

};

signed main(){
//#define LOCAL
#ifdef LOCAL
    freopen("test.in", "r", stdin);
    freopen("test.out", "w", stdout);
#endif

    ios_base::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);

    int n;
    cin >> n;
    int tot = 0;
    for(int i = 1; i <= n; ++i){
        cin >> in[i].a >> in[i].b >> in[i].h;
        line[++tot] = Line(in[i].a, 0, in[i].h, 1);
        line[++tot] = Line(in[i].b, 0, in[i].h, -1);
        pos[i] = in[i].h;
    }
    sort(pos + 1, pos + 2 + n);
    sort(line + 1, line + 1 + tot, [&](Line a, Line b)->int{return a.x < b.x;});
    int kcx = 0;
    pos[0] = -1;
    for(int i = 1; i <= n + 1; ++i){
        if(pos[i] != pos[i - 1])
            pos[++kcx] = pos[i];
    }
    Segment_tree tree(kcx);
//    cout << line[1].Y1 << ' ' << line[1].y2 << '\n';
    tree.Modify(root, line[1].Y1, line[1].y2, line[1].f);
    long long ans = 0;
    for(int i = 2; i <= tot; ++i){
        ans += 1ll * tree.Ask() * (line[i].x - line[i - 1].x);
//        cout << ans << ' ' << tree.Ask() << '\n';
//        cout << line[i].Y1 << ' ' << line[i].y2 << "GS:FFF\n";
        tree.Modify(root, line[i].Y1, line[i].y2, line[i].f);
//        cout << tree.Ask() << '\n';
    }
    cout << ans;

    return 0;
}
2022/11/20 15:37
加载中...