problem_id=1551">题目链接

题目大意：

给出的询问，求出这个区间的里 差小于等于 2 的数字的对数。

思路分析：

莫队算法。

然后分析一下。

假设添加了一个数字。那么就要加它旁边相差为2 的数字的和。

反之降低一个。就要降低相差为2 的数字的和。再减去自己这个1.。

#include <cstdio>

#include <iostream>

#include <cstring>

#include <algorithm>

#include <cmath>

#define maxn 100005

using namespace std;

int app[maxn];

int save[maxn];

int pos[maxn];

struct foo

{

    int l,r,index;

    int ans;

    bool operator < (const foo &cmp)const

    {

        if(pos[l] == pos[cmp.l])

            return r<cmp.r;

        return pos[l]<pos[cmp.l];

    }

}Q[maxn];

bool cmp_id(const foo &a, const foo &b)

{

    return a.index < b.index;

}

void debug()

{

    for(int i=0;i<=7;i++)

        printf("%d ",app[i]);

    puts("");

}

void modify(int p,int &ans,int add)

{

    int tot=0;

    for(int i=max(save[p]-2,0);i<=save[p]+2;i++)

    {

        tot+=app[i];

    }

    if(add>0)ans+=tot;

    else ans-=tot-1;

    app[save[p]]+=add;

}

int main()

{

    int n,m;

    int cas=1;

    while(scanf("%d%d",&n,&m)!=EOF)

    {

        int SIZE=(int)sqrt(1.0*n);

        memset(app,0,sizeof app);

        for(int i=1;i<=n;i++)

        {

            scanf("%d",&save[i]);

            pos[i]=(i-1)/SIZE+1;

        }

        for(int i=0;i<m;i++)

        {

            scanf("%d%d",&Q[i].l,&Q[i].r);

            Q[i].index=i;

        }

        sort(Q,Q+m);

        int ans=0;

        for(int i=0,l=1,r=0;i<m;i++)

        {

            if(r<Q[i].r)

            {

                for(r=r+1;r<=Q[i].r;r++)

                    modify(r,ans,1);

                r--;

            }

            if(r>Q[i].r)

            {

                for(;r>Q[i].r;r--)

                    modify(r,ans,-1);

            }

            if(l<Q[i].l)

            {

                for(;l<Q[i].l;l++)

                    modify(l,ans,-1);

            }

            if(l>Q[i].l)

            {

                for(l=l-1;l>=Q[i].l;l--)

                    modify(l,ans,1);

                l++;

            }

            Q[i].ans=ans;

        }

        sort(Q,Q+m,cmp_id);

        printf("Case %d:\n",cas++);

        for(int i=0;i<m;i++)

            printf("%d\n",Q[i].ans);

    }

    return 0;

}