【題解】ZeroJudge d847: 2D rank finding problem

【範例】二維BIT (樹狀數組)
【題目敘述】https://zerojudge.tw/ShowProblem?problemid=d847

  • bit[x][y]:相對於 ( x , y ),有多少個點 ( a , b ) 在它的左下方 a < x , b < y。
  • 每讀入一組 ( xi , yi ) ,即更新bit,表示增加一點到所有受影響的區間(前綴和即為比該點小的點的個數),xi <= x <= 1000, yi <= y <= 1000。
  • query( x, y ):有多少個點 ( a , b ) 滿足 a < x , b < y,或 a <= x – 1 , b <= y – 1。
  • (Line-34):注意,本題有多組測試資料。
#include <iostream>
#include <cstring>
using namespace std;

const int maxn = 1005;
int n, bit[maxn][maxn], qx, qy, a[10005][2];

void update(int x, int y){
    while (x < maxn){
        int ty = y;
        while (ty < maxn){
            bit[x][ty]++;
            ty += ty & (-ty);
        }
        x += x & (-x);
    }
}

int query(int x, int y){
    int ret = 0;
    while (x){
        int ty = y;
        while (ty){
            ret += bit[x][ty];
            ty -= ty & (-ty);
        }
        x -= x & (-x);
    }
    return ret;
}

int main() {
    while (cin >> n){
        memset(bit, 0, sizeof(bit));
        for (int i = 0; i < n; i++){
            cin >> a[i][0] >> a[i][1];
            update(a[i][0], a[i][1]);
        }
        for (int i = 0; i < n; i++){
            cout << query(a[i][0]-1, a[i][1]-1) << "\n";
        }
    }
    return 0;
}
分享本文 Share with friends