Let $s_{1 \dots n}$ be the string generated after applying the $m$ initial flip updates.
We can make $s$ by directly applying the flips in $O(nm)$ time. For each query, we can then use $O(2^n)$ time to enumerate all possible subsequences and take the lexicographically largest one.
This takes $O(nm + q 2^n)$ time, which runs in time for $n \leq 10, q \leq 1000$.
To make further progress on the problem, we consider the following greedy strategy:
Let $sz = r - l + 1$ and $z$ be the number of $0$'s in $s_{l \dots r}$. Let $t_{1 \dots k}$ be our final string.
Remember that comparing the lexicographical order of two strings $t_1$ and $t_2$ is equivalent to comparing the numbers they interpret in binary.
Thus, our solution that removes all the earliest $0$s (and $1$s when we run out of $0$s) is optimal.
For the sake of simplicity, we will analyze subtask 3 first.
We can loop over the elements in $s_{l \dots r}$ and directly apply our greedy strategy. If there are enough $1$'s, our answer is a string with all ones, otherwise, we remove the first $sz-k$ zeroes. Finally, we can interpret our answer as a binary number with the formula given.
Here is Alex Fan's C++ code:
using namespace std; #include <iostream> #include <set> #include <algorithm> #include <vector> #include <map> #define MAXN 200005 #define MOD 1000000007 int N, M, Q, a[MAXN]; int main() { ios_base::sync_with_stdio(false); cin.tie(0); cin >> N >> M >> Q; for(int i = 0;i < M;++i) { int l, r; cin >> l >> r; l--;r--; for(int i = l;i <= r;++i) { a[i] ^= 1; } } for(int i = 0;i < Q;++i) { int l, r, k; cin >> l >> r >> k; l--;r--; int owo = l; int uwu = 0; for(int i = l;i <= r;++i) { uwu += a[i]; if(uwu + (r - i) >= k) owo = i; } uwu = 0; for(int i = l;i <= owo;++i) uwu += a[i]; if(uwu >= k) { int xwx = 0; for(int i = 0;i < k;++i) { xwx = (2 * xwx + 1) % MOD; } cout << xwx << endl; continue; } int xwx = 0; for(int i = 0;i < uwu;++i) { xwx = (2 * xwx + 1) % MOD; } for(int i = owo + 1;i <= r;++i) { xwx = (2 * xwx + a[i]) % MOD; } cout << xwx << endl; } return 0; }
For subtask 2, we can observe that even though $n$ is large, we can describe it as $O(m)$ intervals of $0$'s or $1$'s. We can still apply our greedy but slightly modified to account for the larger intervals. This approach would require us to raise $2$ a large power modulo $10^9 +7$, which can be efficiently done using binary exponentiation. For more on binary exponentiation, refer to this USACO guide article. This takes $O(mq \log n)$ time, which runs in time for $m \leq 10$.
To improve past $O(n)$ or $O(m)$ per query, we must perform the greedy strategy more efficiently. We can binary search on the index $i$ of the $sz - k + 1$'th zero. This can be done with an auxiliary array $cnt$ that counts the number of $1$'s in the prefix of $1 \dots i-1$. Once we have found it, our string $t$ is $11 \dots 1$ for $i - l$ ones followed by $s_{i \dots r}$. Even though we cannot explicitly store $t$, we can still interpret it.
Suppose we precomputed prefix sums $\text{pre}_{1 \dots n}$ where $\text{pre}_{i} = \sum_{j = 1}^{i-1} s_j \cdot 2^{n - j - 1}$.
Then, $t$ will be intepretted as:
This can be evaluated in $O(\log n)$ or $O(1)$ time depending on how the powers of $2$ and $\frac{1}{2}$ mod $10^9 + 7$ are computed. Note that $\frac{1}{2} \equiv 500000004 \bmod 10^9 + 7$. There is an alternate approach using $pre_{i} = \sum_{j = 1}^{i} s_j \cdot 2^{i - j}$, which does not require inverse mod (division under mod).
This has complexity $O(n \log n + q \log n)$ or $O(n + q \log n)$ as we have to binary search on the index $i$.
Here is my code in C++:
//i dont code with uwus.... qaq #include <iostream> #include <algorithm> #include <vector> #include <array> #include <map> #define sz(x) ((int)(x.size())) #define all(x) x.begin(), x.end() using ll = long long; const ll mod = 1e9 + 7; const ll half = (mod + 1)/2; const int MX = 2e5 + 10; using namespace std; int n, m, q; ll pre[MX], cnt[MX], val[MX]; ll binpow(ll base, int p){ //as all the exponents are <= n, we can also precompute it ll ans = 1; for(int i = 0; (1ll << i) <= p; i++){ if(p&(1ll << i)){ (ans *= base) %= mod; } (base *= base) %= mod; } return ans; } int main(){ cin.tie(0) -> sync_with_stdio(0); cin >> n >> m >> q ; for(int i = 1; i<=m; i++){ int l, r; cin >> l >> r; val[l] ^= 1; val[r+1] ^= 1; } for(int i = 1; i<=n+1; i++){ val[i] ^= val[i-1]; cnt[i] = cnt[i-1] + val[i-1]; pre[i] = pre[i-1] + val[i-1] * binpow(2, n - i + 1); pre[i] %= mod; } while(q--){ int l, r, k; cin >> l >> r >> k; if(cnt[r+1] - cnt[l] >= k){ cout << binpow(2, k) - 1 << "\n"; continue; } int lo = 0, hi = n+1; while(lo + 1 != hi){ int mid = (lo + hi)/2; if(cnt[mid] - cnt[l] + (r + 1 - mid) >= k){ lo = mid; }else{ hi = mid; } } int i = lo; ll front = binpow(2, k) - binpow(2, k - (cnt[i] - cnt[l])); (front += mod) %= mod; ll back = binpow(half, n - r) * (pre[r+1] - pre[i])%mod; (back += mod) %= mod; cout << (front + back)%mod << "\n"; } }
Again, as $n$ is large, we can describe $s$ as $O(m)$ intervals of $0$'s and $1$'s. Additionally, with $q$ queries, we can determine $n' = O(m + q)$ relevant points for which to precompute information. Suppose the start points of these $0$/$1$ and query intervals in sorted order are $e_{1 \dots n'}$.
Imagine the two prefix sums array of length $n$, $cnt$ and $pre$, as the same as defined above. It is not practical to store both arrays explicitly, so we will only store the values at $e_1, e_2, \dots, e_{n'}$. Suppose we defined $cnt'_i = cnt_{e_i}$ and $pre'_{i} = pre_{e_i}$ (and $cnt'_0 = pre'_0 = 0$). We can compute $pre'$ efficiently by computing the powers of $2$ using binary exponentiation.
When we binary search, we find $j$ such that $e_j \leq i < e_{j+1}$. Then as all the elements in $s_{e_j \dots e_{j+1}-1}$ are either all $0$ or all $1$, we can directly solve for $i$ with casework.
When we finally interpret $t$, we can break the sum of $s_{i \dots r}$ into two parts: the prefix of $1$'s and the suffix of our subarray. The suffix of our subarray is given as $(1/2)^{n - r}(pre'_{r+1} - pre'_{i})$. Note that we cannot precompute the value of $pre'_{i}$ (as we don't know what $i$ is), but we can efficiently evaluate it on the fly. This again follows from having a precomputed value up until $e_j$ and knowing that the interval from $e_j$ to $i$ is either all $0$'s or all $1$'s.
This takes $O(\log m)$ time to binary search $i$, and $O(\log n)$ time to compute the powers of two per query. We also need $O((m + q) (\log (m + q) + \log n))$ time to precompute $cnt'$ and $pre'$. This gives our final complexity to be $O((m + q)(\log (m + q) + \log n))$. Other complexity with $\log^2$ complexities might be fast enough to pass.
Here is my C++ code:
//i dont code with uwus.... qaq #include <iostream> #include <algorithm> #include <vector> #include <array> #include <map> #define sz(x) ((int)(x.size())) #define all(x) x.begin(), x.end() using ll = long long; const ll mod = 1e9 + 7; const ll half = (mod + 1)/2; using namespace std; vector<int> e; vector<ll> pre, cnt; vector<int> val; map<int, int> delta; int n, m, q; vector<array<int, 3>> qqs; ll binpow(ll base, int p){ ll ans = 1; for(int i = 0; (1ll << i) <= p; i++){ if(p&(1ll << i)){ (ans *= base) %= mod; } (base *= base) %= mod; } return ans; } #define gind(x) (lower_bound(all(e), x) - e.begin()) int main(){ cin.tie(0) -> sync_with_stdio(0); cin >> n >> m >> q; for(int i = 1; i<=m; i++){ int l, r; cin >> l >> r; delta[l] ^= 1; delta[r+1] ^= 1; e.push_back(l); e.push_back(r+1); } for(int i = 1; i<=q; i++){ int l, r, k; cin >> l >> r >> k; qqs.push_back({l, r, k}); //no need to make queries offline, but makes impl easier e.push_back(l); e.push_back(r+1); } e.push_back(0); e.push_back(n+1); sort(all(e)); e.resize(unique(all(e)) - e.begin()); m = sz(e); //n' val.resize(m); pre.resize(m); cnt.resize(m); for(auto [i, v] : delta){ val[gind(i)] ^= v; } for(int i = 1; i<m; i++){ val[i] ^= val[i-1]; //value of s_e_i cnt[i] += cnt[i-1]; //sum of [0, e_i) pre[i] += pre[i-1]; //sum of [0, e_i) cnt[i] += val[i-1] * (e[i] - e[i-1]); pre[i] += val[i-1] * (binpow(2, n+1 - e[i-1]) - binpow(2, n+1 - e[i])); pre[i] %= mod; } for(auto [l, r, k] : qqs){ int gl = gind(l); int gr = gind(r+1); if(cnt[gr] - cnt[gl] >= k){ cout << binpow(2, k) - 1 << "\n"; continue; } int cntl = cnt[gl]; int lo = 0, hi = m; while(lo + 1 != hi){ int mid = (lo + hi)/2; if(cnt[mid] - cntl + (r - e[mid]) >= k){ lo = mid; }else{ hi = mid; } } int i = cnt[lo] + r - cntl - k; ll front = binpow(2, k) - binpow(2, k - (cnt[lo] - cntl)); ll prei = pre[lo] + val[lo] * (binpow(2, n+1 - e[lo]) - binpow(2, n+1 - i))%mod; (prei += mod) %= mod; ll back = binpow(half, n-r) * (pre[gr] - prei)%mod; (front += mod) %= mod; (back += mod) %= mod; cout << (front + mod + back) % mod << "\n"; } return 0; }
Bonus: Can you solve this in $O(n + q)$ time?