P4062 [Code+#1]Yazid 的新生舞會（線段樹做法）

題意：

給你一個序列a[1…n]?，求存在絕對眾數的子區間個數。

絕對眾數指：區間中出現次數最多的那個數，出現次數嚴格大于區間長度的一半。

題解：

這兩個博客將的很長清楚明白(尤其是第一個)，我在反復看了n遍后，終于明白。題目細節很多，我再怎么寫也沒這兩個詳細，干脆直接放上鏈接。
Zechariah的博客
OMG_wc 的博客
關于題解中提到的三階前綴和:
三階前綴和公式轉換：
圖來自lx_tyin博客

代碼：

#include <bits/stdc++.h> using namespace std; typedef long long LL; const int INF = 0x3f3f3f3f; const LL mod = 1e9 + 7; const int N = 500005; // 修改差分 來維護前綴和的前綴和 // c1 為差分d c2為d*i c3 為d*i*i LL c1[N * 2], c2[N * 2], c3[N * 2]; LL sum(int x) {LL res = 0;for (int i = x; i > 0; i -= i & -i) {res += c1[i] * (x + 2) * (x + 1) - c2[i] * (2 * x + 3) + c3[i];}return res / 2; } void add(int x, LL d, int n) {for (int i = x; i <= n; i += i & -i) {c1[i] += d;c2[i] += d * x;c3[i] += d * x * x;} } int a[N]; vector<int> b[N]; int main() {int n;scanf("%d%*d", &n);for (int i = 1; i <= n; i++) {scanf("%d", &a[i]);b[a[i]].push_back(i);}const int wc = n + 1; // 偏移量，把[-n,n] 平移到 [1,2n+1]LL ans = 0;for (int i = 0; i < n; i++) {b[i].push_back(n + 1);int last = 0;for (int j = 0; j < b[i].size(); j++) {//j表示i的個數int y = 2 * j - last + wc；int x = 2 * j - (b[i][j] - 1) + wc;// 查詢 sum([1,t-1] 的權值和), 其中t在[x,y]范圍內，ans += sum(y - 1) - (x >= 3 ? sum(x - 2) : 0);// [x,y] 這些數的權值+1add(x, 1, 2 * n + 1);add(y + 1, -1, 2 * n + 1);last = b[i][j];}//撤銷操作last = 0;for (int j = 0; j < b[i].size(); j++) {int y = 2 * j - last + wc;int x = 2 * j - (b[i][j] - 1) + wc;add(x, -1, 2 * n + 1);add(y + 1, 1, 2 * n + 1);last = b[i][j];}}printf("%lld\n", ans);return 0; }

總結

以上是生活随笔為你收集整理的P4062 [Code+#1]Yazid 的新生舞会（线段树做法）的全部內容，希望文章能夠幫你解決所遇到的問題。

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