[ZJ][N*NlogN][BIT] a533. IOI2004 Day1.1.阿特米斯
內容 ：
宙斯給森林女神阿特米斯一塊矩形土地種植樹木。這塊矩形土地的左邊位於正Y軸，下邊位於正X軸，左下方位於(0,0)原點。宙斯告訴阿特米斯神樹木只能種在矩形土地內的的整數點上。阿特米斯神希望森林看起來非常自然，所以她種樹的時候會注意任何兩棵樹的連線都不會與X軸或Y軸平行。
宙斯有時候會請阿特米斯神依下列條件為他砍樹：
1. 宙斯希望至少要砍T棵樹。
2. 宙斯希望提倡足球運動，所以阿特米斯神必須將一矩形區域內的所有樹都砍倒，同時不能砍任何未於該區域外的樹。
3. 此矩形區域的每一邊都與X軸或Y軸平行。
4. 此矩型區域的一組對角必須位於樹的位置上，而且這兩棵位於對角的樹也必須砍除。
阿特米斯神非常喜歡樹，所以她希望以砍倒最少的樹來滿足上數條件。請寫一個程式，從樹木種植情形及給定之最少需砍數目棵樹T，找出此矩形區域。
輸入說明 ：
輸出說明 ：
輸出只有一行，包含兩個以一空白隔開的整數I及J。阿特米斯神會使用第I棵(輸入的第I+2行)及第J棵樹(輸入的第J+2行)作為砍樹矩形區域的兩個對角。選取區域的最佳方法可能超過一種，但你只需輸出其中一種，I及J的輸出順序不重要。每一組測試資料都存在至少一組解。
為了judge方便，請只輸出最少要砍倒幾棵樹的數量。
範例輸入 ：
範例輸入1321 12 35 6範例輸入2645 11 24 32 43 56 6
範例輸出 ：
範例輸出12範例輸出25
提示 ：
在所有的輸入中，1<N≤20000, 0≤X,Y≤64000 且1<T≤N。
除此之外，在50%的輸入中，1<N<5000。
1.由於當年比賽主機特強，看似不合理的複雜度是可以在1s內過的..
2.ZJ主機特強
3.注意記憶體限制
出處 ：
這題的複雜度真的是看似不合理, 卻能通過, 為什麼是 N*NlogN呢, 這裡解釋一下,
我們先排序座標 x 軸依序由小到大, 接著我們使用樹狀數組(BIT), 去累計
對於某一個左端點 Pi, 使用新的一個 BIT, 分成上下兩組, 然後查詢小於等於 D[j].y 的值,
我不太會解釋, 或許你可以看程式碼理解, 當然有人願意提供比較詳細的題解也行,
幫我解釋也好 ...
#include <stdio.h>
#include <stdlib.h>
typedef struct {
unsigned short x, y;
} Pt;
int cmp(const void *i, const void *j) {
static Pt *a, *b;
a = (Pt *)i, b = (Pt *)j;
return a->x - b->x;
}
int main() {
int n, t, i, j;
while(scanf("%d %d", &n, &t) == 2) {
Pt D[n];
int L = 0;
for(i = 0; i < n; i++) {
scanf("%hu %hu", &D[i].x, &D[i].y);
D[i].x++, D[i].y++;
if(D[i].y > L) L = D[i].y;
}
qsort(D, n, sizeof(Pt), cmp);
int ans = 0xfffffff;
for(i = 0; i < n; i++) {
short upC[64005] = {}, doC[64005];
int uCnt = 0, dCnt = 0, idx, sum;
for(j = i; j < n; j++) {
if(D[j].y >= D[i].y) {
uCnt++;
idx = D[j].y;
while(idx <= L) {
upC[idx]++;
idx += idx&(-idx);
}
if(uCnt >= t) {
sum = 0, idx = D[j].y;
while(idx) {
sum += upC[idx];
idx -= idx&(-idx);
}
if(sum >= t && sum < ans)
ans = sum;
}
} else {
dCnt++;
idx = D[j].y;
while(idx <= D[i].y) {
doC[idx]++;
idx += idx&(-idx);
}
if(dCnt >= t) {
sum = 0, idx = D[j].y;
while(idx) {
sum += doC[idx];
idx -= idx&(-idx);
}
sum = dCnt - sum;
if(sum >= t && sum < ans)
ans = sum;
}
}
}
if(ans == t) break;
}
printf("%d\n", ans);
}
return 0;
}