题解：P12029 [USACO25OPEN] Election Queries G
Twig_K
·
·
题解
题意
cnblogs
有 n 个整数，值域 [1,n]。请你将这 n 个数划分为两个非空集合 S,T，并选择 x,y。
要求 x 为 S 的众数之一，y 为 T 的众数之一。最大化 \lvert x-y \rvert 的值。
## 题解
对于选出的 $x,y$，考虑如何贪心地划分集合：所有数 $x$ 放入 $S$，所有数 $y$ 放入 $T$，其他数摊到两个集合。
所以，$(x,y)$ 能被同时取出，当且仅当：
$$\forall i \in [1,n],cnt_i \leq cnt_x+cnt_y$$
即:
$$\max_{i=1}^n cnt_i \leq cnt_x+cnt_y$$
既然要最大化下标差，那么我们可以对每种不同的 $cnt$ 记录 $cnt_i=v$ 的最大、最小下标 $mxi_v,mni_v$。
双指针，枚举 $cnt_y$，找到最大的 $cnt_x$ 使 $cnt_x \geq mxcnt - cnt_y$，用 $mxi_{cnt},mni_{cnt}$ 之差更新答案。
双指针移动 $n$ 次，这样复杂度是 $O(n)$ 的，多组询问总复杂度 $O(nQ)$。
怎么优化呢？**因为始终有 $\sum cnt_i=n$，所以本质不同的 $cnt_i$ 最多有 $O(\sqrt n)$ 种**（考虑 $1+2+ \cdots + t \leq n$ 那么 $t$ 是 $O(\sqrt n)$ 的）。
所以只需要考虑那些不同的非零 $cnt_i$ 即可，用 `set` 维护存在的 $cnt$ 值，再对每种 $cnt$ 开一个 `set` 辅助求解最大、最小下标。
时间复杂度 $O(n \log n + n \sqrt n)$。
## 代码
[完整代码](https://www.cnblogs.com/wanggk/p/-/P12029)
```cpp
int n,Q;
set<int> st[maxn],S;
int a[maxn],c[maxn],mxi[maxn],mni[maxn];
void addc(int i,int cl){ //i 的得票变成 cl 了
if(!cl) return; st[cl].insert(i);
mxi[cl]=max(mxi[cl],i);
mni[cl]=min(mni[cl],i);
if(st[cl].size()==1) S.insert(cl);
}
void delc(int i,int cl){ //i 的得票不再是 cl 了
if(!cl) return; st[cl].erase(i);
if(st[cl].empty()) S.erase(cl),mxi[cl]=0,mni[cl]=n+1;
else if(!st[cl].empty()) mxi[cl]=*--st[cl].end(),mni[cl]=*st[cl].begin();
}
signed main()
{
rd(n),rd(Q);
For(i,1,n) rd(a[i]),c[a[i]]++,mxi[i]=0,mni[i]=n+1;
For(i,1,n) addc(i,c[i]);
while(Q--)
{
int i,x;rd(i),rd(x);
delc(a[i],c[a[i]]--),addc(a[i],c[a[i]]); a[i]=x;
delc(a[i],c[a[i]]++),addc(a[i],c[a[i]]);
int mx=*--S.end(),mxp=0,mnp=n+1,res=0;
if(*S.begin()+*S.begin()>=mx) res=max(res,mxi[*S.begin()]-mni[*S.begin()]);
for(auto itl=S.begin(),itr=--S.end();itl!=S.end();itl++){//双指针
while(itr!=S.begin() && (*itr)+(*itl)>=mx)
mxp=max(mxp,mxi[*itr]),mnp=min(mnp,mni[*itr]),itr--;
res=max(res,max(mxp-mni[*itl],mxi[*itl]-mnp));
}
write(res),End;
}
return 0;
}
```