线段树

#include <iostream>

#include <cstring>

#include <cstdio>

#include <algorithm>

using namespace std;

#define lson l,m,rt<<1

#define rson m+1,r,rt<<1|1

const int MAX=100010;

struct point {   int l,r,id; } q[MAX];

int n,m;

int sum[MAX<<2];

int val[MAX];

int mark[MAX];

int ans[MAX];

void putup(int rt)

{   sum[rt]=sum[rt<<1]+sum[rt<<1|1]; }

void build(int l,int r,int rt)

{  sum[rt]=0;    

  if (l==r)      

   return ;     

  int m=(l+r)>>1;  

  build(lson);   

  build(rson);

}

void update(int k,int v,int l,int r,int rt)

{     if (l==r)    

     {  

    m[rt]+=v;      

   return ;  

     }         

int m=(l+r)>>1;    

if (k<=m)       

  update(k,v,lson);    

else    update(k,v,rson);   

  putup(rt); }

int query(int L,int R,int l,int r,int rt)

{    

if (L<=l&&r<=R)        

return sum[rt];    

int m=(l+r)>>1;    

int ret=0;    

if (L<=m)  ret+=query(L,R,lson);    

if (R>m)   ret+=query(L,R,rson);    

return ret;

}

bool cmp(point a,point b)//按照区间右端点排序

{     return a.r<b.r; }

int main()

{     int T;    

   scanf("%d",&T);   

  while (T--)    

{  scanf("%d%d",&n,&m);      

   build(1,n,1);//建树       

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

   scanf("%d",&val[i]);//读入值        

   for (int i=1;i<=m;i++)//m次访问       

  {  

     anf("%d%d",&q[i].l,&q[i].r);//左右区间   

     q[i].id=i;//记录为第i次访问        

  }   

   sort(q+1,q+m+1,cmp);   

   memset(mark,0,sizeof(mark));//初始化

   int cur=1;     

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

     {           

        update(i,1,1,n,1);  

        if (mark[val[i]+1]!=0)//右边出现了     

        update(mark[val[i]+1],-1,1,n,1);         

        if (mark[val[i]-1]!=0)//左边出现了                

        update(mark[val[i]-1],-1,1,n,1);                 //每一次更新一个右区间，先加上1，如果左右同时出现了，最终就是减了1，只出现一个，就是没变，没出现，就是0            

        mark[val[i]]=i;//记录val[i]的位置        

     while (cur<=m&&q[cur].r<=i)//对最终结果确定值        

     {            

        ns[q[cur].id]=query(q[cur].l,q[cur].r,1,n,1);//第i次访问的结果，是其左右端点的访问的结果         

        cur++;            

     }        

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

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

}

return 0 ；

}