题面

SPOJ上的题，数据都很坑

大意：长度为$n$的序列，序列中的值为$1$或$-1$

有$m$个询问，询问在$[L,R]$中区间和为$0$的区间的最大长度

这样会比较好理解吧，翻译的时候没翻好

思路：

莫队+multiset

对于这种区间乱搞操作的，一般选用莫队(Mo’s algorithm)比较方便

来做这道题的大佬们应该都有学过莫队吧，$Luogu$没有莫队模板确实是一件比较复杂的事情，原本这道题$\large \to$HH的项链还是能用莫队水过去，然后结果数据加强了……

莫队模板题$\to$小B的询问可以去做一下

求和为$0$的区间，显然是要预处理的，所以读入的时候就记录前缀和

那么题目转化为$\to$两个相同元素的最大间距

原先的样例为：

1 1 1 -1 -1 -1

转化为前缀和：

1 2 3 2 1 0

求$[1,3]$这个区间，由于前缀和的影响，不应该直接在$[1,3]$这个区间里找相同，而是应该把左端点左移一位，求$[0,3]$这个区间的相同

由于区间的相同元素可能有多个：

1 -1 1 -1 1 -1

这组数据转化后就是：

1 0 1 0 1 0

设元素$x$，在$[l,r]$中最早出现的位置为$Min[x]$，最晚出现的位置为$Max[x]$

在$[1,6]$中，元素$1$和$0$分别有$3$个，但是实际上第一个$1$（或$0$）和最后一个$1$（或$0$）才是有价值的（也就是$Max[1],min[1],Max[0],Min[0]$，价值为他们之间的距离，即$5-1=4$或$6-2=4$），那么中间的元素就可以省去吗？ 不行！由于莫队算法中$Add$和$Del$操作，要求我们记录这些值，才能在$O(1)$的时间里更新

$[l,r]$这个区间里，由每种元素都有可能构成最优值，因此还要用$multiset$记录每种元素的最优值，当然，如果一个区间中某个元素只出现了一次，那么该元素的价值应该是$Max[x]=Min[x],Max[x]-Min[x]=0$，也可以加入$multiset$中，但是在这里我怕时间无法承受，就特判掉了

那么如何记录这些中间值呢？我只想到了链表，其实双端队列（$deque$应该也可以，如果不怕炸的话）

再说一下前缀和，前缀和可能是负数哦~

那么就加一个$n+1$就够了（$n$为序列长度，当然保险点加个$n+7$）

Code：

#include<bits/stdc++.h>
#define N 50010
using namespace std;
struct node{
    int l,r,i;
}b[N];
int a[N],n,m,block,pos[N],l,r,num;
int Min[N<<1],Max[N<<1],Ans[N],L[N],R[N];//Ans记录答案，其他数组用于存链表，据说STL中与一个list
multiset<int>ans;
bool cmp(node a,node b){//莫队奇偶划分
    return (pos[a.l]==pos[b.l])?(pos[a.l]&1)?a.r>b.r:a.r<b.r:a.l<b.l;
}
void Add(int x){//添加
    num=a[x]+n+1;
    if(Max[num]<0)//这种情况链表中没有元素
    {
        Max[num]=Min[num]=x;
        return;
    }
    if(Max[num]!=Min[num])//要更新价值，原先的就要删掉，特判掉了价值为0的情况，为0不删
        ans.erase(ans.lower_bound(Max[num]-Min[num]));
    if(Min[num]>x)//加入头
    {
        L[Min[num]]=x;
        R[x]=Min[num];
        Min[num]=x;
    }
    else//加入尾
    {
        R[Max[num]]=x;
        L[x]=Max[num];
        Max[num]=x;
    }
    ans.insert(Max[num]-Min[num]);//更新最大值
}
void Del(int x){//删除
    num=a[x]+n+1;
    if(Min[num]==Max[num])
    {
        Max[num]=-1;Min[num]=(n<<1)+7;
        return;
    }
    ans.erase(ans.lower_bound(Max[num]-Min[num]));
    if(Min[num]==x)
        Min[num]=R[x];
    else
        Max[num]=L[x];
    if(Max[num]!=Min[num])
        ans.insert(Max[num]-Min[num]);
}
int main()
{
    int i,j;
    scanf("%d%d",&n,&m);block=pow(n,0.54);//玄学优化
    for(i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
        a[i]+=a[i-1];//前缀和
        pos[i]=i/block;
    }
    for(i=1;i<=m;i++)
        scanf("%d%d",&b[i].l,&b[i].r),b[i].i=i;
    sort(b+1,b+1+m,cmp);l=1;
    for(i=1;i<=(n<<1)+7;i++)
        Min[i]=(n<<1)+7,Max[i]=-1;//Max[i]赋为-1是为了包容0这个位置
    ans.insert(0);//预先输入0，防止RE（可我还是RE了）
    for(i=1;i<=m;i++)
    {
        while(r<b[i].r)    Add(++r);
        while(l>b[i].l-1) Add(--l);//如果RE了，就把Add往前挪吧，千万要注意顺序！
        while(r>b[i].r)    Del(r--);//否则Del(r--)后，r的值可能小于l，然后就爆炸
        while(l<b[i].l-1) Del(l++);
        Ans[b[i].i]=*(--ans.end());//最大的价值
    }
    for(i=1;i<=m;i++)
        printf("%d\n",Ans[i]);
    return 0;
}

devil.