蒟蒻求助!
查看原帖
蒟蒻求助!
486001
Knighthood楼主2022/11/23 22:28

20pts 其它是WA。求助!谢谢大佬们!

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

using namespace std;

const int N = 10005;

class Line{

public:

    int x{}, y1{}, y2{}, f{};

    Line(int x, int y1, int y2, int f);

    Line();

}line[N << 1];

Line::Line(int x, int y1, int y2, int f) : x(x), y1(y1), y2(y2), f(f) {}

Line::Line() {
    x = y1 = y2 = 0;
}

int root, p[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 n(k) t[k].num
#define e(k) t[k].len
#define s(k) t[k].sum
#define lf(k) t[k].lflag
#define rf(k) t[k].rflag
#define middle(a, b) ((a + b) >> 1)

private:

    int tot = 0;

    class Tree{
    public:
        int l{}, r{}, lc{}, rc{};
        int num{}, len{}, sum{}, lflag{}, rflag{};

        Tree();

        Tree(int l1, int r1);

    };
    vector<Tree> t;

    void Build(int &k, int l, int r);

    void Pushup(int k);

public:

    explicit Segment_tree(int n);

    void Modify(int k, int l, int r, int add);

    pair<int, int> Ask();

};

Segment_tree::Tree::Tree() = default;

Segment_tree::Tree::Tree(int l1, int r1) {
    l = l1, r = r1;
    lc = rc = num = len = sum = lflag = rflag = 0;
}

Segment_tree::Segment_tree(int n){
    t.resize((n << 2) + 10);
    Build(root, 1, n);
}

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

void Segment_tree::Pushup(int k) {
    if(s(k) > 0){
        n(k) = 1;
        e(k) = p[r(k)] - p[l(k)];
        lf(k) = rf(k) = 1;
    }
    else {
        n(k) = n(lc(k)) + n(rc(k));
        if(rf(lc(k)) && lf(rc(k)))
            --n(k);
        e(k) = e(lc(k)) + e(rc(k));
        lf(k) = lf(lc(k)), rf(k) = rf(rc(k));
    }
}

void Segment_tree::Modify(int k, int l, int r, int add) {
    if(l <= p[l(k)] && p[r(k)] <= r){
        s(k) += add;
        Pushup(k);
        return;
    }
    int mid = middle(l(k), r(k));
    if(lc(k) && l <= p[mid])
        Modify(lc(k), l, r, add);
    if(rc(k) && r > p[mid])
        Modify(rc(k), l, r, add);
    Pushup(k);
}

pair<int, int> Segment_tree::Ask(){
    return make_pair(e(root), n(root));
}

int aabs(int x);

int aabs(int x) {return x < 0 ? -x : x;}

int 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){
        int x1, y1, x2, y2;
        cin >> y1 >> x1 >> y2 >> x2;
        line[++tot] = Line(x1, y1, y2, 1);
        p[tot] = y1;
        line[++tot] = Line(x2, y1, y2, -1);
        p[tot] = y2;
    }

    sort(p + 1, p + 1 + tot);
    sort(line + 1, line + 1 + tot, [&](Line a, Line b)->int{return a.x != b.x ? a.x < b.x : a.f > b.f;});
    int kcx = (int)(unique(p + 1, p + 1 + tot) - p - 1);
    Segment_tree tree(kcx);

    long long ans = 0;
    int last = 0;
    for(int i = 1; i <= tot; ++i){
        while(i < tot && line[i].f == line[i + 1].f && line[i].x == line[i + 1].x){
            tree.Modify(root, line[i].y1, line[i].y1, line[i].f);
            ++i;
        }
        tree.Modify(root, line[i].y1, line[i].y2, line[i].f);
        pair<int, int> now = tree.Ask();
//        cout << ans << ' ' << now.first << ' ' << now.second << '\n';
        ans += 1ll * aabs(now.first - last);
        last = now.first;
        ans += 2ll * now.second * (long long)(line[i + 1].x - line[i].x);
    }

    cout << ans;

    return 0;
}
2022/11/23 22:28
加载中...