洛谷-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​中的每个数是否在右侧出现过。如果有则找到答案。否则向右递归。发现这样询问次数上界为2NNN2N4⋯4N2NN\frac{N}{2}\frac{N}{4}\dots4N2NN2N​4N​⋯4N需要优化。注意到如果最终向左递归则询问∣Il∣|I_l|∣Il​∣次。否则询问2∣Il∣2|I_l|2∣Il​∣次。因此我们希望多一些向左递归。考虑平衡询问数和层数让左边分到k⋅∣I∣k\cdot |I|k⋅∣I∣个下标。实验法得知k0.62k0.62k0.62时刚好通过本题。Code#includebits/stdc.h#definerep(i,a,b)for(inti(a);ib;i)#definerept(i,a,b)for(inti(a);ib;i)#defineebemplace_backusingnamespacestd;boolchiedi(vectorintS,intx);intcalc(vectorintid,vectorintval){intmidmax(1,int(id.size()*0.62));vectorintlId,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){vectorintid,val;rept(i,0,n)id.eb(i);rep(i,0,n)val.eb(i);returncalc(id,val);}