D. Cut and Stick

（賽后補(bǔ)題）借本題學(xué)習(xí)莫隊算法以及區(qū)間眾數(shù)的求法

題意：對于整型數(shù)組，每次詢問$[L,R]$區(qū)間問最少分為多少個子序列，使得每個子序列的眾數(shù)$x$的個數(shù)$cn{t}_x$不大于 $?\frac{len}{2}?$，$len$表示子序列的長度

思路：對于每次詢問只需知道詢問區(qū)間內(nèi)的眾數(shù)$x$的個數(shù)即可，最優(yōu)解即為將其余的非眾數(shù)盡可能與更多的$x$組合為一個子序列，而剩下的$x$每個自為一個子序列

給一個不嚴(yán)格的證明，圖中有$a$個眾數(shù)與$b$個非眾數(shù)，法①將全部的非眾數(shù)放在同一個子序列中，此時該子序列最多匹配$b+1$個眾數(shù)，而剩余的眾數(shù)則需單獨(dú)出現(xiàn)；法②將b個非眾數(shù)分為兩部分（$c+d=b$），兩部分分別匹配$c+1$和$d+1$個眾數(shù)（$c+1+d+1=c+d+2=b+2$）此時比法①多匹配了一個眾數(shù)，然而由于被分為兩部分，自然地也多產(chǎn)生了一個子序列，因此兩者是等效的，可見只要將盡可能多的眾數(shù)匹配給非眾數(shù)，無論非眾數(shù)分為多少塊其效果是等效的

因此問題便轉(zhuǎn)化為求區(qū)間眾數(shù)的個數(shù)問題。
數(shù)組長度：$n$，詢問次數(shù)：$m$
若采用暴力求解，每次詢問計算眾數(shù)的個數(shù)的時間復(fù)雜度為$O(n)$，總時間復(fù)雜度為$O(m?n)$，會超時
采用莫隊算法優(yōu)化，可將每次詢問的平均時間復(fù)雜度降為$O(\sqrt{n})$

莫隊步驟：

將數(shù)組分為大小為$\sqrt{n}$的塊

將詢問順序按下面的規(guī)則排序
首先按照$L$所在的塊號排序，塊號越小越靠前（升序）
若$L$所在的塊號相同，則按$R$所在的塊號升序

接著定義兩個函數(shù)$add()$和$del()$分別用于添加和刪除元素，用于在上一個詢問的區(qū)間基礎(chǔ)上增刪元素得到當(dāng)前詢問的區(qū)間，每次調(diào)用增刪函數(shù)的關(guān)鍵是動態(tài)地更新眾數(shù)的狀態(tài)

維護(hù)眾數(shù)狀態(tài)：
采用$map$映射存儲每個數(shù)出現(xiàn)的次數(shù)，采用數(shù)組$a$記錄有多少個數(shù)出現(xiàn)了$i$次，當(dāng)前的眾數(shù)的個數(shù)即為數(shù)組$a[i]>0$的最大的$i$，每次增刪實(shí)時更新兩者的數(shù)據(jù)即可

#include<bits/stdc++.h> #define debug1(x) cout<<#x<<":"<<x<<endl #define fastio() ios_base::sync_with_stdio(0);cin.tie(0) typedef long long ll; typedef unsigned long long ull; const int N = (int)3e5+100; const int RN = sqrt(N)+10; const int MOD = 10000; using namespace std; int a[N]; map<int,int> mp[RN]; int n,m,block; int cnt[N],sum[N],ans[N],max_cnt = 0; struct query {int id;int l;int r; }q[N];bool cmp(query a, query b) {int al = a.l / block, bl = b.l / block;int ar = a.r / block, br = b.r / block;if(al != bl) return al < bl;return ar < br; }void add(int e) {sum[cnt[e]]--;cnt[e]++;sum[cnt[e]]++;max_cnt = max(max_cnt, cnt[e]); }void del(int e) {sum[cnt[e]]--;if(cnt[e] == max_cnt && sum[cnt[e]] == 0) max_cnt--;cnt[e]--;sum[cnt[e]]++; }int main() {cin>>n>>m;block = sqrt(n);for(int i = 1; i <= n; i++) scanf("%d",&a[i]);int l, r;for(int i = 0; i < m; i++){scanf("%d%d",&l,&r);q[i].id = i;q[i].l = l;q[i].r = r;}sort(q, q + m, cmp);int cl, cr, width;cl = cr = 0; add(a[0]);for(int i = 0; i < m; i++){l = q[i].l, r = q[i].r;while(cr < r) add(a[++cr]);while(cl > l) add(a[--cl]);while(cr > r) del(a[cr--]);while(cl < l) del(a[cl++]);width = r - l + 1;ans[q[i].id] = max(2 * max_cnt - width, 1);}for(int i = 0; i < m; i++) printf("%d\n", ans[i]);return 0; }

總結(jié)

以上是生活随笔為你收集整理的【莫队】区间众数（Codeforces Round #716 (Div. 2) D）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。