hdu 5032 알 아 채 기 어 려 운 트 리 배열

http://acm.hdu.edu.cn/showproblem.php?pid=5032
1000 x 1000 의 점진 을 정 하고 m 조 는 매번 (0, 0), (x, 0) 점 1 과 원점 에서 출발 하 는 방향 벡터 (a, b) 로 구 성 된 직각 삼각형 으로 둘러싸 인 점 의 값 과 값 을 묻는다.
먼저 1000 x1000 개의 점 을 극 각 관 계 를 오프라인 으로 한 다음 에 m 개의 질문 에 대해 극 각 으로 정렬 하고 add 를 멈 추 지 않 으 며 문의 하 는 극 각 을 만나면 query 접두사 와

#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <string>
#include <queue>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
#define RD(x) scanf("%d",&x)
#define RD2(x,y) scanf("%d%d",&x,&y)
#define clr0(x) memset(x,0,sizeof(x))
typedef long long LL;
int A,B,m;
struct point{
    int x,y;
    LL ans;
    double p;
}s[1000005],sc[100005];
bool cmpp(point a,point b)
{
    return a.p < b.p;
}
bool cmpid(point a,point b)
{
    return a.y < b.y;
}
LL bit[1005];
void add(int x,LL v)
{
    for(int i = x;i <= 1000;i += (i&-i))
        bit[i] += v;
}
LL query(int x)
{
    LL ans = 0;
    for(int i = x;i >= 1;i -= (i&-i))
        ans += bit[i];
    return ans;
}
int main(){
    int _,cnt = 0,cas = 1,x,a,b;
    RD(_);
    for(int i = 1;i <= 1000;++i)
    for(int j = 1;j <= 1000;++j){
        s[cnt++] = (point){i,j,0,1.0*j/i};
    }
    sort(s,s+cnt,cmpp);
    while(_--){
        RD2(A,B);
        RD(m);
        for(int i = 0;i < m;++i){
            RD2(a,b);RD(x);
            sc[i] = (point){x,i,0,1.0*b/a};
        }
        sort(sc,sc+m,cmpp);
        clr0(bit);
        int now = 0;
        for(int i = 0;i < m;++i){
            while(s[now].p <= sc[i].p){
                add(s[now].x,(LL)(s[now].x + A)*(s[now].y + B));
                now++;
            }
            sc[i].ans = query(sc[i].x);
        }
        sort(sc,sc+m,cmpid);
        printf("Case #%d:
",cas++);
        for(int i = 0;i < m;++i)
            //cout<<sc[i].ans<<endl;
            printf("%I64d
",sc[i].ans);
     }
     return 0;
 }