Official Analysis

Implementation

Time complexity: $\mathcal{O}(N \log N + Q \log N)$. $\mathcal{O}(N \log N)$ from generating the sparse tables, and $\mathcal{O}(Q \log N)$ from processing the LCA.

Copy
#include <bits/stdc++.h>

using namespace std;

using ll = long long;
const int MOD = 1e9 + 7;

 Code Snippet: ModInt (Click to expand)

// equivalent to dividing by 1000000