Almost Acyclic Graph
出处：CF915D
题目大意：给定一个 $n$ 个点 $m$ 条边有向图，最多可以移除它的一条边，问是否能把它变成有向无环图？
数据范围：$2 \leq n \leq 500, 1 \leq m \leq \min(n(n-1),100000)$。
思路：事实上，看到这个数据范围就知道时间复杂度大概是 $O(nm)$ 了，而DAG的显著性质又是拓扑排序，它的时间复杂度是 $O(m)$ ，因此考虑对每个点作一次check。
然而，check应该如何check？注意到去除一条边是把一个点的入度减一，因此直接模拟即可，原来是猜猜题。
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
| void solve() {
int n, m;
int x, y;
cin >> n >> m;
vvi ma(n);
vi deg(n);
rep(i, 0, m - 1) {
cin >> x >> y;
ma[x - 1].push_back(y - 1);
deg[y - 1]++;
}
queue<int> q;
auto check = [&](int x) -> bool {
auto deg2 = deg;
deg2[x] = max(deg2[x] - 1, 0);
vi res;
while (!q.empty()) q.pop();
rep(i, 0, n - 1) {
if (!deg2[i]) q.push(i);
}
while (!q.empty()) {
auto node = q.front();
q.pop();
res.push_back(node);
for (int& p : ma[node]) {
if (--deg2[p] == 0) q.push(p);
}
}
return sz(res) == n;
};
rep(i, 0, n - 1) {
if (check(i)) {
cout << "YES" << endl;
return;
}
}
cout << "NO" << endl;
return;
}
|
AI robots
出处：CF1045G
题目大意：给定机器人位置、视野半径和智商，统计能互相看见且智商差不超过 $K$ 的无序对数量。
数据范围： $1 \leq n \leq 10^5, 0 \leq K \leq 20, 0 \leq x_i,r_i,q_i \leq 10^9$
思路：
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
| template <typename T = long long>
class Tree {
vector<T> tree;
public:
Tree() {}
// 构造函数：初始化大小为 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, k;
cin >> n >> k;
vector<tri> ma;
map<int, vi> ma2;
int x, y, z;
rep(i, 0, n - 1) {
cin >> x >> y >> z;
ma.emplace_back(x, y, z);
ma2[z].push_back(x);
}
for (auto& [x, y] : ma2) {
ranges::sort(y);
y.erase(unique(all(y)), y.end());
}
map<int, Tree<ll>> tree;
for (auto& [x, y] : ma2) {
tree[x] = Tree<ll>(sz(y));
}
sort(all(ma), [&](const tri& x, const tri& y) { return get<1>(x) > get<1>(y); });
ll ans = 0;
rep(i, 0, n - 1) {
auto& [x, y, z] = ma[i];
rep(j, max(0, z - k), z + k) {
if (!ma2.count(j)) continue;
int tem = ranges::lower_bound(ma2[j], x - y) - ma2[j].begin();
int tem2 = ranges::upper_bound(ma2[j], x + y) - ma2[j].begin() - 1;
ans += tree[j].query(tem, tem2);
}
int tem = ranges::lower_bound(all(ma2[z]), x) - ma2[z].begin();
tree[z].add(tem, 1);
}
cout << ans << endl;
return;
}
|
Tree Master
出处：CF1806E
题目大意：给定有根带点权树，多次询问 $x,y$ ，求两点同时向父亲移动直到根外时经过点权乘积的总和。
数据范围： $2 \leq n \leq 10^5, 1 \leq q \leq 10^5, 1 \leq a_i \leq 10^5, 1 \leq p_i < i$
思路：
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
| void solve() {
int n, q, x, y;
cin >> n >> q;
vi pa(n, -1);
vl a(n);
vvl ma(n);
rep(i, 0, n - 1) cin >> a[i];
rep(i, 1, n - 1) {
cin >> pa[i];
pa[i]--;
ma[pa[i]].push_back(i);
}
vl pre(n);
vl cnt(n);
vvl node(n);
vl dep(n);
auto dfs = [&](this auto&& dfs, int x, int pr, ll d, int d2) -> void {
pre[x] = d;
cnt[d2]++;
node[d2].push_back(x);
dep[x] = d2;
for (auto& p : ma[x]) {
if (p == pr) continue;
dfs(p, x, d + a[p] * a[p], d2 + 1);
}
return;
};
dfs(0, -1, a[0] * a[0], 0);
int B = sqrt(n);
vl id(n);
vvl dp(n);
rep(i, 0, n - 1) {
int tem = sz(node[i]);
rep(j, 0, tem - 1) { id[node[i][j]] = j; }
if (tem > 0 && tem <= B) {
dp[i].assign(tem * (tem + 1) / 2, LLONG_MIN);
}
}
auto get = [&](int x, int y) -> int {
if (x > y) swap(x, y);
return y * (y + 1) / 2 + x;
};
auto dfs2 = [&](this auto&& dfs2, int x, int y) -> ll {
if (x == y) return pre[x];
if (cnt[dep[x]] <= B) {
int tem = get(id[x], id[y]);
if (dp[dep[x]][tem] != LLONG_MIN) return dp[dep[x]][tem];
ll res = a[x] * a[y] + dfs2(pa[x], pa[y]);
dp[dep[x]][tem] = res;
return res;
} else {
return a[x] * a[y] + dfs2(pa[x], pa[y]);
}
};
rep(i, 0, q - 1) {
cin >> x >> y;
x--, y--;
cout << dfs2(x, y) << endl;
}
return;
}
|
Magic Triples (Hard Version)
出处：CF1822G2
题目大意：给定数组 $a$ ，统计有序三元组 $(i,j,k)$ 的数量，使 $a_i,a_j,a_k$ 能按某个整数公比构成等比关系。
数据范围： $1 \leq t \leq 10^4, 3 \leq n \leq 2 \cdot 10^5, 1 \leq a_i \leq 10^9, \sum n \leq 2 \cdot 10^5$
思路：
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
| struct custom_hash {
static uint64_t splitmix64(uint64_t x) {
x += 0x9e3779b97f4a7c15;
x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
return x ^ (x >> 31);
}
size_t operator()(uint64_t x) const {
static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
return splitmix64(x + FIXED_RANDOM);
}
};
void solve() {
int n;
cin >> n;
int B = 1e6;
vl a(n);
rep(i, 0, n - 1) cin >> a[i];
ll ans = 0;
umap<ll, ll, custom_hash> ma;
for (auto& p : a) ma[p]++;
for (auto& [x, y] : ma) ans += y * (y - 1) * (y - 2);
ll maxx = *max_element(all(a));
for (auto& [x, y] : ma) {
if (x <= B) {
for (ll j = 2; j * j <= x; j++) {
if (x % j == 0) {
if (ma.count(x / j) && ma.count(x * j)) {
ans += y * ma[x / j] * ma[x * j];
}
if (j * j != x && ma.count(j) && ma.count(x * x / j)) {
ans += ma[j] * ma[x * x / j] * y;
}
}
}
if (x > 1 && x <= maxx / x && ma.count(1) && ma.count(x * x)) {
ans += y * ma[1] * ma[x * x];
}
} else {
for (ll j = 2 * x; j <= maxx; j += x) {
if (x * x % j == 0 && ma.count(j) && ma.count(x * x / j)) ans += y * ma[j] * ma[x * x / j];
}
}
}
cout << ans << endl;
return;
}
|
ace5 and Task Order
出处：CF1918E
题目大意：交互题。隐藏一个排列和初始值 $x$ ，每次比较某个位置后 $x$ 会变化，需要在询问限制内还原排列。
数据范围： $1 \leq t \leq 1000, 2 \leq n \leq 10^4, \sum n \leq 10^4$
思路：
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
| mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
string ask(int l) {
cout << "? " << l << '\n';
cout.flush();
string op;
cin >> op;
return op;
}
void report(vl& res) {
cout << "! ";
rep(i, 1, sz(res) - 1) cout << res[i] << ' ';
cout << '\n';
cout.flush();
}
void solve() {
int n;
cin >> n;
vl ans(n + 1, 0);
vi cur;
rep(i, 1, n) cur.push_back(i);
auto dfs = [&](this auto&& dfs, int l, int r, vi cur) {
if (cur.empty()) return;
if (l == r) {
ans[cur[0]] = l;
return;
}
int p = cur[rng() % sz(cur)];
while (ask(p) != "=");
vi left, right;
for (auto& v : cur) {
if (v == p) continue;
string op = ask(v);
if (op == "<")
left.push_back(v);
else
right.push_back(v);
ask(p);
}
ans[p] = l + sz(left);
dfs(l, l + sz(left) - 1, left);
dfs(l + sz(left) + 1, r, right);
return;
};
dfs(1, n, cur);
report(ans);
return;
}
|
Library of Magic
出处：CF2036G
题目大意：交互题。隐藏三个特殊编号，每次询问一个区间会返回该区间内特殊编号的按位异或，需要找出三个编号。
数据范围： $1 \leq t \leq 300, 3 \leq n \leq 10^{18}$
思路：
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
| ll ask(ll l, ll r) {
cout << "xor " << l << ' ' << r << '\n';
cout.flush();
ll op;
cin >> op;
return op;
}
void report(ll a, ll b, ll c) {
cout << "ans " << a << ' ' << b << ' ' << c << ' ' << '\n';
cout.flush();
}
void solve() {
ll n;
cin >> n;
ll tem = ask(1, n);
ll a, b, c;
if (tem == 0) {
frep(i, 60, 0) {
if ((1LL << i) > n) continue;
ll tem2 = ask((1LL << i), min(n, ((1LL << (i + 1)) - 1)));
if (tem2 != 0) {
a = tem2;
break;
}
}
int idx = -1;
rep(i, 0, 60) {
if ((a >> i) & 1LL) {
idx = i;
break;
}
}
ll l = 1, r = n, mid, ans = 1;
auto check = [&](ll mid) -> bool {
ll tem2 = ask(l, mid);
if (l <= a && a <= mid) tem2 ^= a;
return (tem2 >> idx) & 1LL;
};
while (l <= r) {
mid = (l + r) / 2;
if (check(mid)) {
ans = mid;
r = mid - 1;
} else
l = mid + 1;
}
c = a ^ ans;
report(a, c, ans);
return;
} else {
int idx = -1;
rep(i, 0, 60) {
if ((tem >> i) & 1LL) {
idx = i;
break;
}
}
ll l = 1, r = n, mid, ans = 1;
auto check = [&](ll mid) -> bool {
ll tem2 = ask(l, mid);
return (tem2 >> idx) & 1LL;
};
while (l <= r) {
mid = (l + r) / 2;
if (check(mid)) {
ans = mid;
r = mid - 1;
} else
l = mid + 1;
}
a = ans;
ll tem3 = tem ^ ans;
l = 1, r = n, mid, ans = 1;
int idx2 = -1;
rep(i, 0, 60) {
if ((tem3 >> i) & 1LL) {
idx2 = i;
break;
}
}
auto check2 = [&](ll mid) -> bool {
ll tem2 = ask(l, mid);
if (l <= a && a <= mid) tem2 ^= a;
return (tem2 >> idx2) & 1LL;
};
while (l <= r) {
mid = (l + r) / 2;
if (check2(mid)) {
ans = mid;
r = mid - 1;
} else
l = mid + 1;
}
report(a, ans, tem3 ^ ans);
return;
}
return;
}
|
Magic Numbers
出处：CF628D
题目大意：给定 $m,d$ 和区间 $[a,b]$ ，统计能被 $m$ 整除且十进制位满足指定奇偶位置限制的整数数量。
数据范围： $1 \leq m \leq 2000, 0 \leq d \leq 9, 1 \leq a \leq b < 10^{2000}$
思路：
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
| void solve() {
int m, dd;
cin >> m >> dd;
string num1, num2;
cin >> num1 >> num2;
int n = sz(num2);
int dif = n - num1.length();
const int INF = 1e9 + 7;
vector<vector<int>> dp(n + 1, vector<int>(m, -1));
auto dfs = [&](this auto&& dfs, int cnt, int s, bool limit_low, bool limit_high) -> int {
if (cnt == n) return s == 0;
if (!limit_low && !limit_high && dp[cnt][s] != -1) return dp[cnt][s];
ll res = 0;
int lo = limit_low && cnt >= dif ? num1[cnt - dif] - '0' : 0;
int hi = limit_high ? num2[cnt] - '0' : 9;
int d = lo;
for (; d <= hi; d++) {
if (cnt % 2 == 0 && d == dd) continue;
if (cnt % 2 == 1 && d != dd) continue;
res += dfs(cnt + 1, (s * 10 + d) % m, limit_low && d == lo, limit_high && d == hi) % INF;
res %= INF;
}
if (!limit_high && !limit_low) dp[cnt][s] = res;
return res;
};
cout << dfs(0, 0, true, true) << endl;
return;
}
|
Radio stations
出处：CF762E
题目大意：给定无线电台的位置、广播半径和频率，统计距离与频率差均满足条件的电台对数量。
数据范围： $1 \leq n \leq 10^5, 0 \leq k \leq 10, 1 \leq x_i,r_i \leq 10^9, 1 \leq f_i \leq 10^4$
思路：
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
| template <typename T = long long>
class Tree {
vector<T> tree;
public:
Tree() {}
// 构造函数：初始化大小为 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, k;
cin >> n >> k;
vector<tri> ma;
vvi ma2(1e4 + 1);
int x, y, z;
rep(i, 0, n - 1) {
cin >> x >> y >> z;
ma.emplace_back(x, y, z);
ma2[z].push_back(x);
}
rep(i, 1, 1e4) {
ranges::sort(ma2[i]);
ma2[i].erase(unique(all(ma2[i])), ma2[i].end());
}
vector<Tree<ll>> tree(1e4 + 1);
rep(i, 1, 1e4) { tree[i] = Tree<ll>(sz(ma2[i])); }
sort(all(ma), [&](const tri& x, const tri& y) { return get<1>(x) > get<1>(y); });
ll ans = 0;
rep(i, 0, n - 1) {
auto& [x, y, z] = ma[i];
rep(j, max(1, z - k), min(10000, z + k)) {
if (ma2[j].empty()) continue;
int tem = ranges::lower_bound(ma2[j], x - y) - ma2[j].begin();
int tem2 = ranges::upper_bound(ma2[j], x + y) - ma2[j].begin() - 1;
ans += tree[j].query(tem, tem2);
}
int tem = ranges::lower_bound(all(ma2[z]), x) - ma2[z].begin();
tree[z].add(tem, 1);
}
cout << ans << endl;
return;
}
|
Anton and Permutation
出处：CF785E
题目大意：初始排列为 $1\sim n$ ，每次交换两个位置并询问交换后的逆序对数量。
数据范围： $1 \leq n \leq 2 \cdot 10^5, 1 \leq q \leq 5 \cdot 10^4$
思路：
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
| void solve() {
int n, q, l, r;
cin >> n >> q;
int B = sqrt(n) + 1;
int m = (n + B - 1) / B;
vl a(n);
vvl s(m);
rep(i, 0, n - 1) {
a[i] = i + 1;
s[i / B].push_back(a[i]);
}
rep(i, 0, m - 1) ranges::sort(s[i]);
ll ans = 0;
auto calc = [&](int l, int r, int x, int y) -> ll {
if (l > r) return 0;
if (x + 1 >= y) return 0;
ll res = 0;
int idl = l / B, idr = r / B;
if (idl == idr) {
rep(i, l, r) res += (x < a[i] && a[i] < y);
} else {
rep(i, l, min(n - 1, (idl + 1) * B - 1)) res += (x < a[i] && a[i] < y);
rep(i, idl + 1, idr - 1) {
int tem = ranges::upper_bound(s[i], x) - s[i].begin();
int tem2 = ranges::lower_bound(s[i], y) - s[i].begin();
res += tem2 - tem;
}
rep(i, idr * B, r) res += (x < a[i] && a[i] < y);
}
return res;
};
auto check = [&](int x, int y) -> void {
int id = x / B;
auto it = ranges::lower_bound(s[id], a[x]);
s[id].erase(it);
a[x] = y;
s[id].push_back(y);
ranges::sort(s[id]);
return;
};
rep(i, 0, q - 1) {
cin >> l >> r;
l--, r--;
if (l == r) {
cout << ans << endl;
continue;
}
if (l > r) swap(l, r);
if (a[l] < a[r])
ans += 1 + 2 * calc(l + 1, r - 1, a[l], a[r]);
else
ans -= 1 + 2 * calc(l + 1, r - 1, a[r], a[l]);
ll tem = a[l];
check(l, a[r]);
check(r, tem);
cout << ans << endl;
}
return;
}
|
Almost Difference
出处：CF903D
题目大意：给定数组 $a$ ，对所有有序对按题面定义的差值函数求和，其中绝对差不超过 $1$ 的贡献为 $0$ 。
数据范围： $1 \leq n \leq 2 \cdot 10^5, 1 \leq a_i \leq 10^9$
思路：
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
112
113
114
115
116
117
118
119
120
| void print(__int128 x) {
if (x == 0) {
cout << 0 << endl;
return;
}
if (x < 0) {
cout << '-';
x = -x;
}
string s;
while (x) {
s += char('0' + x % 10);
x /= 10;
}
reverse(all(s));
cout << s << endl;
}
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;
vl a(n);
rep(i, 0, n - 1) cin >> a[i];
auto sorted = a;
ranges::sort(sorted);
sorted.erase(unique(all(sorted)), sorted.end());
int m = sz(sorted);
__int128 ans = 0;
Tree cnt(m + 1);
Tree sum(m + 1);
rep(i, 0, n - 1) {
auto x1 = ranges::lower_bound(sorted, a[i]);
int tem = x1 - sorted.begin();
auto x2 = ranges::upper_bound(sorted, a[i] - 2);
if (x2 != sorted.begin()) {
int tem2 = x2 - sorted.begin() - 1;
ll tem3 = sum.query(0, tem2);
ll tem4 = cnt.query(0, tem2);
ans += (__int128)tem4 * a[i] - tem3;
}
auto x3 = ranges::lower_bound(sorted, a[i] + 2);
if (x3 != sorted.end()) {
int tem2 = x3 - sorted.begin();
ll tem3 = sum.query(tem2, m);
ll tem4 = cnt.query(tem2, m);
ans += (__int128)tem4 * a[i] - tem3;
}
cnt.add(tem, 1);
sum.add(tem, a[i]);
}
print(ans);
return;
}
|
Count The Rectangles
出处：CF1194E
题目大意：给定若干水平或竖直线段，统计能由两条水平线段和两条竖直线段围成的矩形数量。
数据范围： $1 \leq n \leq 5000, |x_{i,j}|,|y_{i,j}| \leq 10^9$
思路：
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;
}
|
