Hướng dẫn cho LQDOJ CUP 2022 - Final Round - INRANGE
Chỉ sử dụng khi thực sự cần thiết như một cách tôn trọng tác giả và người viết hướng dẫn này.
Chép code từ bài hướng dẫn để nộp bài là hành vi có thể dẫn đến khóa tài khoản.
Chép code từ bài hướng dẫn để nộp bài là hành vi có thể dẫn đến khóa tài khoản.
Authors:
Subtask \(1\) (\(25\%\) số điểm): \(N \leq 10^{3}\).
Tutorial
Duyệt trâu để đếm từng điểm \(j\) thỏa mãn với mọi \(i\)
Độ phức tạp: \(\mathcal{O}(n^2)\)
Solution
C++
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 100005;
int n, a, b, p, mod;
int x[MAX_N];
int y[MAX_N];
long long binPow(long long a, long long b) {
long long result = 1;
while (b) {
if (b & 1) {
result = result * a % mod;
}
b >>= 1;
a = a * a % mod;
}
return result;
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
freopen("INRANGE.inp", "r", stdin);
freopen("INRANGE.out", "w", stdout);
cin >> n >> a >> b >> p >> mod;
x[1] = a, y[1] = b;
int pre = 0;
int answer = 0;
for (int i = 2; i <= n; i++) {
x[i] = (x[i - 1] + (long long)pre * p + binPow(i + a, a)) % mod + 1;
y[i] = (y[i - 1] + (long long)pre * p + binPow(i + b, b)) % mod + 1;
pre = 0;
for (int j = 1; j < i; j++) {
pre += (x[j] < x[i] && y[j] < y[i]);
}
answer += pre;
}
cout << answer << "\n";
return 0;
}
Subtask \(2\) (\(25\%\) số điểm): \(MOD \leq 10^{3}\).
Tutorial
Ta thấy rằng ta cần đếm số điểm trong một bảng từ ô \((1, 1)\) đến ô \((x, y)\) vì \(x\) và \(y\) khá nhỏ nên ta sẽ sử dụng Fenwick tree 2D để giải quyết subtask này
Độ phức tạp: \(\mathcal{O}(n \cdot log_2(X)^2)\)
Solution
C++
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 1005;
int n, a, b, p, mod;
struct FenwickTree2D {
int nodes[MAX_N][MAX_N];
void update(int x, int y) {
for (; x <= mod; x += x & -x) {
for (int i = y; i <= mod; i += i & -i) {
nodes[x][i]++;
}
}
}
long long get(int x, int y) {
long long result = 0;
for (; x; x -= x & -x) {
for (int i = y; i > 0; i -= i & -i) {
result += nodes[x][i];
}
}
return result;
}
};
FenwickTree2D fenwickTree2D;
long long binPow(long long a, long long b) {
long long result = 1;
while (b) {
if (b & 1) {
result = result * a % mod;
}
b >>= 1;
a = a * a % mod;
}
return result;
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
freopen("INRANGE.inp", "r", stdin);
freopen("INRANGE.out", "w", stdout);
cin >> n >> a >> b >> p >> mod;
int x = a, y = b;
fenwickTree2D.update(x, y);
long long answer = 0;
int pre = 0;
for (int i = 2; i <= n; i++) {
x = (x + (long long)pre * p + binPow(i + a, a)) % mod + 1;
y = (y + (long long)pre * p + binPow(i + b, b)) % mod + 1;
pre = fenwickTree2D.get(x - 1, y - 1);
fenwickTree2D.update(x, y);
answer += pre;
}
cout << answer << "\n";
return 0;
}
Subtask \(3\) (\(25\%\) số điểm): \(MOD \leq 10^{5}\).
Tutorial
Bây giờ \(x, y\) là \(10^5\), ta không thể sử dụng cấu trúc dữ liệu Fenwick tree 2D nữa và phải sử dụng một cấu trúc dữ liệu động, vì thế, ta sẽ kết hợp giữa Fenwick tree hoặc Segment tree 1 chiều và một cấu trúc dữ liệu động khác (Segment tree động hoặc Trie).
Độ phức tạp: \(\mathcal{O}(n \cdot log_2(X)^2)\)
Solution
C++
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 100005;
int n, a, b, p, mod;
struct FenwickTree2D {
private:
struct Trie {
private:
const int LOG = 30;
struct Node {
int total;
int children[2];
Node() {
total = 0;
children[0] = children[1] = 0;
}
};
int root, numNode;
vector<Node> nodes;
int getBit(int num, int pos) {
return (num >> pos) & 1;
}
public:
Trie() {
root = numNode = 0;
nodes.push_back(Node());
}
void update(int id) {
int current = root;
for (int i = LOG; i >= 0; i--) {
int x = getBit(id, i);
if (nodes[current].children[x] == 0) {
nodes[current].children[x] = ++numNode;
nodes.push_back(Node());
}
current = nodes[current].children[x];
nodes[current].total++;
}
}
int get(int id) {
int current = root;
int result = 0;
for (int i = LOG; i >= 0; i--) {
int x = getBit(id, i);
if (x == 1 && nodes[current].children[0]) {
result += nodes[nodes[current].children[0]].total;
}
current = nodes[current].children[x];
if (current == 0) {
break;
}
}
return result;
}
};
Trie nodes[MAX_N];
public:
void update(int x, int y) {
for (; x <= mod; x += x & -x) {
nodes[x].update(y);
}
}
long long get(int x, int y) {
long long result = 0;
x--;
for (; x > 0; x -= x & -x) {
result += nodes[x].get(y);
}
return result;
}
};
FenwickTree2D fenwickTree2D;
long long binPow(long long a, long long b) {
long long result = 1;
while (b) {
if (b & 1) {
result = result * a % mod;
}
b >>= 1;
a = a * a % mod;
}
return result;
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
freopen("INRANGE.inp", "r", stdin);
freopen("INRANGE.out", "w", stdout);
cin >> n >> a >> b >> p >> mod;
int x = a, y = b;
fenwickTree2D.update(x, y);
long long answer = 0;
int pre = 0;
for (int i = 2; i <= n; i++) {
x = (x + (long long)pre * p + binPow(i + a, a)) % mod + 1;
y = (y + (long long)pre * p + binPow(i + b, b)) % mod + 1;
pre = fenwickTree2D.get(x, y);
fenwickTree2D.update(x, y);
answer += pre;
}
cout << answer << "\n";
return 0;
}
Subtask \(4\) (\(25\%\) số điểm): Không có ràng buộc gì thêm.
Tutorial
Khi phát triển từ subtask 2 lên subtask 3, ta nhận thấy mình đã bỏ bớt một chiều tĩnh của cấu trúc dữ liệu và biến đổi thành cấu trúc dữ liệu động để tối ưu bộ nhớ, nhưng ta hoàn toàn có thể làm tốt hơn nữa.
Ta sẽ thay đổi cả chiều tĩnh còn lại của cấu trúc dữ liệu Fenwick tree và thay thế bằng cấu trúc dữ liệu động.
Solution của ban tổ chức sử dụng Trie lồng trong Trie và có rất nhiều cách giải quyết bài toán khác nhau dựa trên sự lựa chọn cấu trúc dữ liệu cho bài toán này (Trie - Segment tree, Segment tree - Trie, Segment tree - Segment tree).
Độ phức tạp: \(\mathcal{O}(n \cdot log_2(X)^2)\)
Solution
C++
#include <bits/stdc++.h>
using namespace std;
int n, a, b, p, mod;
struct FenwickTree2D {
private:
struct Trie {
private:
const int LOG = 30;
struct Node {
int total;
int children[2];
Node() {
total = 0;
children[0] = children[1] = 0;
}
};
int root, numNode;
vector<Node> nodes;
int getBit(int num, int pos) {
return (num >> pos) & 1;
}
public:
Trie() {
root = numNode = 0;
nodes.push_back(Node());
}
int update(int id, int value, int current = 0) {
for (int i = LOG; i >= 0; i--) {
int x = getBit(id, i);
if (nodes[current].children[x] == 0) {
nodes[current].children[x] = ++numNode;
nodes.push_back(Node());
}
current = nodes[current].children[x];
nodes[current].total += value;
}
return current;
}
int getNode(int id) {
int current = root;
for (int i = LOG; i >= 0; i--) {
int x = getBit(id, i);
current = nodes[current].children[x];
if (current == 0) {
return -1;
}
}
return current;
}
int get(int id, int current) {
int result = 0;
for (int i = LOG; i >= 0; i--) {
int x = getBit(id, i);
if (x == 1 && nodes[current].children[0]) {
result += nodes[nodes[current].children[0]].total;
}
current = nodes[current].children[x];
if (current == 0) {
break;
}
}
return result;
}
};
Trie nodes;
public:
void update(long long x, long long y) {
for (; x <= mod; x += x & -x) {
int node = nodes.update(x, 0);
nodes.update(y, 1, node);
}
}
long long get(long long x, long long y) {
long long result = 0;
x--;
for (; x > 0; x -= x & -x) {
int node = nodes.getNode(x);
if (node != -1) {
result += nodes.get(y, node);
}
}
return result;
}
};
FenwickTree2D fenwickTree2D;
long long binPow(long long a, long long b) {
long long result = 1;
while (b) {
if (b & 1) {
result = result * a % mod;
}
b >>= 1;
a = a * a % mod;
}
return result;
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
freopen("INRANGE.inp", "r", stdin);
freopen("INRANGE.out", "w", stdout);
cin >> n >> a >> b >> p >> mod;
int x = a, y = b;
fenwickTree2D.update(x, y);
long long answer = 0;
int pre = 0;
for (int i = 2; i <= n; i++) {
x = (x + (long long)pre * p + binPow(i + a, a)) % mod + 1;
y = (y + (long long)pre * p + binPow(i + b, b)) % mod + 1;
pre = fenwickTree2D.get(x, y);
fenwickTree2D.update(x, y);
answer += pre;
}
cout << answer << "\n";
return 0;
}
Bình luận