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;
}