#include <bits/stdc++.h>
using namespace std;
const int N = 410;

struct node {
	//  op 线是进还是出
	int x, y_1, y_2, op;
};

node a[N];
int tot;

bool cmp(node a, node b) {
	return a.x < b.x;
}

int x_1[N], x_2[N], y_1[N], y_2[N];
int y[405], cnt[405], sum_y;

// 增加的线条
void add(int y_1, int y_2) {
	for (int i = 1; i <= tot; i++) {
		if (y[i] >= y_1 && y[i] < y_2) {
			if (cnt[i] == 0)
				sum_y += y[i + 1] - y[i];
			cnt[i]++;
		}
	}
}

// 删除线
void del(int y_1, int y_2) {
	for (int i = 1; i <= tot; i++) {
		if (y[i] >= y_1 && y[i] < y_2) {
			cnt[i]--;
			if (cnt[i] == 0)
				sum_y -= y[i + 1] - y[i];
		}
	}
}
int n;

int main() {
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> x_1[i] >> y_1[i] >> x_2[i] >> y_2[i];
		a[++tot] = {x_1[i], y_1[i], y_2[i], 1};  // 进入
		y[tot] = y_1[i];
		a[++tot] = {x_2[i], y_1[i], y_2[i], -1}; // 出
		y[tot] = y_2[i];
	}

	sort(a + 1, a + 1 + tot, cmp);
	sort(y + 1, y + 1 + tot);

	long long ans = 0;
	for (int i = 1; i <= tot; i++) {
		if (i > 1)
			ans += 1ll * (a[i].x - a[i - 1].x) * sum_y;
		if (a[i].op == 1)
			add(a[i].y_1, a[i].y_2);
		else
			del(a[i].y_1, a[i].y_2);
	}
	cout << ans;
	return 0;
}

E

// 1. 排序去重 x 和 y\

// 矩形， 两个点， （x1, y1 ） (x2, y2)
for (int i = 1; i <= n; i++) {
	int x = lower_bound(tx + 1, tx + 1 + x_n, x1[i]) - tx;
	int y = lower_bound(ty + 1, ty + 1 + y_n, y1[i]) - ty;
	int xx = lower_bound(tx + 1, tx + 1 + x_n, x2[i]) - tx;
	int yy = lower_bound(ty + 1, ty + 1 + y_n, y2[i]) - ty;
	// 标记这些范围有面积
	for (int j = x; j < xx; j++)
		for (int k = y; k < yy; k++) {
			vis[j][k] = 1;
		}
}
// 计算面积
long long ans = 0;

for (int i = 1; i < x_n ; i++) {
	for (int j = 1; j < y_n; j++) {
		if (vis[i][j])
			ans += 1LL * (tx[i + 1] - tx[i]) * (ty[i + 1] - ty[i]);
	}
}
cout << ans;

D

//三台相机， 4 种放法
//1. 三台横
//2. 三台竖
//3. 两横一竖
//4. 一横两竖
#include <bits/stdc++.h>
using namespace std;
const int N = 5e4 + 10;
int n, x[N], y[N];
int tx[N], ty[N], x_n, y_n;
vector<int> vx[N], vy[N];
int cntx[N], cnty[N];
int cx, cy; // 对应整体的 行和列的个数，去重以后的

// 添加 （i,j） 这个点
void add(int i, int j) {
	if (cntx[i] == 0)
		cx++;
	if (cnty[j] == 0)
		cy++;
	cntx[i]++;
	cnty[j]++;
}

// 删除 i,j 这个点
void dele(int i, int j) {
	cntx[i]--;
	cnty[j]--;
	if (cntx[i] == 0)
		cx--;
	if (cnty[j] == 0)
		cy--;
}

int main() {
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> x[i] >> y[i];
		tx[i] = x[i];
		ty[i] = y[i];
	}
	sort(tx + 1, tx + 1 + n);
	sort(ty + 1, ty + 1 + n);
	x_n = unique(tx + 1, tx + 1 + n) - (tx + 1);
	y_n = unique(ty + 1, ty + 1 + n) - (ty + 1);

	// 离散化
	for (int i = 1; i <= n; i++) {
		x[i] = lower_bound(tx + 1, tx + 1 + x_n, x[i]) - tx;
		y[i] = lower_bound(ty + 1, ty + 1 + y_n, y[i]) - ty;
		vx[x[i]].push_back(y[i]);
		vy[y[i]].push_back(x[i]);
		add(x[i], y[i]);
	}
	// 对应 三横或者 三列可以搞定
	if (cx <= 3 || cy <= 3) {
		cout << 1;
		return 0;
	}
	// 枚举删除每一行
	for (int i = 1; i <= x_n; i++) {
		for (auto j : vx[i])
			dele(i, j);
		if (cx <= 2 || cy <= 2) {
			cout << 1;
			return 0;
		}
		// 复原
		for (auto j : vx[i])
			add(i, j);
	}
	// 枚举删除每一列
	for (int j = 1; j <= y_n; j++) {
		for (auto i : vy[j])
			dele(i, j);
		if (cx <= 2 || cy <= 2) {
			cout << 1;
			return 0;
		}
		for (auto i : vy[j])
			add(i, j);
	}
	cout << 0;
	return 0;
}

C

先处理得到区间范围，剩下的和上一题差不多

B

A

分别对 x 和  y 离散化，
输出相对位置就是最后的结果

// 离散化
// 对于一组数字a[i]，
// 用a[i] 的排名去替代它
//1   10   1000  10000 100000
//1   2      3    4      5
//1. 先得到所有的数组 a[i]
//2. 排序， 去重
//3. 找到相对位置
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int n, a[N];
int t[N];
// 1 2 3 3 4 4 5  sort
// 1 2 3 4 5 3 4   unique
int main() {
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
		t[i] = a[i];
	}
	sort(t + 1, t + 1 + n);
	int la = unique(t + 1, t + 1 + n)  - (t + 1);
	for (int i = 1; i <= n; i++)
		cout << a[i] << " ";
	cout << endl;
	// 找到每一个值 的相对顺序
	for (int i = 1; i <= n; i++) {
		int res = lower_bound(t + 1, t + 1 + la, a[i]) - t;
		cout << res << " ";
	}
	return 0;
}