洛谷-P14538 [OII 2025] 市政委员会 / Giunta comunale 题解

Solution

考虑分治，并不断缩小答案的查找范围。维护当前下标集合III和它对应的数值集合V={ai∣i∈I}V=\{a_i|i\in I\}V={ai​∣i∈I}。

将当前范围分成左右两半，下标集合分别为IlI_lIl​和IrI_rIr​。先处理出所有在左边出现过的数VlV_lVl​。

此时如果∣Il∣>∣Vl∣|I_l|>|V_l|∣Il​∣>∣Vl​∣，说明答案在左侧，向左递归。否则判断VlV_lVl​中的每个数是否在右侧出现过。如果有则找到答案。否则向右递归。

发现这样询问次数上界为2N+N+N2+N4+⋯=4N2N+N+\frac{N}{2}+\frac{N}{4}+\dots=4N2N+N+2N​+4N​+⋯=4N，需要优化。

注意到如果最终向左递归，则询问∣Il∣|I_l|∣Il​∣次。否则询问2∣Il∣2|I_l|2∣Il​∣次。因此我们希望多一些向左递归。考虑平衡询问数和层数，让左边分到k⋅∣I∣k\cdot |I|k⋅∣I∣个下标。

实验法得知，k=0.62k=0.62k=0.62时刚好通过本题。

Code

#include<bits/stdc++.h>#definerep(i,a,b)for(inti(a);i<b;++i)#definerept(i,a,b)for(inti(a);i<=b;++i)#defineebemplace_backusingnamespacestd;boolchiedi(vector<int>S,intx);intcalc(vector<int>id,vector<int>val){intmid=max(1,int(id.size()*0.62));vector<int>lId,rId,lVal,rVal;rep(i,0,mid)lId.eb(id[i]);rep(i,mid,id.size())rId.eb(id[i]);for(intx:val){if(chiedi(lId,x))lVal.eb(x);elserVal.eb(x);}if(lId.size()>lVal.size())returncalc(lId,lVal);for(intx:lVal)if(chiedi(rId,x))returnx;returncalc(rId,rVal);}intdelibera(intn){vector<int>id,val;rept(i,0,n)id.eb(i);rep(i,0,n)val.eb(i);returncalc(id,val);}