D. Cut and Stick

給定一個長度為$n$的數組，里面元素為$a_1,a_2,a_3,\dots ,a_{n?1},a_n,(1\le a_i\le n)$，有$m$次詢問，每次給定$l,r$，

問如果把$[l,r]$劃分若干段子序列，假設其中一段長度為$len$，里面出現最多次的元素次數$\le ?\frac{len}{2}?$，對所有段都滿足，

不考慮劃分成一段的情況，那么我們就是要盡可能地把最大地給劃開，最優的策略是兩個最大的跟一個其他的一起劃分，

假設區間長度為$r?l+1=len$，最大的元素個數為$x$，則還有$len?x$個其他元素，

由于其他元素都是小于$?\frac{len}{2}?$的，所以，我們讓兩個最大元素與其他元素配對時，可以保證剩下的元素中最大個數不會超過$x$的值，

假設我們要配對$k$個，則當滿足，$x?2k+len?x?k+1\ge 2x?4k$時只需要一個序列即可，解得$k=2x?len?1$，

所以最后答案為$max(2x?len,1)$，所以我們只要統計區間數量最多的值即可，可用莫隊解決。

#include <bits/stdc++.h>using namespace std;const int N = 1e6 + 10;int a[N], ans[N], sum[N], num[N], n, m, block, maxn;struct Res {int l, r, id; }query[N];bool cmp(Res x, Res y) {return ((x.l / block) != (y.l / block)) ? x.l < y.l : ((x.l / block) & 1) ? x.r < y.r : x.r > y.r; }void add(int x) {num[a[x]]++;sum[num[a[x]]]++;while (sum[maxn + 1]) {maxn++;} }void del(int x) {sum[num[a[x]]]--;num[a[x]]--;while (maxn && !sum[maxn]) {maxn--;} }int main() {// freopen("in.txt", "r", stdin);// freopen("out.txt", "w", stdout);scanf("%d %d", &n, &m);for (int i = 1; i <= n; i++) {scanf("%d", &a[i]);}block = sqrt(n);for (int i = 1, l, r; i <= m; i++) {scanf("%d %d", &l, &r);query[i] = {l, r, i};}sort(query + 1, query + 1 + m, cmp);int l = 1, r = 0;for (int i = 1; i <= m; i++) {while (r < query[i].r) {add(++r);}while (l < query[i].l) {del(l++);}while (r > query[i].r) {del(r--);}while (l > query[i].l) {add(--l);}ans[query[i].id] = max(1, 2 * maxn - (query[i].r - query[i].l + 1));}for (int i = 1; i <= m; i++) {printf("%d\n", ans[i]);}return 0; }

總結

以上是生活随笔為你收集整理的D. Cut and Stick（Codeforces Round #716 (Div. 2)）的全部內容，希望文章能夠幫你解決所遇到的問題。

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