Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- #define _ ios_base::sync_with_stdio(0);cin.tie(0);
- typedef long long ll;
- typedef pair<int, int> ii;
- const int INF = 0x3f3f3f3f;
- const ll LINF = 0x3f3f3f3f3f3f3f3fll;
- chrono::time_point<chrono::high_resolution_clock> beg;
- void reset_time() {
- beg = chrono::high_resolution_clock::now();
- }
- double get_time() {
- auto end = chrono::high_resolution_clock::now();
- chrono::duration<double> elapsed = end - beg;
- return elapsed.count();
- }
- int n;
- std::vector<std::vector<int>> adj;
- int block_size, block_cnt;
- std::vector<int> first_visit;
- std::vector<int> euler_tour;
- std::vector<int> height;
- std::vector<int> log_2;
- std::vector<std::vector<int>> st;
- std::vector<std::vector<std::vector<int>>> blocks;
- std::vector<int> block_mask;
- void dfs(int v, int p, int h) {
- first_visit[v] = euler_tour.size();
- euler_tour.push_back(v);
- height[v] = h;
- for (int u : adj[v]) {
- if (u == p)
- continue;
- dfs(u, v, h + 1);
- euler_tour.push_back(v);
- }
- }
- int min_by_h(int i, int j) {
- return height[euler_tour[i]] < height[euler_tour[j]] ? i : j;
- }
- void precompute_lca(int root) {
- // get euler tour & indices of first occurences
- first_visit.assign(n, -1);
- height.assign(n, 0);
- euler_tour.reserve(2 * n);
- dfs(root, -1, 0);
- // precompute all log values
- int m = euler_tour.size();
- log_2.reserve(m + 1);
- log_2.push_back(-1);
- for (int i = 1; i <= m; i++)
- log_2.push_back(log_2[i / 2] + 1);
- block_size = std::max(1, log_2[m] / 2);
- block_cnt = (m + block_size - 1) / block_size;
- // precompute minimum of each block and build sparse table
- st.assign(block_cnt, std::vector<int>(log_2[block_cnt] + 1));
- for (int i = 0, j = 0, b = 0; i < m; i++, j++) {
- if (j == block_size)
- j = 0, b++;
- if (j == 0 || min_by_h(i, st[b][0]) == i)
- st[b][0] = i;
- }
- for (int l = 1; l <= log_2[block_cnt]; l++) {
- for (int i = 0; i < block_cnt; i++) {
- int ni = i + (1 << (l - 1));
- if (ni >= block_cnt)
- st[i][l] = st[i][l-1];
- else
- st[i][l] = min_by_h(st[i][l-1], st[ni][l-1]);
- }
- }
- // precompute mask for each block
- block_mask.assign(block_cnt, 0);
- for (int i = 0, j = 0, b = 0; i < m; i++, j++) {
- if (j == block_size)
- j = 0, b++;
- if (j > 0 && (i >= m || min_by_h(i - 1, i) == i - 1))
- block_mask[b] += 1 << (j - 1);
- }
- // precompute RMQ for each unique block
- int possibilities = 1 << (block_size - 1);
- blocks.resize(possibilities);
- for (int b = 0; b < block_cnt; b++) {
- int mask = block_mask[b];
- if (!blocks[mask].empty())
- continue;
- blocks[mask].assign(block_size, std::vector<int>(block_size));
- for (int l = 0; l < block_size; l++) {
- blocks[mask][l][l] = l;
- for (int r = l + 1; r < block_size; r++) {
- blocks[mask][l][r] = blocks[mask][l][r - 1];
- if (b * block_size + r < m)
- blocks[mask][l][r] = min_by_h(b * block_size + blocks[mask][l][r],
- b * block_size + r) - b * block_size;
- }
- }
- }
- }
- int lca_in_block(int b, int l, int r) {
- return blocks[block_mask[b]][l][r] + b * block_size;
- }
- int lca(int v, int u) {
- int l = first_visit[v];
- int r = first_visit[u];
- if (l > r)
- std::swap(l, r);
- int bl = l / block_size;
- int br = r / block_size;
- if (bl == br)
- return euler_tour[lca_in_block(bl, l % block_size, r % block_size)];
- int ans1 = lca_in_block(bl, l % block_size, block_size - 1);
- int ans2 = lca_in_block(br, 0, r % block_size);
- int ans = min_by_h(ans1, ans2);
- if (bl + 1 < br) {
- int l = log_2[br - bl - 1];
- int ans3 = st[bl+1][l];
- int ans4 = st[br - (1 << l)][l];
- ans = min_by_h(ans, min_by_h(ans3, ans4));
- }
- return euler_tour[ans];
- }
- int main(int argc, char** argv) { _
- srand(atoi(argv[1]));
- cin >> n;
- vector<int> v(n);
- for (int& i : v) i = rand()%n;
- vector<pair<int, int>> q(1000000);
- for (int i = 0; i < 1000000; i++) {
- int a = rand()%n, b = rand()%n;
- if (a > b) swap(a, b);
- q[i] = {a, b};
- }
- cout << "LCA using Farach-Colton and Bender" << '\n';
- reset_time();
- vector<int> parent(n, -1);
- stack<int> s;
- for (int i = 0; i < n; i++) {
- int last = -1;
- while (!s.empty() && v[s.top()] >= v[i]) {
- last = s.top();
- s.pop();
- }
- if (!s.empty())
- parent[i] = s.top();
- if (last >= 0)
- parent[last] = i;
- s.push(i);
- }
- adj.resize(n);
- int root = -1;
- for (int i = 0; i < n; i++) {
- if (parent[i] >= 0)
- adj[parent[i]].push_back(i);
- else
- root = i;
- }
- precompute_lca(root);
- double build_time = get_time();
- ll sum = 0;
- reset_time();
- for (auto i : q) sum += v[lca(i.first, i.second)];
- double query_time = get_time();
- cout << sum << '\n';
- cout << int(1000*build_time) << " " << int(1000*query_time) << '\n';
- exit(0);
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement