Lập trình thi đấu

Chặt nhị phân song song

Sử dụng cho các bài toán cần chặt nhị phân nhiều lần

Nguồn tham khảo

Cần biết trước

Tìm kiếm nhị phân (tất nhiên vì bạn cần phải hiểu cách tìm kiếm nhị phân hoạt động).

Mở đầu

Trong một số bài toán. Ta cần sử dụng kĩ thuật tìm kiếm nhị phân cho rất nhiều truy vấn. Trong đó có một số thao tác trong lúc chặt nhị phân được lặp lại nhiều lần. Để tối ưu hóa việc này, ta thực hiện chặt nhị phân song song - tức chặt nhị phân cùng một lúc nhiều truy vấn.

Bài toán

Ta xét bài toán sau đây: Meteors.

Đề bài

Bài toán có thể được phát biểu đơn giản như sau:

Cho $N$ người và $M$ cái túi. Túi thứ $i$ được sở hữu bởi người thứ $o_i$, và mỗi người cần ít nhất $g_i$ quả táo trong các túi mà mình sở hữu. Các cái túi được xếp theo thứ tự thành vòng tròn.

Sau đó, có $K$ sự kiện lần lượt xảy ra, mỗi sự kiện có dạng $l_i, r_i, x_i$: các túi được đánh số từ $l_i$ đến $r_i$ được tăng thêm $x_i$ quả táo ($l_i$ có thể lớn hơn $r_i$ do các túi được xếp thành vòng tròn).

Với mỗi người, cho biết sau ít nhất bao nhiêu sự kiện thì người đó đạt đủ số lượng quả táo mà mình muốn.

Giới hạn

  • $1 \leq N, M, K \leq 3 \cdot 10^5$
  • $1 \leq o_i, l_i, r_i \leq N$
  • $1 \leq g_i, x_i \leq 10^9$

Phân tích

Cách tiếp cận dễ nhận ra đó là với mỗi người, ta tiến hành tìm kiếm nhị phân số lượng sự kiện, sau đó cập nhật từng sự kiện lên cây phân đoạn hoặc cây Fenwick. Tuy nhiên, tổng độ phức tạp thời gian cho cách này sẽ lên tới $\mathcal{O}(N \cdot \log K \cdot K \cdot \log M)$ và tất nhiên sẽ bị TLE.

Từ đây ta nhận ra việc tìm kiếm nhị phân lần lượt cho $N$ là không khả thi. Vậy nên ta sẽ tìm cách áp dụng kĩ thuật chặt nhị phân song song.

Lời giải

Từ phân tích trên, ta nhận thấy việc cập nhật các sự kiện từ đầu đến một vị trí nào đó trong các lần chặt nhị phân đã bị lặp lại nhiều lần. Ví dụ như, trong lượt chặt nhị phân đầu tiên của mỗi người, ta đều cần cập nhật lại các sự kiện từ $1$ đến $\frac{K+1}{2}$.

Từ đây ta sẽ tiếp cận việc tìm kiếm nhị phân theo một hướng khác: thay vì chặt nhị phân $N$ lần cho từng người, thì ta chỉ chặt nhị phân $1$ lần sao cho trong mỗi lượt, ta tiến hành “chia nhóm” $N$ người theo kết quả.

Cụ thể, trong lượt đầu tiên, mọi người đều chung một nhóm $[1, K]$. Sang lượt thứ hai, sẽ có một số người nằm ở nhóm $[1, \frac{K}{2}]$ và số còn lại ở nhóm $(\frac{K}{2}, K]$ tùy theo điều kiện thỏa mãn hay không. Đến lượt thứ ba, ta có $4$ nhóm: $[1, \frac{K}{4}]$, $(\frac{K}{4}, \frac{2K}{4}]$, $(\frac{2K}{4}, \frac{3K}{4}]$, và $(\frac{3K}{4}, K]$. Như vậy, sau khoảng $\mathcal{O}(\log K)$ lượt, mọi người đều được chia vào một điểm, điểm này sẽ chính là đáp án cho người đó. Đồng thời, ở mỗi lượt, ta chỉ cần thực hiện cập nhật lần lượt $K$ sự kiện là có thể tính được cho $N$ người và chia nhóm cho $N$ người đó.

Độ phức tạp: Do mỗi thao tác cập nhật $K$ sự kiện mất $\mathcal{O}(\log M)$, nên độ phức tạp của thuật toán này là $\mathcal{O}(\log Q \cdot Q \cdot \log M)$, vừa đủ với giới hạn đề bài.

Cài đặt

Ta cần chuẩn bị:

  • Một cấu trúc dữ liệu cho phép cập nhật đoạn và truy vấn một phần tử (có thể dùng cây Fenwick hoặc cây phân đoạn)
  • Một mảng check_list với check_list[x] lưu danh sách những người đang chặt nhị phân tại vị trí $\text{mid} = x$
  • Các mảng $L[i], R[i], \text{best}[i]$ dùng để lưu trạng thái chặt nhị phân của người thứ $i$.

Mỗi lượt trong $\log K$ lượt chặt nhị phân, ta thực hiện như sau:

  • Khởi tạo lại cây Fenwick/phân đoạn.
  • Khởi tạo lại mảng check_list
  • Xác định vị trí chặt nhị phân $\text{mid}[i] = \frac{L[i]+ R[i]}{2}$ cho từng người và thêm vào check_list[mid[i]]
  • Duyệt lần lượt các sự kiện và cập nhật lên cây Fenwick/phân đoạn. Khi duyệt đến vị trí $x$ thì duyệt từng người trong check_list[x], tính tổng và cập nhật $L[i], R[i], \text{best}[i]$ cho người đó. Như vậy trong mỗi lượt ta cập nhật cho cây Fenwick đúng $K$ lần, và gọi truy vấn phần tử trên cây cho đúng $M$ cái túi.
