HDU Always Cook Mushroom：極角排序 + 樹狀數組離線處理三角形區域權值和

問題建模

1000×1000 網格，點 (x,y) 權值 (x+A)(y+B)。
M ≤ 10⁵ 個查詢：每查詢給 (a,b,x)，求直角三角形區域和。三角形頂點：(0,0), (x,0), 以及射線 y = (b/a)x 與 x=x 交點 (x, bx/a)。保證所有網格點在 [1,1000] 內。

核心洞察：極角掃描線 + 離線處理

三角形由 x 軸與射線 θ = atan2(b,a) 夾住。
若將所有網格點按極角 atan2(y,x) 排序，查詢也按 atan2(b,a) 排序。
想像一根射線從 x 軸逆時針掃過：掃過的點即滿足 y/x ≤ b/a 的點。
對於查詢 (a,b,x)，需再限制 x ≤ x_q → 樹狀數組維護 x 軸前綴和。

演算法流程

1. 預處理：生成所有 10⁶ 個網格點 (x,y)，計算極角 s = y/x（用 double），按 s 升序排序。
2. 讀入查詢：計算極角 s = b/a，存 (a,b,x,id,s)，按 s 升序排序（同極角按 x 升序）。
3. 離線掃描：
    初始化 BIT（大小 1000）。
    指標 ptr = 0 指向點陣列。
    遍歷排序後查詢：
     while (ptr < 1e6 && points[ptr].s <= query.s)：
      BIT.add(points[ptr].x, (points[ptr].x+A)*(points[ptr].y+B))
      ++ptr
     ans[query.id] = BIT.sum(query.x)
4. 按原順序輸出。

完整 C++ 實作

#include 
#include 
#include 
#include 
#include 
using namespace std;

typedef long long ll;
const int MAXG = 1005;
const int MAXQ = 100005;

struct Point {
    int x, y;
    double ang;
} pts[MAXG * MAXG];

struct Query {
    int a, b, x, id;
    double ang;
} qs[MAXQ];

ll BIT[MAXG];
ll ans[MAXQ];
int idxMap[MAXQ];  // 原始順序 -> 排序後位置

inline int lowbit(int x) { return x & -x; }
void bitAdd(int x, ll val) {
    for (; x <= 1000; x += lowbit(x)) BIT[x] += val;
}
ll bitSum(int x) {
    ll res = 0;
    for (; x > 0; x -= lowbit(x)) res += BIT[x];
    return res;
}

bool cmpPt(const Point& a, const Point& b) { return a.ang < b.ang; }
bool cmpQ(const Query& a, const Query& b) {
    if (a.ang != b.ang) return a.ang < b.ang;
    return a.x < b.x;
}

int main() {
    // 1. 預處理所有網格點極角
    int ptCnt = 0;
    for (int i = 1; i <= 1000; ++i)
        for (int j = 1; j <= 1000; ++j) {
            pts[ptCnt].x = i;
            pts[ptCnt].y = j;
            pts[ptCnt].ang = 1.0 * j / i;  // 避免 atan2，單調等價
            ++ptCnt;
        }
    sort(pts, pts + ptCnt, cmpPt);

    int T;
    scanf("%d", &T);
    for (int tc = 1; tc <= T; ++tc) {
        ll A, B;
        int M;
        scanf("%lld%lld%d", &A, &B, &M);
        for (int i = 0; i < M; ++i) {
            scanf("%d%d%d", &qs[i].a, &qs[i].b, &qs[i].x);
            qs[i].ang = 1.0 * qs[i].b / qs[i].a;
            qs[i].id = i;
        }
        sort(qs, qs + M, cmpQ);
        for (int i = 0; i < M; ++i) idxMap[qs[i].id] = i;

        memset(BIT, 0, sizeof(BIT));
        int ptr = 0;
        for (int i = 0; i < M; ++i) {
            while (ptr < ptCnt && pts[ptr].ang <= qs[i].ang) {
                ll val = (ll)(pts[ptr].x + A) * (pts[ptr].y + B);
                bitAdd(pts[ptr].x, val);
                ++ptr;
            }
            ans[i] = bitSum(qs[i].x);
        }

        printf("Case #%d:\n", tc);
        for (int i = 0; i < M; ++i) {
            printf("%lld\n", ans[idxMap[i]]);
        }
    }
    return 0;
}

關鍵優化細節

• 極角用 y/x 代替 atan2：單調性相同，避免昂貴三角函數，精度足夠（分母 ≤ 1000）。
• 離線處理：將 M 次查詢合併為一次掃描，總複雜度 O((10⁶ + M) log 1000)。
• BIT 尺寸固定 1000：x 座標範圍固定，操作極快。
• 快速輸入輸出：用 scanf/printf 或自訂快速 IO，避免 iostream 慢。

複雜度分析

• 預處理：10⁶ log 10⁶ ≈ 2×10⁷，一次性。
• 每測資：排序查詢 O(M log M)，掃描 O(10⁶ + M) log 1000。
• 總時間：< 1 秒（C++ 優化後）。
• 空間：點陣列 10⁶ × 16 bytes ≈ 16 MB，BIT 1000 × 8 bytes ≈ 8 KB。