SPOJ ZQUERY – Zero Query(分块)

题目链接

寒假集训只剩最后半个月不到了,乎的想起自己似乎还不会莫队,惊了,听队友讲了一下原理后感觉不难可以直接做下专题,写完前两题,很舒服,暴力膜哇。
然而碰到这题——卒

题意一样很简单,就是问你有一几个区间满足区间和为0。
这题的主要思路和我的上一篇博客可以说有着相同的解题思路,只不过我们考虑到他的数据比较小,因而可以采用分块的方法去解决。

我们在处理出每个的前缀和的所有可能的位置之后,我们可以二分的去找给定l,r之内符合要求的L和R,接着和要输出的len比较一下长度,一直更新到L=l&&R=r,这样便在nmlog(n)的时间内在线处理出可能的最大值。

接下来讲讲我为什么re了3发(┙>∧<)┙へ┻┻

re了之后我一直找不出错在哪里,然后随便的给所有的数组大小都加了个0之后就过了,当时真的是惊了,re?不存在的,加个0就解决了,如果还re,那就再加一个。

事实上,再接着做了一些测试之后,我终于发现了,是最初预处理pos的时候,我的pos开了1e5+5,然而我自己处理到了2*5e5>1e5+5

小错不断也是个很麻烦的问题啊。

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<cmath>
#include<vector>
#include<set>
#include<queue>
#include<limits.h>
#include<string.h>
#include<map>
using namespace std;
typedef long long ll;

#define inf int(0x3f3f3f3f)
#define mod int(1e9+7)
#define eps double(1e-6)
#define pi acos(-1.0)
#define lson  root << 1
#define rson  root << 1 | 1

int n,m;

int a[100005];

vector<int> pos[100005];

int vis[100005];

int ans[5000][5000];

int unit;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    for(int i=0;i<=50001*2;i++)
        pos[i].clear();
    cin>>n>>m;
    int unit=sqrt(n);
    //memset(a,0,sizeof(a));
    a[0]=50004;
    pos[50004].push_back(0);
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        a[i]+=a[i-1];
        pos[a[i]].push_back(i);
    }
    int s=(n+unit)/unit;
    //cout<<unit<<endl;
    for(int i=0;i<=n;i+=unit)
    {
        memset(vis,-1,sizeof(vis));
        int len=0;
        for(int j=i;j<=n;j++)
        {
            if(j%unit==0)
                ans[i/unit][j/unit]=len;
            if(vis[a[j]]==-1)
                vis[a[j]]=j;
            else
                len=max(len,j-vis[a[j]]);
        }
        ans[i/unit][s]=len;
    }
    //cout<<ans[1/unit][4/unit]<<endl;
    for(int i=1;i<=m;i++)
    {
        int l,r;
        cin>>l>>r;
        l--;
        int L=(l+unit)/unit*unit;
        int R=r/unit*unit;
        int sum=ans[L/unit][R/unit];
        //cout<<sum<<endl;
        for(int i=l;i<L;i++)
        {
            int p=lower_bound(pos[a[i]].begin(),pos[a[i]].end(),r)-pos[a[i]].begin()-1;
            if(p<0)
                continue;
            sum=max(sum,pos[a[i]][p]-i);
            //cout<<sum<<endl;
        }
        for(int i=r;i>=R;i--)
        {
            int p=lower_bound(pos[a[i]].begin(),pos[a[i]].end(),l)-pos[a[i]].begin();
            if(p==pos[a[i]].size())
                continue;
            sum=max(sum,i-pos[a[i]][p]);
            //cout<<sum<<endl;
        }
        cout<<sum<<endl;
    }
}