題意

給定一個正整數序列 \(a_1, a_2, \cdots, a_n\) ，求
\[ \sum_{i=1}^{n} \sum_{j=i}^{n} (j - i + 1) \min(a_i,a_{i+1},\cdots,a_j) \max(a_i,a_{i+1},\cdots,a_j) \pmod {10^9} \]
\(n \le 5\times 10^5, a_i \le 10^9\)

題解

對于這種求一段區間內所有子區間答案和的東西，我們常常可以考慮分治解決。

通常思路是這樣的：

假設我們計算 \([l, r]\) 這段區間的答案和。令 \(\displaystyle mid = \lfloor \frac{l + r}{2} \rfloor\) 。

我們分治計算全在 \([l, mid]\) 以及 \([mid + 1, r]\) 區間的答案。

然后計算跨過 \(mid\) 的區間的答案。也就是左端點在 \([l, mid]\) 并且右端點在 \([mid + 1, r]\) 中的區間。

最后所有區間答案加起來就行了，正確性是顯而易見的，因為一個區間要么全在左邊，要么全在右邊，要么跨過中點。

接下來難點就在跨過區間的答案計算上。

通常的話我們可以枚舉一個端點，快速計算另外一個端點的貢獻。

首先可以從 \(mid\) 到 \(l\) 枚舉這個區間的左端點 \(x\) ，令 \([x, mid]\) 的最小值為 \(a\) ，最大值為 \(b\) 。

兩個單調指針 \(p,q\) 從 \(mid\) 向右走（最多到 \(r\) ），分別指向使得 \([mid/x, i]\) 最小值/最大值 為 \(a\) / \(b\) 的最大位置 \(i\) 。

我們把區間右端點 \(y\) 分三種情況討論。

對于 \(y \in [mid + 1, \min \{p, q\}]\) 這一部分 \(\min = a, \max = b\) 。那么答案就是
\[ \sum_{y=mid+1}^{ \min \{p, q\}} (y - x + 1) \times a \times b \]
這部分用高斯求和優化即可。

對于 \(y \in (\min \{p, q\}, \max \{p, q\}]\) 這部分，會有兩種情況，本質是一樣的。

我們討論 \(p < q\) 這種，那么答案就是
\[ \sum_{y=\min \{p, q\}+1}^{\max \{p, q\}} (\min_{k = mid}^{y} a_k) \times(y - x + 1) \times b \]
我們可以考慮預處理 \(\displaystyle \sum_{y=1}^{n} (\min_{k = mid}^{y}a_k)~y\) 以及 \(\displaystyle \sum_{y=1}^{n} (\min_{k = mid}^{y}a_k)\) 就行了。那么每次計算就是前綴和相減，然后乘上系數就行了。

對于最后一部分 \(y \in (\max \{p, q\}, r]\) ，那么我們類似與上面那個式子處理
\[ \sum_{y=\max \{p, q\}+1}^{r} (\min_{k = mid}^{y} a_k) (\max_{k = mid}^{y} a_k) \times(y - x + 1) \]
那么我們只需要考慮預處理 \(\displaystyle \sum_{y=1}^{n}(\min_{k = mid}^{y} a_k)(\max_{k = mid}^{y} a_k)~y\) 以及 \(\displaystyle \sum_{y=1}^{n}(\min_{k = mid}^{y} a_k)(\max_{k = mid}^{y} a_k)\) ，類似于上面那個式子前綴和相減就行了。

然后這樣就可以做完了，每次操作只需要掃一遍區間，所以復雜度就是 \(O(n \log n)\) 的。

總結

考慮所有子區間答案，或者所有點對的答案，可以嘗試考慮分治。

然后繼續考慮枚舉一個端點，另外一個端點用一些特殊結構快速計算就行了。

代碼

