锐客网

  1. 首页 > it技术 > >

bzoj|bzoj4241 历史研究 回滚莫队

bzoj莫队

题目大意：
有一个长度为n的序列。
有m个询问，每次询问l~r范围内每个数值乘以该数值出现次数的最大值。
题目分析：
据说这题可以在线做？
【bzoj|bzoj4241 历史研究 回滚莫队】这题普通的莫队GG，因为不支持快速删除操作，但是支持快速加入一个值的操作，所以上回滚莫队就好了。
回滚莫队可以把删除操作去掉，并且时间复杂度仍然保持在在O（nsqrtn）。
分块和排序都按照正常莫队做法来，然后在统计答案的时候，如果一个询问的左端点和右端点在同一个块内，那就暴力统计。
然后对于左端点在同一块内的询问我们一起统计，首先让左端点在这一块的最右端，然后让右端点正常向右扩张。当右端点满足条件的时候，记录一下这个时候的状态，再把左端点调整到询问的左端点，这个时候统计一下答案，然后再回滚到没有调整左端点的时候的那个状态。然后再做下一个询问就可以了。
这样仍然保证了时间复杂度是O（nsqrtn）
代码如下：

#include #include #include #include #define N 120000 using namespace std; typedef long long LL; inline LL Max(LL x,LL y) { return x>y?x:y; } int n,m,block_size,pos; int a[N],d[N],belong[N],top; LL sum[N],tmp[N],last_ans,cur_ans,ans[N]; struct Query{ int l,r,id; bool operator < (const Query &c) const { return belong[l]q[i].l) Add(a[--l]); ans[q[i].id]=cur_ans; while(l

    推荐阅读


    上一篇：bzoj|bzoj2906 颜色 分块

    下一篇：bzoj|bzoj1137 [POI2009]Wsp 岛屿 半平面交