Code AC của mình 
  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
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151

// Created by BJMinhNhut
#include <bits/stdc++.h>
using namespace std;
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define FOR(i, a, b) for(int i = (a), _b = (b); i <= _b; ++i) 
#define FORD(i, a, b) for(int i = (a), _b = (b); i >= _b; --i)
#define ALL(a) (a).begin(), (a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define MASK(i) (1ll<<(i))
#define BIT(t, i) (((t)>>(i))&1)
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef pair<ll, ll> pll;
typedef pair<int, int> ii;

/***Common Functions***/
template <class T>
bool minimize(T &a, T b) {
	if (a > b) {
		a = b;
		return true;
	}
	return false;
}

template <class T>
bool maximize(T &a, T b) {
	if (a < b) {
		a = b;
		return true;
	}
	return false;
}

/***End of Template***/
int n, m;
const int N = 3e5+5;
int owner[N];	
int goal[N];
int k;
struct Query {
	int l, r, val;
} queries[N];

struct BinarySearch {
	int l, r, best;

	BinarySearch(int _l = 0, int _r = 0): l(_l), r(_r), best(_r+1) {}

	int getMid() {return (l+r) >> 1;}

	bool finished() {return l > r;}

	void update(bool go_left) {
		if (go_left) {
			best = getMid();
			r = getMid() - 1;
		} else l = getMid() + 1;
	}
} state[N];

struct Fenwick {
	ll nodes[N];

	void reset() {
		memset(nodes, 0, sizeof nodes);
	}

	void update(int k, int val) {
		for(; k < N; k += k&-k) nodes[k] += val;
	}

	void rangeUpdate(int l, int r, int val) {
		update(l, val);
		update(r+1, -val);
	}

	ll getSum(int k) {
		ll ans = 0;
		for(; k > 0; k -= k&-k) ans += nodes[k];
		return ans;
	}
} FT;

vi check_list[N];
vi sectors[N];

void Input() {
	cin >> n >> m;
	FOR(i, 1, m) cin >> owner[i], sectors[owner[i]].pb(i);
	FOR(i, 1, n) cin >> goal[i];
	cin >> k;
	FOR(i, 1, k) {
		cin >> queries[i].l >> queries[i].r >> queries[i].val;
	}
}

void update(int l, int r, int val) {
	if (l <= r) FT.rangeUpdate(l, r, val);
	else {
		FT.rangeUpdate(l, m, val);
		FT.rangeUpdate(1, r, val);
	}
}

void Solve() {
	//init
	FOR(i, 1, n) state[i] = BinarySearch(1, k); // binary search in the range [1, k] 

	bool changed = true;
	while (changed) {
		changed = false; // check whether any state[i] changed

		//init
		FT.reset();
		FOR(i, 1, n) if (!state[i].finished()) 
			check_list[state[i].getMid()].pb(i);

		FOR(mid, 1, k) { //sweep through k queries
			update(queries[mid].l, queries[mid].r, queries[mid].val);
			while (check_list[mid].size()) { //check every person who currently has mid = i in binary search
				changed = true;
				int cur = check_list[mid].back(); check_list[mid].pop_back();
				ll sum = 0;
				for(int x : sectors[cur]) {
					sum += FT.getSum(x);
					if (sum >= goal[cur]) break;
				}
				state[cur].update(sum >= goal[cur]); // go left when meet the goal
			}
		}
	}

	FOR(i, 1, n) 
		if (state[i].best <= k) cout << state[i].best << '\n'; //print binary search result
		else cout << "NIE\n";
}

int main() {
	ios::sync_with_stdio(0); cin.tie(0);
	if (fopen("inputf.in", "r")) {
		freopen("inputf.in", "r", stdin);
		freopen("outputf.in", "w", stdout);
	}
	Input(), Solve();
	return 0;
}

Tổng kết

“A cool way to visualize this is to think of a binary search tree. Suppose we are doing standard binary search, and we reject the right interval — this can be thought of as moving left in the tree. Similarly, if we reject the left interval, we are moving right in the tree.

So what Parallel Binary Search does is move one step down in N binary search trees simultaneously in one “sweep”, taking $\mathcal{O}(NX)$ time, where X is dependent on the problem and the data structures used in it. Since the height of each tree is $\log N$, the complexity is $\mathcal{O}(NX\log{N})$.” — animeshf

Mình xin phép dịch lại như sau: Một cách đơn giản, chặt nhị phân song song tức là ta vẽ ra một cây tìm kiếm nhị phân. Cứ mỗi lượt ta duyệt một tầng, và đẩy các phần tử trong mỗi nút thuộc tầng này sang hai nút trái hoặc phải ở tầng dưới. Việc này được thực hiện chỉ trong $\mathcal{O}(NX)$ với $X$ tùy thuộc vào từng bài toán và cấu trúc dữ liệu mà ta sử dụng. Từ đó dẫn đến tổng độ phức tạp thuật toán là $\mathcal{O}(NX\log{N})$.

Ngoài ra, cách xử lí truy vấn ở bài toán trên chỉ là một trường hợp cụ thể, trong các trường hợp khác, về tổng quát, ta cần tư duy rằng ở mỗi tầng, ta có danh sách các truy vấn mới được tạo ra từ việc tìm $\text{mid}[i]$ và ta cần đi giải quyết nhanh các truy vấn này.

Một số bài tập khác

© 2022 - 2023 BJMinhNhut Blog
Dựng bởi Hugo
Theme Stack thiết kế bởi Jimmy