1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
|
template <typename T = long long>
class Tree {
vector<T> tree;
public:
// 构造函数：初始化大小为 n 的树状数组，初始所有元素值为 val（外部表现为 0-based）
Tree(int n, T val = 0) : tree(n + 1) {
for (int i = 1; i <= n; i++) {
tree[i] += val;
int nxt = i + (i & -i);
if (nxt <= n) {
tree[nxt] += tree[i];
}
}
}
// 构造函数：使用给定的 vector 在 O(N) 时间内快速初始化建树
Tree(const vector<T>& data) {
int n = data.size();
tree.resize(n + 1);
for (int i = 1; i <= n; i++) {
tree[i] += data[i - 1]; // data是 0-based
int nxt = i + (i & -i);
if (nxt <= n) {
tree[nxt] += tree[i];
}
}
}
// 单点修改：将 0-based 下标 i 处的元素增加 val
void add(int i, T val = 1) {
for (++i; i < tree.size(); i += i & (-i)) {
tree[i] += val;
}
}
// 前缀求和：计算 0-based 下标区间 [0, i] 内的所有元素之和
T pre(int i) const {
T res = 0;
for (++i; i > 0; i &= i - 1) {
res += tree[i];
}
return res;
}
// 区间求和：计算 0-based 下标区间 [l, r] 内的所有元素之和
T query(int l, int r) const {
if (r < l) {
return 0;
}
return pre(r) - pre(l - 1); // 当 l=0 时, pre(-1) 会合理地返回 0
}
// 树上二分查找：返回满足前缀和 >= val 的最小 0-based 下标
int lower_bound(T val) const {
int w = bit_width(tree.size() - 1);
int res = 0;
T s = 0;
for (int i = w - 1; i >= 0; i--) {
int nxt = res + (1 << i);
if (nxt < tree.size() && tree[nxt] + s < val) {
res += (1 << i);
s += tree[nxt];
}
}
return res; // 返回 0-based 下标：内部 1-based 下标为 res + 1，因此 0-based 为 res
}
};
void solve() {
int n;
cin >> n;
int a, b, c, d;
int bias = 5005;
vector<tri> tem;
vector<tri> tem2;
rep(i, 0, n - 1) {
cin >> a >> b >> c >> d;
if (a == c)
tem.emplace_back(a, min(b, d), max(b, d));
else
tem2.emplace_back(b, min(a, c), max(a, c));
}
ll ans = 0;
sort(all(tem2), [&](const tri& x, const tri& y) { return get<0>(x) < get<0>(y); });
Tree tree(2 * bias + 5);
rep(i, 0, sz(tem2) - 1) {
auto& [y, lx, rx] = tem2[i];
vector<tri> tem3;
rep(j, 0, sz(tem) - 1) {
auto& [x, ly, ry] = tem[j];
if (ly <= y && ry >= y && lx <= x && x <= rx) {
tree.add(x + bias, 1);
tem3.emplace_back(x, ly, ry);
}
}
sort(all(tem3), [&](const tri& x, const tri& y) { return get<2>(x) < get<2>(y); });
int cnt = 0;
rep(j, i + 1, sz(tem2) - 1) {
auto& [y2, lx2, rx2] = tem2[j];
while (cnt < sz(tem3) && get<2>(tem3[cnt]) < y2) {
tree.add(get<0>(tem3[cnt]) + bias, -1);
cnt++;
}
int tem4 = tree.query(lx2 + bias, rx2 + bias);
ans += 1LL * tem4 * (tem4 - 1) / 2;
}
rep(j, cnt, sz(tem3) - 1) { tree.add(get<0>(tem3[j]) + bias, -1); }
}
cout << ans << endl;
return;
}
|
