hdu4638Group

http://acm.hdu.edu.cn/showproblem.php?pid=4638

求某一区间所包含的连续的段 对于乱序的数 到了i这个数所包含的段数 首先把这个数看作单独的段 再看一下前面是否出现了它的朋友 若出现了就说明前面已经加过这样单独的段了 就把前面的更新掉-1 这样始终保证一个段的最后一个值记录着这是第几个段 从左到右扫描一遍 离线处理后 这样用树状数组或者线段树进行区间求和就可以了

 #include <iostream>

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 #include<stdlib.h>

 #define N 100010

 using namespace std;

 #define lowbit(x) (x&(-x))

 int p[N],a[N],re[N],ans[N],n;

 struct node

 {

     int l,r,id;

 }q[N];

 bool cmp(node a,node b)

 {

     return a.r<b.r;

 }

 void add(int x,int da)

 {

     while(x<=n)

     {

         re[x]+=da;

         x+=lowbit(x);

     }

 }

 int getsum(int x)

 {

     int s=;

     while(x)

     {

         s+=re[x];

         x-=lowbit(x);

     }

     return s;

 }

 int main()

 {

     int i,j,m,t;

     cin>>t;

     while(t--)

     {

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

         memset(re,,sizeof(re));

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

         {

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

             p[a[i]] = i;

         }

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

         {

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

             q[i].id = i;

         }

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

         j = ;

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

         {

             add(i,);

             if(a[i]<n&&p[a[i]+]<i)

             add(p[a[i]+],-);

             if(a[i]>&&p[a[i]-]<i)

             add(p[a[i]-],-);

             while(j<=m&&q[j].r==i)

             {

                 int x = getsum(q[j].r);

                 int y = getsum(q[j].l-);

                 ans[q[j].id] =x - y;

                 j++;

             }

         }

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

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

     }

     return ;

 }