为什么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;
}