P4062 [Code+#1]Yazid 的新生舞會

題意：

給出一個序列，求有多少個子區間滿足眾數的出現次數大于區間長度的一半。
出現次數大于區間長度的一般我們稱之為絕對眾數

題解：

分治做法
對于一個區間[l,r]，設mid=$?\frac{l+r}{2}?$,我們只需要求出所有經過mid的區間內能夠成為眾數的所有數,不橫跨mid位置的子區間總會在一個二分統計中計算

有這樣一個性質：如果x是區間[l,r]的絕對眾數，對于l<=k<=r,x一定是區間[l,k]或區間(k,r]的眾數
利用這個性質，我們可以令k=mid。

我們只需要求出區間[x,mid] (l<=x<mid)和區間[mid,y] (mid<y<=r)的眾數，就可以得知所有橫跨mid 的子區間的眾數。這樣就可以O(n)從mid出發往左右兩邊掃，求出所有能成為眾數的數。

找出來的區間眾數個數不會大于log(區間長度)

設當然枚舉到的眾數為nownum，問題就變成：有多少橫跨mid的子區間中包含一半以上的nownum

這里用到一個高級的轉化：我們將區間中不是nownum的數變成-1，是nownum的變成1，這樣問題就變成：有多少橫跨mid的子區間的和大于0
因為子區間橫跨mid，我們設左端點為x(x一定在[l,mid]中)，右端點為y(y一定在[mid+1,r]中)
我們求一個前綴和sum，如果子區間是符合要求的，那一定滿足sum[y]-sum[x-1]>0,移項后sum[y]>sum[x-1]，也就是對于每一個sum[y]，有多少個sum[x-1]是符合要求的。我們可以開一個桶，把所有sum[x-1]存進去，然后桶求個前綴和，這樣就可以O(1)直到有多少個sum[x-1]是小于sum[y]的了
sum[x-1]的前綴和有可能是負數，所以加一個偏移量n
遞歸樹中，每一層區間長度加起來是n，可能的眾數個數有log n個，每一層的復雜度是O(nlogn).總共有log n層，總復雜度是$O(nlo{g}^{2}n)$

代碼：

// Problem: P4062 [Code+#1]Yazid 的新生舞會 // Contest: Luogu // URL: https://www.luogu.com.cn/problem/P4062 // Memory Limit: 500 MB // Time Limit: 4000 ms // Data:2021-08-11 14:54:52 // By Jozky#include <bits/stdc++.h> #include <unordered_map> #define debug(a, b) printf("%s = %d\n", a, b); using namespace std; typedef long long ll; typedef unsigned long long ull; typedef pair<int, int> PII; clock_t startTime, endTime; //Fe~Jozky const ll INF_ll= 1e18; const int INF_int= 0x3f3f3f3f; template <typename T> inline void read(T& x) {T f= 1;x= 0;char ch= getchar();while (0 == isdigit(ch)) {if (ch == '-')f= -1;ch= getchar();}while (0 != isdigit(ch))x= (x << 1) + (x << 3) + ch - '0', ch= getchar();x*= f; } template <typename T> inline void write(T x) {if (x < 0) {x= ~(x - 1);putchar('-');}if (x > 9)write(x / 10);putchar(x % 10 + '0'); } void rd_test() { #ifdef ONLINE_JUDGE #elsestartTime= clock();freopen("in.txt", "r", stdin); #endif } void Time_test() { #ifdef ONLINE_JUDGE #elseendTime= clock();printf("\nRun Time:%lfs\n", (double)(endTime - startTime) / CLOCKS_PER_SEC); #endif } const int maxn= 5e5; int a[maxn]; ll ans; int n, m; int num[maxn], t, tot[maxn]; int isnum[maxn]; int sum[maxn * 2]; void solve(int l, int r) {if (l == r) {ans++;return;}int mid= (l + r) >> 1;solve(l, mid);solve(mid + 1, r);t= 0;for (int i= mid; i >= l; i--) {tot[a[i]]++; //記錄出現次數//如果出現次數大于區間長度的一半，并且還沒有加入過，就加入數組if (tot[a[i]] > (mid - i + 1) / 2) {if (!isnum[a[i]]) {isnum[a[i]]= 1;num[++t]= a[i];}}}for (int i= mid; i >= l; i--)tot[a[i]]= 0;for (int i= mid; i <= r; i++) {tot[a[i]]++;if (tot[a[i]] > (i - mid) / 2) {if (!isnum[a[i]]) {isnum[a[i]]= 1;num[++t]= a[i];}}}for (int i= l; i <= r; i++)tot[a[i]]= 0, isnum[a[i]]= 0;int s, nownum;for (int k= 1; k <= t; k++) {s= 0;nownum= num[k]; //枚舉現在所有的眾數sum[s + n]++;for (int i= l; i < mid; i++) {s+= (a[i] == nownum ? 1 : -1);sum[s + n]++;}s+= (a[mid] == nownum ? 1 : -1);int len= r - l + 1;for (int i= -len; i <= len; i++) {sum[i + n]+= sum[i + n - 1];}for (int i= mid + 1; i <= r; i++) {s+= (a[i] == nownum ? 1 : -1);ans+= sum[s + n - 1];}for (int i= -len; i <= len; i++) {sum[i + n]= 0;}} } int main() {//rd_test();cin >> n >> m;for (int i= 1; i <= n; i++)cin >> a[i];solve(1, n);printf("%lld\n", ans);//Time_test(); }

總結

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

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