Hdu 5032 Always Cook Mushroom (樹狀數組)

Hdu 5032 Always Cook Mushroom (樹狀數組)

題目大意：

在一個1000*1000的二維平面上，每一個整點都有一個權值，權值大小是 the production in the grid points (x, y) is (x + A)(y + B) where A, B are two constant.

思路分析：

先離線處理出所有的詢問，對於每一個詢問都有一個極角，按照極角排序。

然後對於平面上每一個點，都依次的加入到BIT中，當當前的這個詢問的極角比這個點到原點的對應極角要大的時候，就將這個點加進去。

可以理解成有一根線，按照逆時針的方向在掃描整個二維平面，當這根線和某一個詢問重合的時候，記錄和，否則將掃過的所有點加入到BIT中。

#include 
#include 
#include 
#include 
#include 
#define lowbit(x) (x&(-x))
#define maxn 1005

using namespace std;
typedef long long ll;
int A,B;
struct node
{
    int r,c;
    double p;
    node(){}
    node(int _r,int _c,double _p):r(_r),c(_c),p(_p){}
    bool operator < (const node &cmp)const
    {
        return p cq;
struct line
{
    int x,id;
    ll ans;
    double p;
    line(){}
    line(int _x,double _p):x(_x),p(_p){}
    bool operator < (const line &cmp)const
    {
        return p scline;
ll bit[1005];
bool cmp_id(line a,line b)
{
    return a.id=1;x-=lowbit(x))res+=bit[x];
    ll ret=0;
    for(int x=l-1;x>=1;x-=lowbit(x))ret+=bit[x];
    return res-ret;
}

int main()
{
    int T,cas=1;

    cq.clear();

    for(int i=1;i<=1000;i++)
    {
        for(int j=1;j<=1000;j++)
        {
            cq.push_back(node(i,j,1.0*i/j));
        }
    }

    sort(cq.begin(),cq.end());


    for(scanf("%d",&T);T--;)
    {
        scanf("%d%d",&A,&B);

        scline.clear();

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

        for(int i=0;i