#include <bits/stdc++.h>#define For(i, l, r) for(register int i = (l), i##end = (int)(r); i <= i##end; ++i) #define Fordown(i, r, l) for(register int i = (r), i##end = (int)(l); i >= i##end; --i) #define Set(a, v) memset(a, v, sizeof(a)) #define Cpy(a, b) memcpy(a, b, sizeof(a)) #define debug(x) cout << #x << ": " << x << endl #define DEBUG(...) fprintf(stderr, __VA_ARGS__)using namespace std;inline bool chkmin(int &a, int b) {return b < a ? a = b, 1 : 0;} inline bool chkmax(int &a, int b) {return b > a ? a = b, 1 : 0;}inline int read() {int x = 0, fh = 1; char ch = getchar();for (; !isdigit(ch); ch = getchar()) if (ch == '-') fh = -1;for (; isdigit(ch); ch = getchar()) x = (x << 1) + (x << 3) + (ch ^ 48);return x * fh; }void File() { #ifdef zjp_shadowfreopen ("3745.in", "r", stdin);freopen ("3745.out", "w", stdout); #endif }const int N = 5e5 + 1e3, inf = 0x7f7f7f7f, Mod = 1e9;int n, a[N]; int ans = 0;int Sum(int l, int r) { return (1ll * (r - l + 1) * (r + l) / 2) % Mod; }int SMM[N], SMMP[N], SMax[N], SMin[N], SMaxp[N], SMinp[N]; int Minv[N], Maxv[N]; // SumMaxMin SunMaxMinPos SumMax SumMin SumMaxPos SumMinpos MinVal MaxValinline int Add(int a, int b) {return (a += b) >= Mod ? a - Mod : a; }void Solve(int l, int r) {if (l == r) { ans = Add(ans, 1ll * a[l] * a[r] % Mod); return ; }int mid = (l + r) >> 1; Solve(l, mid); Solve(mid + 1, r);int p = mid, q = mid; int minl = a[mid], maxl = a[mid];SMM[mid] = SMMP[mid] = SMax[mid] = SMin[mid] = SMaxp[mid] = SMinp[mid] = 0;For (i, mid + 1, r) {if (i == mid + 1) {Minv[i] = Maxv[i] = SMax[i] = SMin[i] = a[i];SMinp[i] = SMaxp[i] = 1ll * a[i] * i % Mod;SMM[i] = 1ll * a[i] * a[i] % Mod; SMMP[i] = 1ll * i * a[i] % Mod * a[i] % Mod;continue ;}Minv[i] = min(a[i], Minv[i - 1]); Maxv[i] = max(a[i], Maxv[i - 1]);SMin[i] = Add(SMin[i - 1], Minv[i]);SMax[i] = Add(SMax[i - 1], Maxv[i]);SMinp[i] = Add(SMinp[i - 1], 1ll * Minv[i] * i % Mod);SMaxp[i] = Add(SMaxp[i - 1], 1ll * Maxv[i] * i % Mod);SMM[i] = Add(SMM[i - 1], 1ll * Minv[i] * Maxv[i] % Mod);SMMP[i] = Add(SMMP[i - 1], 1ll * i * Minv[i] % Mod * Maxv[i] % Mod);}Fordown (i, mid, l) {chkmin(minl, a[i]); chkmax(maxl, a[i]);while (p < r && Minv[p + 1] >= minl) ++ p;while (q < r && Maxv[q + 1] <= maxl) ++ q;int gapl = min(p, q), gapr = max(p, q);ans = Add(ans, 1ll * Sum(mid - i + 2, gapl - i + 1) * minl % Mod * maxl % Mod);if (p < q) ans = Add(ans, (((SMinp[q] - SMinp[p]) - 1ll * (SMin[q] - SMin[p]) * (i - 1)) % Mod + Mod) * maxl % Mod);if (p > q) ans = Add(ans, (((SMaxp[p] - SMaxp[q]) - 1ll * (SMax[p] - SMax[q]) * (i - 1)) % Mod + Mod) * minl % Mod);ans = Add(ans, (((SMMP[r] - SMMP[gapr]) - 1ll * (SMM[r] - SMM[gapr]) * (i - 1)) % Mod + Mod) % Mod);} }int main () {File();n = read(); For (i, 1, n) a[i] = read();Solve(1, n);printf ("%d\n", ans);return 0; }

轉載于:https://www.cnblogs.com/zjp-shadow/p/9483629.html

總結

以上是生活随笔為你收集整理的BZOJ 3745: [Coci2015]Norma（分治）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。