X星球的一批考古机器人正在一片废墟上考古。
该区域的地面坚硬如石、平整如镜。
管理人员为方便，建立了标准的直角坐标系。
每个机器人都各有特长、身怀绝技。
它们感兴趣的内容也不相同。
经过各种测量，每个机器人都会报告一个或多个矩形区域，作为优先考古的区域。
矩形的表示格式为 (x1,y1,x2,y2)(x1,y1,x2,y2)，代表矩形的两个对角点坐标。
为了醒目，总部要求对所有机器人选中的矩形区域涂黄色油漆。
小明并不需要当油漆工，只是他需要计算一下，一共要耗费多少油漆。
其实这也不难，只要算出所有矩形覆盖的区域一共有多大面积就可以了。
注意，各个矩形间可能重叠。
输入格式
第一行，一个整数 nn，表示有多少个矩形。
接下来的 nn 行，每行有 44 个整数 x1,y1,x2,y2x1,y1,x2,y2，空格分开，表示矩形的两个对角顶点坐标。
输出格式
一行一个整数，表示矩形覆盖的总面积。
数据范围
1≤n≤100001≤n≤10000,
0≤x1,x2,y2,y2≤100000≤x1,x2,y2,y2≤10000
数据保证 x1<x2x1<x2 且 y1<y2y1<y2。
输入样例1：
3
1 5 10 10
3 1 20 20
2 7 15 17
输出样例1：
340
输入样例2：
3
5 2 10 6
2 7 12 10
8 1 15 15
输出样例2：
128分析
从左往右遍历所有的线段，如果遇到左端点，就在线段数里加上这条线，遇到右端点，就在线段树里减去这条线。
线段树的len 表示当前区间被覆盖的长度，cnt表示当前区间被多少条线整体覆盖。
类似于差分求当前点被多少条线覆盖，遇到一个矩形左边的线 cnt + 1，遇到右边的线 cnt - 1。当前线如果被覆盖，当前区间的len 就是r - l + 1。如果当前线没有被覆盖，当前区间的长度是从子节点传上来的。
删除一条线的时候，当前区间的len 会直接变成0吗？不会，因为除了本身有长度，子区间也有长度。长度是从子区间传上来的长度。
//-------------------------代码----------------------------
//#define int ll
const int N = 1e5+10;
int n,m;
struct segment {
int x,y1,y2,k;
bool operator<(segment X) {
return x < X.x;
}
} seg[N * 2];
struct node {
int l,r,cnt,len;
} tr[N<<2];
void build(int u, int l, int r)
{
tr[u] = {l, r};
if (l == r) return;
int mid = l + r >> 1;
build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
}
void push_up(int u)
{
if (tr[u].cnt > 0) tr[u].len = tr[u].r - tr[u].l + 1;
else if (tr[u].l == tr[u].r) tr[u].len = 0;
else tr[u].len = tr[u << 1].len + tr[u << 1 | 1].len;
}
void modify(int u, int l, int r, int k)
{
if (tr[u].l >= l && tr[u].r <= r)
{
tr[u].cnt += k;
push_up(u);
}
else
{
int mid = tr[u].l + tr[u].r >> 1;
if (l <= mid) modify(u << 1, l, r, k);
if (r > mid) modify(u << 1 | 1, l, r, k);
push_up(u);
}
}
void solve()
{
scanf("%d", &n);
int m = 0;
for (int i = 0; i < n; i ++ )
{
int x1, y1, x2, y2;
scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
seg[m ++ ] = {x1, y1, y2, 1};
seg[m ++ ] = {x2, y1, y2, -1};
}
sort(seg, seg + m);
build(1, 0, 10000);
int res = 0;
for (int i = 0; i < m; i ++ )
{
if (i > 0) res += tr[1].len * (seg[i].x - seg[i - 1].x);
modify(1, seg[i].y1, seg[i].y2 - 1, seg[i].k);
}
printf("%d\n", res);
}
void main_init() {}
signed main(){
TLE;
cout<<fixed<<setprecision(12);
main_init();
// while(cin>>n,n)
// while(cin>>n>>m,n,m)
// int t;cin>>t;while(t -- )
solve();
// {solve(); }
return 0;
}
/*样例区
*/
//------------------------------------------------------------
标签：矩形,tr,len,1228,x2,扫描线,y1,y2,acwing From： https://www.cnblogs.com/er007/p/16583762.html