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 ;

 }

巴特西

hdu4638Group

最新文章

热门文章