脚本宝典收集整理的这篇文章主要介绍了可持久化摸鱼（桶排优化），脚本宝典觉得挺不错的，现在分享给大家，也给大家做个参考。
原题 SDFZ-NOIP2021模拟11-T2 韭菜收割，改成 (text{zyd & lyn}) 摸鱼扔到洛谷 U188872。
PS: 可持久化摸鱼是今年我们 ICPC 济南站打星队的队名，所以就这么起名了。
前 50 分很送，(mathcal{O(knlog n)}) 我一直以为过不去 (nle 2000,kle 2000)，然而开 O2 跑得飞快。有一个 (a_ile 2) 的部分分，可以直接开桶统计 (2) 的个数。
考虑正解。暴力中，区间是怎样向右扩展的？进来一个 (a_i)，直接扔进堆里，然后取堆顶元素对吧？还是说加一个剪枝——与堆顶比较，如果更大则直接加入答案，不再进堆，否则扔进去？后者直接指向一个关键结论：随着区间向右扩展，其最大值单调不增！ 更大的不会进堆（直接加了），原来的最大值会被取出，更小的元素成为最大值……正确性显然。
特别地，最后只出不入的阶段，可以等价为加了一堆 (0)，仍然不增。
利用这个结论，我们不难创造一个算法：开桶记录 (1to p-1) 每个数值出现的次数，暴力跑到当前最大值位置 (cur)；继续枚举后面的 (a_i)，仍然是更大直接加，否则扔进桶里，取出最大值加入答案。注意，这时“取出最大值”不再是拿堆顶，而是 cnt[cur]--;。
分析时间复杂度：对于每次询问从 (1) 到 (n) 枚举，(cur) 同时从 (n) 减小到 (1)，显然 (mathcal{O(kn)})。
下面是 AC 代码：
int fnd(){ while(!cnt[cur]) cur--; return cur; }//查找当前最大值
int main(){
int n=inn(),k=inn(); rep(i,1,n) a[i]=inn();
while(k--){
int p=inn(); rep(i,1,p-1) cnt[a[i]]++;
cur=n,fnd(); lint ans=0;
rep(i,1,n)
if(i+p-1<=n)
if(a[i+p-1]>=fnd()) ans+=(i&1)*a[i+p-1];//插入元素更大，直接加
else cnt[a[i+p-1]]++,ans+=(i&1)*cur,cnt[cur]--;//取max加，新元素入桶
else ans+=(i&1)*fnd(),cnt[cur]--;//等效于加0，直接取max加
printf("%lldn",ans);
}
return 0;
}
以上是脚本宝典为你收集整理的可持久化摸鱼（桶排优化）全部内容，希望文章能够帮你解决可持久化摸鱼（桶排优化）所遇到的问题。
本图文内容来源于网友网络收集整理提供，作为学习参考使用，版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ：384754419，请注明来意。