Solutions of Product

Select solution language

Write solution here.

bean Created at 19 likes

Ta sẽ sử dụng kĩ thuật chia để trị để giải quyết bài toán này trong

$\mathcal{O}(n \times log(n))$ Xét trên đoạn

$[l, r]$ , ta chia đoạn này thành 2 nửa,

$[l, mid]$ và

$[mid + 1, r]$ , với

$mid$ là điểm nằm giữa

$l$ và

$r$ . Cố định

$i$ bằng cách duyệt

$i$ trên đoạn

$[l, mid]$ , khi này, ta có thể chia thành 4 trường hợp: -

$x, y \in [i, mid]$ -

$x, y \in [mid + 1, r]$ -

$x \in [i, mid]$ , còn

$y \in [mid + 1, r]$ -

$y \in [i, mid]$ , còn

$x \in [mid + 1, r]$ Với:

$x = min(a_i, a_{i + 1}, a_{i + 2}, ..., a_{mid})$

$y = max(a_i, a_{i + 1}, a_{i + 2}, ..., a_{mid})$ Gọi

$j$ là vị trí đầu tiên thuộc

$[mid + 1, r]$ mà

$a_j < x$ . Tương tự, gọi

$k$ là vị trí đầu tiên thuộc

$[mid + 1, r]$ mà

$a_k > y$ . Ta có thể tìm vị trí này bằng cách dùng hai con trỏ Như vậy, với mọi vị trí thuộc khoảng

$[i, min(j, k) - 1]$ đều sẽ rơi vào trường hợp 1, đáp án ở đây là

$(min(j, k) - mid - 1) \times x \times y$ Tương tự, với mọi vị trí thuộc khoảng

$[max(j, k) + 1, r]$ đều sẽ rơi vào trường hợp 2, đáp án là tổng

$min(a_{mid}, a_{mid + 1}, ..., a_{p}) \times max(a_{mid}, a_{mid + 1}, ..., a_{p})$ với

$p \in [max(j, k) + 1, r]$ ta có thể tính nhanh tổng ở đây bằng mảng tiền tố. Còn lại trường hợp 3, và 4. Khi này: - Nếu

$j < k$ , ta sẽ lấy

$x$ và tổng của

$min(a_{mid + 1}, a_{mid + 2}, ..., a_{p})$ , với

$p \in (j, k]$ , ta có thể tính nhanh tổng này bằng mảng tiền tố - Ngược lại, nếu

$j > k$ , ta cũng có thể làm tương tự, nhưng với

$y$ và tổng của max trên đoạn. **Code tham khảo:**

$cpp #include "bits/stdc++.h" using namespace std; #ifdef LOCAL #include "debug.h" #else #define debug(...) 42 #endif #define int int64_t int32_t main() { cin.tie(0)->sync_with_stdio(0); int n; cin >> n; vector<int> a(n); for (int i = 0; i < n; i++) { cin >> a[i]; } int res = 0; const int inf = 1e9; vector<int> pre(n), smn(n), smx(n); const int mod = (int)1e9 + 7; auto add = [&](int x, int y) { x += y; if (x >= mod) { x -= mod; } if (x < 0) { x += mod; } return x; }; auto mult = [&](int x, int y) -> int { return 1ll * x * y % mod; }; function<void(int, int)> dnc = [&](int l, int r) { if (l == r) { res += mult(a[l], a[l]); return; } int mid = (l + r) >> 1; dnc(l, mid); dnc(mid + 1, r); int mn = inf, mx = -inf; smn[mid] = smx[mid] = pre[mid] = 0; for (int i = mid + 1; i <= r; i++) { mn = min(mn, a[i]); mx = max(mx, a[i]); smn[i] = add(smn[i - 1], mn); smx[i] = add(smx[i - 1], mx); pre[i] = add(pre[i - 1], mult(mn, mx)); } mn = inf, mx = -inf; int i = mid, j = mid + 1, k = mid + 1; while (i >= l) { mn = min(mn, a[i]); mx = max(mx, a[i]); while (j <= r && a[j] >= mn) { j++; } while (k <= r && a[k] <= mx) { k++; } if (j < k) { res = add(res, mult(j - mid - 1, mult(mn, mx))); res = add(res, mult(mx, add(smn[k - 1], -smn[j - 1]))); res = add(res, add(pre[r], -pre[k - 1])); } else { res = add(res, mult(k - mid - 1, mult(mn, mx))); res = add(res, mult(mn, add(smx[j - 1], -smx[k - 1]))); res = add(res, add(pre[r], -pre[j - 1])); } i--; } }; dnc(0, n - 1); cout << res; }$