LG SP20644 ZQUERY - Zero Query

zcmimi at 
查看原题'" class='mdui-btn mdui-btn-raised mdui-ripple'>点击加载点击跳转这题可以算是回滚莫队板子题设$S$为前缀和假设区间$[l,r]$区间和为$0$,那么$Sr-S{1-1}=0$如果使用莫队算法的话,容易想到:用桶记录某个前缀和出现的最大/最小位置,加点操作就很容易维护答案但这样的话删点操作就有点难实现了可以使用回滚莫队回滚莫队是一种只添加不删除的莫队,实现如下:首先对原序列进行分块,并对询问按照如下的方式排序:以左端点所在的块升序为第一关键字,以右端点升序为第二关键字枚举当前要处理的块,处理所有左端点在该块内的询问,设当前块右端为$R$,左……