大神的世界

題目的論述很簡單，就是要找出一個矩形區塊中，樹的數量 >= T  且最少的樹數

我原本的想法是，記錄區塊中每一點，其左下方包含的樹數

但這不實際，因為最多有 64000 * 64000 個點，且每個點至少 4 byte ( 假設我們用 int 存 )

則所需空間大約為 64k * 64k * 8 = 幾萬 M  ( 河河河)

google 了別人的想法後，發現 BIT 這個神奇的東西

https://blog.csdn.net/Yaokai_AssultMaster/article/details/79492190

這裡，我假設你已經懂 BIT 了

我們的想法就是先按樹的 x 座標排序

並依序作為矩形區塊的頂點 (可能是左下，也可能是左上，詳情往下看, 另外，方便起見，我們把它稱作基準點)

 接著將後面的樹加入 (  後面 : x 座標 >= 該點 )

並將加入的點作為矩形區塊的頂點 ( 可能是右上，也可能是右下)

再計算此矩形區塊中的樹數

怎麼計算呢？

這裡我們把 y 座標視為原數組的 index，value 部份則是該 y 座標有幾棵樹

每加入一棵樹就更新一次

並計算該矩形的區段和 (也就是基準點的 y 座標，與新加入點的 y 座標的區段)

這個數也代表著此矩形區域的樹數

圖示

以上圖來說，我們以紅點為基準點，並加入後方的點 ( 紫點、藍點 若干個綠點）

我們先來說說紫點 ，紫點加入時，藍點與右方的綠點皆尚未加入，真正加入的只有紫點左方與紅點右方的綠點

而我們要找的矩形區塊，即為紫色部份

可以發現，紫色區塊皆在紅點上方

因此，整個 BIT 只有考慮紅點上方的部份

那可想而知，每一個基準點應該都要有兩個 BIT ( 分別存上面及下面 )

事實上，紫點的 BIT 區段和直接算就行了

但藍點就必須特別注意

因為籃點 BIT 的區段和是藍色區塊下方

所以藍色矩形的樹數，必須用已加入的樹 (紅點下方)  去扣，才能得到

ps：

如果想只用一個 BIT 也是可以，但區段和要算兩次 ( 基準點 和 新加入的點 )

此外

如果基準點在上方，則區段和分別為   sum( 0 , 基準點 y 座標 ) - sum( 0 , 新加入的點的 y 座標 - 1 )

否則為  sum( 0 , 新加入的點的 y 座標 )  - sum( 0 , 基準點 y 座標 - 1 )

以下程式碼修改自 台長大大

#include <cstdio>
#include <cstdlib>

constexpr int MAX_Y = 64001;

struct tree{
    unsigned short x, y;
};

int cmp(const void *_a, const void *_b)
{
    tree *ta = (tree *)_a;
    tree *tb = (tree *)_b;
    return ta->x - tb->x;
}

int main() {
    int tree_num, query_num;
    while(scanf("%d %d", &tree_num, &query_num) == 2) {
        
        tree T[tree_num];

        int max_y = 0;
        for(int i = 0; i < tree_num; i+=1) {
            scanf("%hu %hu", &T[i].x, &T[i].y);
            T[i].x += 1; T[i].y += 1;
            if(T[i].y > max_y) max_y = T[i].y;
        }

        qsort(T, tree_num, sizeof(tree), cmp);

        int ans = 0xfffffff;
        for(int i = 0; i < tree_num; i+=1) {
            short upperBIT[MAX_Y] = {}, lowerBIT[MAX_Y] = {};
            int upper_tree_cnt = 0, lower_tree_cnt = 0;
            for(int j = i; j < tree_num; j++) {
                if(T[j].y >= T[i].y) {
                    upper_tree_cnt += 1;

                    int idx = T[j].y;
                    while(idx <= max_y) {
                        upperBIT[idx]++;
                        idx += idx&(-idx);
                    }

                    if(upper_tree_cnt >= query_num) {
                        int sum = 0;
                        idx = T[j].y;
                        while(idx) {
                            sum += upperBIT[idx];
                            idx -= idx&(-idx);
                        }
                        if(sum >= query_num && sum < ans)
                            ans = sum;
                    }
                } else {
                    lower_tree_cnt+=1;

                    int idx = T[j].y;
                    while(idx <= T[i].y) {
                        lowerBIT[idx]++;
                        idx += idx&(-idx);
                    }

                    if(lower_tree_cnt >= query_num) {
                        int sum = 0;
                        idx = T[j].y;
                        while(idx) {
                            sum += lowerBIT[idx];
                            idx -= idx&(-idx);
                        }
                        sum = lower_tree_cnt - sum;
                        if(sum >= query_num && sum < ans)
                            ans = sum;
                    }
                }
            }

            if(ans == query_num)
                break;
        }

        printf("%d\n", ans);
    }
    return 0;
}