link：https://codeforces.com/contest/1514/problem/D
很久以前小号打的场了，当时D题写的莫队，现在重新来看看。
题意：给一个序列 \([a_1,\dots,a_n]\)，有q次询问，每次问：把\([a_l,\dots,a_r]\) 划分最少几个不相交子序列，才能使得每个子序列是beautiful的。称一个序列 \(a_1,\dots,a_x\) 是beautiful的，当且仅当其不存在某个元素的出现次数超过\(\lceil x/2\rceil\)
\(1\leq n,q\leq 3\times 10^5\).
如果某个子区间不存在绝对众数，答案是1，否则假设绝对众数 \(x\) 出现了 \(cnt_x\) 次，则一定要把一些 \(x\) 单独拿出来作为一个序列，假设要拿出来 \(y\) 个，则需要有 \(cnt_x-y\leq (len-cnt_x)+1\)，得\(y\geq 2cnt_x -len -1\)，此时答案是 \(1+\max(0,2 cnt_x-len-1)\).
所有问题都指向，1、判断区间是否存在绝对众数。2、确定绝对众数的出现次数。后者容易回答，因为绝对众数要么唯一，要么两个出现次数一样，找到某个绝对众数 \(v\) 后，容易通过前缀和 \(O(\log n)\) 地找到。
而如何寻找绝对众数呢？
- 莫队典中典问题，维护每个值 \(v\) 的出现次数、以及出现次数为 \(c\) 的值有几个，每次改动端点对出现次数的影响至多+1/-1，可以在 \(O(1)\) 的时间内完成更新，这个复杂度 \(O(n\sqrt n)\) 足以通过此题。这个做法不依赖于 “绝对” 众数，只要是众数就可以了。
- 随机化： 随机 \([l,r]\) 内的一个数字，如果存在绝对众数，则找到的概率不小于 \(1/2\)，随机 \(T\) 次，如果存在，则找到的概率至少是 \(p_T=1-(\frac{1}{2})^T\) ，对于 \(q\) 次询问，完全回答正确的概率大约是 \((1-(1/2)^T)^q\approx 1-q\times (1/2)^T\) ，取一个\(T=40\) 左右，就能让正确率达到\(1-10^{-7}\) 左右。
- 线段树： 还是依赖于其绝对众数的性质，\([l,r]\) 内如果有绝对众数，第 \(\lceil\frac{r-l+1}{2}\rceil =1+\lfloor\frac{r-l}{2}\rfloor\) 大的数一定就是绝对众数。静态区间第 \(k\) 大问题，直接用可持久化线段树完成。
| 复杂度 | 适用 | 修改 | 实现 | |
|---|---|---|---|---|
| 莫队 | \(O(n\sqrt n)\) | 众数 | X | 容易 |
| 随机化 | \(O(n\log^2 n)\) | 绝对众数 | X | 最容易 |
| 线段树 | \(O(n\log n)\) | 绝对众数 | √ | 容易 |
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define endl '\n'
#define fastio ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define dbg(x) cout<<#x"="<<x<<' '
using namespace std;
const int N=3e5+5;
int n,q,a[N],rt[N];
vector<vector<int>> pos;
struct Node{int v,ls,rs;};
template<int LOG=20>
class SegT{
Node tr[N*LOG];
int cnt_node;
public:
void modify(int &x,int y,int l,int r,int p,int v){
tr[x=++cnt_node]=tr[y];
if(l==r){
tr[x].v+=v;
return;
}
int mid=l+(r-l>>1);
if(mid>=p)modify(tr[x].ls,tr[y].ls,l,mid,p,v);
else modify(tr[x].rs,tr[y].rs,mid+1,r,p,v);
tr[x].v=tr[tr[x].ls].v+tr[tr[x].rs].v;
}
int query(int x,int y,int l,int r,int k){
if(l==r)return l;
int mid=l+(r-l>>1);
int s=tr[tr[y].ls].v-tr[tr[x].ls].v;
if(s>=k)return query(tr[x].ls,tr[y].ls,l,mid,k);
return query(tr[x].rs,tr[y].rs,mid+1,r,k-s);
}
};
SegT tr;
int main(){
fastio;
cin>>n>>q;
pos=vector<vector<int>>(n+1);
rep(i,1,n){
cin>>a[i];
pos[a[i]].push_back(i);
tr.modify(rt[i],rt[i-1],1,n,a[i],1);
}
while(q--){
int l,r,count,v;
cin>>l>>r;
v=tr.query(rt[l-1],rt[r],1,n,1+(r-l)/2);
auto L=lower_bound(pos[v].begin(),pos[v].end(),l);
auto R=prev(upper_bound(pos[v].begin(),pos[v].end(),r));
if(L==pos[v].end())count=0;
else count=(R-L)+1;
if(2*count>=r-l+1)cout<<1+max(0,2*count-(r-l+1)-1)<<endl;
else cout<<1<<endl;
}
return 0;
}