题解 P5906 【【模板】回滚莫队&不删除莫队】

呜呼呼这个回滚莫队大概是一种正难则反的思路，如果遇到比较毒瘤的删除的话，要不就减少删除的次数，要不就把删除改成插入 恰好这道题都用了，虽然套一个数据结构的莫队比较好做（可惜有个$log$），可是这道题已经写了【模板】回滚莫队&不删除莫队，所以我们至少得用莫队 首先一看就知道用$st,ed$两个桶，每次都记录这个点在$[l,r]$(表示当前问题的左端点和右端点的位置)。 但是如果套普通的套一个莫队，你会发现这东西可以做到$O(1)$修改，但是似做不到O(1)撤销（除非开大空间存下来） 原来的莫队是左端点在每$\sqrt{m}$区间内的问题排序,所以这些询问的左端点都在一个块内部，右端点则是按$r$升序排序（不管奇偶性优化），可见对右端点可以做到没有删除操作，但是左端点则不然，况且左端点只有$\sqrt{m}$个操作，我们对左端点也可以做到没有插入操作，那就是每次从这个块的最右边往左移，每次向左之后要还原就行了。 可以看见每个块内的询问最多向右$\sqrt{m}$次 每个询问最多向左走$\sqrt{m}$次 复杂度还是$O(n\sqrt{m})$ 除此之外本题还有一些细节要注意，写在代码注释上了 ```cpp #include<touwenjian.h> using namespace std; const int maxn=502000;//用不到这么多的空间 int n,m; int st[maxn],ed[maxn],looker[maxn],lok[maxn],a[maxn],b[maxn]; int ans; int bj[maxn]; int len,cnt; int aans[maxn]; struct que{ int l,r,bh; }q[maxn]; int cmp(que aa,que bb) { if((aa.l-1)/len==(bb.l-1)/len) return aa.r<bb.r; return aa.l<bb.l; } int tst[maxn],ted[maxn],tlooker[maxn],tcnt; int bl(int l,int r) //这东西得单独开一套变量来 { int i,ans=0; for(i=l;i<=r;i++) { if(!tst[a[i]]) tst[a[i]]=i; ted[a[i]]=max(ted[a[i]],i); ans=max(ted[a[i]]-tst[a[i]],ans); tlooker[++tcnt]=a[i]; } for(i=1;i<=tcnt;i++) tst[tlooker[i]]=ted[tlooker[i]]=0,tlooker[i]=0; tcnt=0; return ans; } inline void addr(int x) //右端点只有插入，因此可以保留 { if(!st[a[x]]) st[a[x]]=x; ed[a[x]]=max(ed[a[x]],x); ans=max(ed[a[x]]-st[a[x]],ans); looker[++cnt]=a[x]; } inline void addl(int x) //左端点每次都要清空，除了判断答案在左边这个块的情况暂时用一用ed数组（之后也要清空），其他都不能动。 { if(!ed[a[x]]) ed[a[x]]=x; else ans=max(ans,ed[a[x]]-x); } int main() { ios::sync_with_stdio(false); register int i,j; cin>>n; len=sqrt(n); for(i=1;i<=n;i++) cin>>a[i],b[i]=a[i]; sort(b+1,b+n+1); int tot=unique(b+1,b+n+1)-b-1; for(i=1;i<=n;i++) a[i]=lower_bound(b+1,b+tot+1,a[i])-b; cin>>m; for(i=1;i<=m;i++) cin>>q[i].l>>q[i].r,q[i].bh=i; sort(q+1,q+m+1,cmp); i=1; for(j=1;j<=(n-1)/len+1;j++) { ans=0; int baspla=min(len*j,n); int l=baspla+1,r=baspla; for(;(q[i].l-1)/len+1==j&&i<=m;i++) //一定要加上i<=m的判断 { if((q[i].l-1)/len==(q[i].r-1)/len) aans[q[i].bh]=bl(q[i].l,q[i].r); else { while(q[i].r>r) addr(++r); //莫队基本操作 int rigans=ans; while(q[i].l<l) addl(--l); while(l<=baspla) { if(ed[a[l]]<=baspla) ed[a[l]]=0; l++;} aans[q[i].bh]=ans; ans=rigans; } } for(int k=1;k<=cnt;k++) st[looker[k]]=ed[looker[k]]=0,looker[k]=0; //记得清空 cnt=0; } for(i=1;i<=m;i++) cout<<aans[i]<<endl; return 0; } ```