学步园

分析问题并考虑已知的数据结构。

细节处理很重要。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
//用标记数组的话果然不对  比如样例3 1 2 5 4，走一遍之后，再从头开始进行遍历的话，3+1，3-1都有标记，后面的都加了1
//还有得注意到底是什么情况下用sum(a)-sum(b);什么情况下只用sum(a)就够了
//树状数组更新之后 其后所有的数都会更新 切记
int a[100005];
int visit[100005];
int c[100005];
int ret[100005];
int num[100005];
struct vv
{
    int l,r;
    int id;
}v[100005];
int max(int a,int b)
{
    if(a<b) return b;
    else return a;
}
int min(int a,int b)
{
    if(a<b) return a;
    else return b;
}
int cmp(struct vv x,struct vv y)
{
    return x.l<y.l;
}
int lowbit(int x)
{
    return x&-x;
}
void update(int a,int b)
{
    for(int i=a;i<=100005;i+=lowbit(i))
        c[i]+=b;
}
int sum(int a)
{
    int ret=0;
    for(int i=a;i>=1;i-=lowbit(i))
        ret+=c[i];
    return ret;
}
int main()
{
    int case_num;
    scanf("%d",&case_num);
    while(case_num--)
    {
        memset(c,0,sizeof(c));
        memset(num,0,sizeof(num));
        int n,m;
        scanf("%d%d",&n,&m);
        for(int i = 1;i <= n;i++)
        {
            scanf("%d",&a[i]);
            num[a[i]]=i;
        }
        num[0] = n+10;
        num[n+1] = n+10;
        for(int i = 1;i <= n;i++)
        {
            if(i < num[a[i]-1] && i < num[a[i]+1])     //d段数加1
                update(i,1);
            else if(i > num[a[i]-1] && i > num[a[i]+1])   //段数减1
                update(i,-1);
        }
        for(int i=0;i<m;i++)
        {
            scanf("%d%d",&v[i].l,&v[i].r);
            v[i].id=i;//利用这个Id进行编号是个好技巧...应该可以这么输出？
        }
        sort(v,v+m,cmp);
        int i = 1;
        int j = 0;
        while(j < m)       //m次询问
        {
            while(i <= n && i < v[j].l)   //从左到右删除
            {
                if(i > num[a[i]-1] && i > num[a[i]+1])   //删除a[i],则把原来加的一,减去
                    update(i,-1);
                else if(i < num[a[i]-1] && i < num[a[i]+1])
                {
                    int Min = min(num[a[i]-1],num[a[i]+1]);
                    int Max = max(num[a[i]-1],num[a[i]+1]);
                    update(i,-1);               //愿来加的一减去
                    update(Min,1);              //少了a[i],则相应段数增加
                    update(Max,1);              // . ...
                }
                else if(i < num[a[i]-1])
                {
                    update(i,-1);
                    update(num[a[i]-1],1);
                }
                else
                {
                    update(i,-1);
                    update(num[a[i]+1],1);
                }
                i++;
            }
                ret[v[j].id]= sum(v[j].r); //保存答案
                j++;
        }
        for(int i=0;i<m;i++)
            printf("%d\n",ret[i]);
    }
     return 0;
}