hdu4417(离线操作 + 树状数组)

题意：

给定一个长度为n的数组，有m次的查询，每次查询[a,b]区间里比H小的数有多少个？

由于n和m的取值范围为0到10的5次方，所以直接回答会超时，所以考虑先读入所有的查询操作，然后依次回答比H小的[a,b]区间里的数有多少个，

求和类似于求正序数的方法。

写法可以边插变查，也可以边查边插，边查边插简单些；

可是这道题从头wa到了尾，原因是add函数少打了等于号,扇自己一巴掌.

边插边查：

#include <iostream>

#include <cstdio>

#include <time.h>

#include <stdlib.h>

#include <cstring>

#include<algorithm>

#define maxn 110000

#define LL  int

using namespace std;

struct node

{

   LL value,id;

};

struct querynode

{

    LL L,R,H=-,cnt;

};

node a[maxn];

querynode  que[maxn];

LL c[maxn];

LL N,M;

LL ans[maxn];

void init()

{

   memset(a,,sizeof(a));

   memset(c,,sizeof(c));

   memset(ans,,sizeof(ans));

}

bool cmp1(node a,node b)

   {

       return a.value<b.value;

   }

bool cmp2(querynode a,querynode b)

{

        return a.H<b.H;

}

int inline lowbit(int x){

    return x & (-x);

}

void inline add(int x){

    while(x <= N){

       c[x]++;

       x += lowbit(x);

    }

}

int inline sum(int x){

    int s = ;

    while(x > ){

      s += c[x];

      x -= lowbit(x);

    }

    return s;

}

void  solve()

{

    int t=;

    for(int i=;i<=N;i++)

    {

            if(que[t].H==-)

            {

                break;

            }

            while(que[t].H<a[i].value && que[t].H!=-)

            {

                ans[ que[t].cnt ]=sum(que[t].R)-sum(que[t].L-);

                t++;

            }

            add(a[i].id);

            while(a[i].value==a[i+].value && i<=N)

            {

                 i++;

                 add(a[i].id);

            }

            while(que[t].H==a[i].value && que[t].H!=-)

            {

                ans[ que[t].cnt ]=sum(que[t].R)-sum(que[t].L-);

                t++;

            }

    }

    for(int i=t;i<=M;i++)

    {

        ans[que[i].cnt]=sum(que[i].R)-sum(que[i].L-);

    }

}

int main()

{

    // freopen("test.txt","r",stdin);

    int t;

    scanf("%d",&t);

    int Case=;

    for(int Case=;Case<=t;Case++)

    {

      scanf("%d%d",&N,&M);

      init();

      for(int i=;i<=N;i++)

      {

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

        a[i].id=i;

      }

      for(int i=;i<=M;i++)

      {

         scanf("%d%d%d",&que[i].L,&que[i].R,&que[i].H);

         que[i].L++;

         que[i].R++;

         que[i].cnt=i;

      }

      sort(a+,a+N+,cmp1);

      sort(que+,que+M+,cmp2);

       solve();

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

        for(int i = ; i <= M; ++i){

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

       }

    }

    return ;

}

边查边插：

#include <iostream>

#include <cstdio>

#include <time.h>

#include <stdlib.h>

#include <cstring>

#include<algorithm>

#define maxn 110000

#define LL  int

using namespace std;

struct node

{

   LL value,id;

};

struct querynode

{

    LL L,R,H,cnt;

};

node a[maxn];

querynode  que[maxn];

LL c[maxn];

LL N,M;

LL ans[maxn];

void init()

{

   memset(a,,sizeof(a));

   memset(c,,sizeof(c));

   memset(ans,,sizeof(ans));

   for(int i=;i<maxn;i++)

   {

       que[i].H=-;

   }

}

bool cmp1(node a,node b)

   {

       return a.value<b.value;

   }

bool cmp2(querynode a,querynode b)

{

        return a.H<b.H;

}

int inline lowbit(int x){

    return x & (-x);

}

void inline add(int x){

    while(x <= N ){

       c[x]++;

       x += lowbit(x);

    }

}

int inline sum(int x){

    int s = ;

    while(x > ){

      s += c[x];

      x -= lowbit(x);

    }

    return s;

}

void solve1()

{

       for(int aski = ,ditj = ; aski < M; ++aski){

           while(ditj < N && que[aski].H >= a[ditj].value){

              add(a[ditj].id);

              ditj++;

           }

           ans[que[aski].cnt] = sum(que[aski].R) - sum(que[aski].L - );

       }

}

int main()

{

     //freopen("test.txt","r",stdin);

    int t;

    scanf("%d",&t);

    int Case=;

    for(int Case=;Case<=t;Case++)

    {

      scanf("%d%d",&N,&M);

      init();

      for(int i=;i<N;i++)

      {

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

        a[i].id=i+;

      }

      for(int i=;i<M;i++)

      {

         scanf("%d%d%d",&que[i].L,&que[i].R,&que[i].H);

         que[i].L++;

         que[i].R++;

         que[i].cnt=i+;

      }

      sort(a,a+N,cmp1);

      sort(que,que+M,cmp2);

       solve1();

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

        for(int i = ; i <= M; ++i){

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

       }

    }

    return ;

}

巴特西

hdu4417(离线操作 + 树状数组)

最新文章

热门文章