d847 - 2D rank finding problem
題目描述
題目要求計算二度平面上給定點集合中，每個點的排名。排名定義為集合中比該點小的點的個數，其中點的大小關係定義為：A > B 若且唯若 a1 > b1 且 a2 > b2。
解題思路
這題的核心是計算每個點左下方點的數量。直接暴力比較會導致時間複雜度過高。可以使用二維 Binary Indexed Tree (BIT) 來高效地計算。BIT 允許我們在 O(log^2 n) 的時間內查詢矩形區域內的元素數量。
具體來說，對於每個點 (x, y)，我們需要計算滿足 a < x 且 b < y 的點 (a, b) 的數量。這相當於計算矩形區域 (0, 0) 到 (x-1, y-1) 內的點的數量。BIT 儲存的是累積和，因此可以通過查詢 BIT[x-1][y-1] 得到這個數量。
程式碼中，edit(x, y) 函數用於在 BIT 中更新點 (x, y) 的值，sum(x, y) 函數用於查詢矩形區域 (0, 0) 到 (x, y) 內的點的數量。
複雜度分析
- 時間複雜度: O(n log^2 n)，其中 n 是點的數量。對於每個點，我們需要進行一次 BIT 查詢和一次 BIT 更新，每次操作的時間複雜度都是 O(log^2 n)。
- 空間複雜度: O(n^2)，因為 BIT 的大小是 1001x1001。
程式碼
#include <iostream>
using namespace std;
int BIT[1001][1001],MAX_N=1000;
int lowerbit(int x){
return (x)&(-x);
}
int edit(int x,int y){
for(int i=x;i<=MAX_N;i+=lowerbit(i))
for(int j=y;j<=MAX_N;j+=lowerbit(j))
++BIT[i][j];
}
int sum(int x,int y){
int rt=0;
for(int i=x;i>0;i-=lowerbit(i))
for(int j=y;j>0;j-=lowerbit(j))
rt+=BIT[i][j];
return rt;
}
int main(){
cin.tie(0);ios::sync_with_stdio(0);
int n;
while(cin >> n){
for(int i=0;i<1001;++i)
for(int j=0;j<1001;++j)
BIT[i][j]=0;
int a[n][2];
for(int i=0;i<n;++i){
cin >> a[i][0] >> a[i][1];
edit(a[i][0],a[i][1]);
}
for(int i=0;i<n;++i)
cout << sum(a[i][0]-1,a[i][1]-1) << "\n";
}
}