题目大意：
每次询问一个区间，将这个区间尽可能少的划分为几个子区间是的出现次数最多的那个数字不超过limit
limit = len/2（上取整，len为区间长度）
推导：
假设（为例）区间长度是8，那么limit = 4
那么出现次数大于4的数字如果有的话，有且只有一种
假设这种数字出现了x次
那么剩余的好的子序列的个数为len-x
我们可以把一部分x加入到len-x这部分子序列中来
可以加入的数量为len-x+1（保证最多的不超过limit）
那么第一部分的x就剩下x - （len-x+1）-->2*x-len -1
这部分的数字全是相同的，这不分数字需要划分成 2*x -len -1 个子序列，再加上第二部分（原本就是好的那部分）一个序列
综上，对于一个区间[L,R]需要划分成的子序列个数为2*x - len
Solution1: - 莫队-O（n*sqrt(n)）：
莫队维护区间众数的个数
add操作比较简单，就是一边加一边取max
del操作中会使原来是众数的数字不是众数
因为我们只维护从出现次数
那么在一次del操作之后，众数的出现次数，要么不变，要么减一
再开一个数组维护次数的出现次数就ok了
CODE：
// Problem: D. Cut and Stick // Contest: Codeforces - Codeforces Round #716 (Div. 2) // URL: https://codeforces.com/contest/1514/problem/D // Memory Limit: 512 MB // Time Limit: 3000 ms // // Powered by CP Editor (https://cpeditor.org) #include <algorithm> #include <cctype> #include <cmath> #include <cstdio> #include <cstdlib> #include <cstring> #include <ctime> #include <iostream> #include <map> #include <queue> #include <set> #include <sstream> #include <string> #include <vector> using namespace std; typedef long long ll; typedef pair<int, int> PII; typedef unsigned long long ull; const int inf = 0x3f3f3f3f; const int maxn = 6e5 + 7; const ll mod = 1e9 + 7; #define mst(x, a) memset(x, a, sizeof(x)) #define rep(i, a, b) for (int i = (a); i <= (b); ++i) #define dep(i, a, b) for (int i = (a); i >= (b); --i) inline ll read() { ll x = 0; bool f = 0; char ch = getchar(); while (ch < '0' || '9' < ch) f |= ch == '-', ch = getchar(); while ('0' <= ch && ch <= '9') x = x * 10 + ch - '0', ch = getchar(); return f ? -x : x; } void out(ll x) { int stackk[20]; if (x < 0) { putchar('-'); x = -x; } if (!x) { putchar('0'); return; } int top = 0; while (x) stackk[++top] = x % 10, x /= 10; while (top) putchar(stackk[top--] + '0'); } ll qpow(ll a, ll b) { ll ans = 1; while (b) { if (b & 1) ans = ans * a % mod; a = a * a % mod; b >>= 1; } return ans; } int n ,a[maxn]; struct node{ int id,l,r,b; }q[maxn]; int m ; bool cmp(node x,node y) { if(x.b==y.b) return x.l<y.l; return x.r<y.r; } bool cmp1(node x,node y) { return x.b^y.b?x.b<y.b:x.b&1?x.r<y.r:x.r>y.r; } int ans[maxn],now,kind[maxn]; int sum[maxn]; void add(int x) { sum[kind[a[x]]]--; kind[a[x]]++; sum[kind[a[x]]]++; now = max(now,kind[a[x]]); } void del(int x) { sum[kind[a[x]]]--; if(sum[kind[a[x]]]==0&&kind[a[x]]==now) now--; kind[a[x]]--; sum[kind[a[x]]]++; } int main() { n=read(),m=read(); rep(i,1,n) a[i] = read(); int block = 450; for(int i=1 ;i<=m ;i++) { q[i].l=read(),q[i].r=read(); q[i].id = i; q[i].b = q[i].l/block; } sort(q+1,q+1+m,cmp1); int r=0,l=1; for(int i=1 ;i<=m ;i++) { int ql = q[i].l; int qr = q[i].r; int id = q[i].id; while(l>ql) add(--l); while(r<qr) add(++r); while(l<ql) del(l++); while(r>qr) del(r--); ans[id] = now*2 - (qr - ql + 1); } rep(i,1,m) printf("%d\n",max(1,ans[i])); return 0; } /* */
Solution1: - 主席树上二分 - O(nlogn)：
我们已经证明过，超过limit限制的数字，如果有的话，只会有一种
那么用主席树维护一个区间内每种数的出现次数的和
如果左边大于limit查左边
如果右边大于limit查右边
CODE：
// Problem: D. Cut and Stick // Contest: Codeforces - Codeforces Round #716 (Div. 2) // URL: https://codeforces.com/contest/1514/problem/D // Memory Limit: 512 MB // Time Limit: 3000 ms // // Powered by CP Editor (https://cpeditor.org) #include <algorithm> #include <cctype> #include <cmath> #include <cstdio> #include <cstdlib> #include <cstring> #include <ctime> #include <iostream> #include <map> #include <queue> #include <set> #include <sstream> #include <string> #include <vector> using namespace std; typedef long long ll; typedef pair<int, int> PII; typedef unsigned long long ull; const int inf = 0x3f3f3f3f; const int maxn = 3e5 + 7; const ll mod = 1e9 + 7; #define mst(x, a) memset(x, a, sizeof(x)) #define rep(i, a, b) for (int i = (a); i <= (b); ++i) #define dep(i, a, b) for (int i = (a); i >= (b); --i) inline ll read() { ll x = 0; bool f = 0; char ch = getchar(); while (ch < '0' || '9' < ch) f |= ch == '-', ch = getchar(); while ('0' <= ch && ch <= '9') x = x * 10 + ch - '0', ch = getchar(); return f ? -x : x; } void out(ll x) { int stackk[20]; if (x < 0) { putchar('-'); x = -x; } if (!x) { putchar('0'); return; } int top = 0; while (x) stackk[++top] = x % 10, x /= 10; while (top) putchar(stackk[top--] + '0'); } ll qpow(ll a, ll b) { ll ans = 1; while (b) { if (b & 1) ans = ans * a % mod; a = a * a % mod; b >>= 1; } return ans; } int n ,val[maxn] , m,rt[maxn]; struct node{ int ls,rs,sum; }a[maxn*32]; int indexx; void insert(int pre,int &now,int l,int r,int num) { now = ++indexx; a[now] = a[pre],a[now].sum++; if(l==r) return ; int mid = (l+r)>>1; if(num<=mid) insert(a[pre].ls,a[now].ls,l,mid,num); else insert(a[pre].rs,a[now].rs,mid+1,r,num); } int query(int v,int u,int l,int r,int limit) { int sum = a[u].sum - a[v].sum; if(sum<=limit) return 0; if(l==r) return sum; int sum1 = a[a[u].ls].sum - a[a[v].ls].sum; int sum2 = a[a[u].rs].sum - a[a[v].rs].sum; int mid = (l+r)>>1; if(sum1>limit) return query(a[v].ls,a[u].ls,l,mid,limit); if(sum2>limit) return query(a[v].rs,a[u].rs,mid+1,r,limit); return 0; } int main() { n=read(),m=read(); rep(i,1,n) val[i] = read(),insert(rt[i-1],rt[i],1,300000,val[i]); while(m--) { int ql = read(); int qr = read(); int ans = query(rt[ql-1],rt[qr],1,300000,(qr-ql+1+1)/2); ans = max(ans*2 -(qr-ql+1) ,1); out(ans); puts(""); } return 0; } /* */