hdu5032 树状数组

题意:

对于一个1000*1000的Mushroom，

起点在（1，1）给定一个斜率和一个x，求由斜率和x所对应的直线构成的三角形内蘑菇的总值。

每个点的对应的值为(x+A)(y+B)

解

每个点都有一个相对于(1,1)的一个斜率我们就按照这个斜率的大小进行排序大的放在后面

然后我们对于每个要查询的点的斜率的进行排序

采用离线的方法去计算我们要求的东西这样我们对于每次查询都把小于他斜率的点扔进树状数组对应的x中就可以了

然后求和

#include <iostream>

#include <algorithm>

#include <string.h>

#include <cstdio>

using namespace std;

const int maxn =+;

typedef long long LL;

struct point

{

    int x,y;

    LL ans;

    double p;

    point(int cx=,int cy=,LL cans=,double cp=)

    {

          x=cx; y=cy; ans=cans; p=cp;

    }

}s[maxn],sc[maxn];

bool cmpp(point a, point b)

{

     return a.p<b.p;

}

bool cmpi(point a, point b)

{

     return a.y<b.y;

}

LL C[];

int lowbit(int x)

{

     return x&-x;

}

void add(int x,LL d)

{

    while(x<=)

        {

             C[x]+=d; x+=lowbit(x);

        }

}

LL sum(int x)

{

    LL ret=;

    while(x>)

    {

       ret+=C[x]; x-=lowbit(x);

    }

    return ret;

}

int main()

{

    int num=;

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

         for(int j=; j<=; j++)

           s[num++]=point(i,j,,1.0*j/i);

    int cas;

    sort(s,s+num,cmpp);

    scanf("%d",&cas);

    for(int cc =; cc<=cas; cc++)

    {

         LL A,B;

         scanf("%I64d%I64d",&A,&B);

         int m;

         scanf("%d",&m);

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

             int a,b,x;

             scanf("%d%d%d",&a,&b,&x);

             sc[i]=point( x,i,,1.0*b/a );

        }

        sort(sc,sc+m,cmpp);

        int now=;

        memset(C,,sizeof(C));

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

        {

            while(now<&&s[now].p<=sc[i].p){

                 add(s[now].x,1LL*(s[now].x+A)*(s[now].y+B));now++;

            }

            sc[i].ans=sum(sc[i].x);

        }

        sort(sc,sc+m,cmpi);

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

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

        {

            printf("%I64d\n",sc[i].ans);

        }

    }

    return ;

}

巴特西

hdu5032 树状数组

最新文章

热门文章