莫队 get！

A4paper · 2018-08-23 09:07:06 · 个人记录

实现过程：

先暴力跑出第一个询问区间的和，记录左右端点

再分别修改左右端点扩展到下一个区间

struct node{
    int L,R;
}q[MAXN];

int main(void)  //求区间和
{
    for(int i=q[1].L;i<=q[1].R;i++)
        ans += num[i];
    int l = q[1].L, r = q[1].R;
    for(int i=2;i<=m;i++)
    {
        if(l < q[i].L)
            for(int j=l;j<q[i].L;j++)   ans -= z[j];
        else
            for(int j=q[i].L;j<l;j++)   ans += z[j]; 
        if(r < q[i].R)
            for(int j=r+1;j<=q[i].R;j++) ans += z[j];
        else
            for(int j=q[i].R+1;j<r;j++)  ans -= z[j];
    }
    return 0;
}

变式：

传送门

疯狂TLE 疯狂TLE 疯狂TLE ！！！

一晚上狂 T 20 多次。。。

进行了无数次优化

仍然只得了 80 分。。。

所以，就着这道题，总结一下莫队的优化：

1.按左右端点排序，略有效果。

2.分块排序，效果明显

3.瞎优化，效果显著（比如这道题就是按分块后奇偶性排序 AC ）

4.其实不需要先暴力跑出第一个区间的值（见代码）

5.想不出来了，留着以后补充

最后，上代码：

struct node{//分块排序
    int L,R,id;
    bool operator < (const node &b) const{
        return (L/500)==(b.L/500) ? (R<b.R) : ((L/500)<(b.L/500));
    }
}ask[500010];

void add(int C){
    if(++vis[C] == 1)
        ans++;
}
void del(int C){
    if(--vis[C] == 0)
        ans--;
}

int main()
{
    scanf("%d",&N);
    for(int i=1;i<=N;i++)   scanf("%d",&a[i]);
    scanf("%d",&M);
    for(int i=1;i<=M;i++)
    {
        scanf("%d%d",&ask[i].L,&ask[i].R);
        ask[i].id = i;
    }
    sort(ask+1,ask+1+M);
    for(int i=1;i<=M;i++)
    {
        while(ask[i].R > R) add(a[++R]);
        while(ask[i].R < R) del(a[R--]);
        while(ask[i].L < L) add(a[--L]);
        while(ask[i].L > L) del(a[L++]);
        Ans[ask[i].id] = ans;
    }
    for(int i=1;i<=M;i++)
        printf("%d\n",Ans[i]);
    return 0;
}