题目链接:http://poj.org/problem?id=2352 既然题目中说Y坐标是升序给出,那么只需要维护到当前结点的小于X的值,这样很快能求出来所有的等级,然后就balabalabala……
![](/Images/OutliningIndicators/ContractedBlock.gif) view code 1 #include <iostream> 2 #include <cstdio> 3 #include <cstdlib> 4 #include <cstring> 5 #include <cmath> 6 #include <algorithm> 7 using namespace std; 8 #define lson l, m, rt << 1 9 #define rson m + 1, r, rt << 1 | 1 10 const int maxn = 32010; 11 int sum[maxn << 2], ans[15010]; 12 void PushUp(int rt){ 13 sum[rt] = sum[rt << 1] + sum[rt << 1 | 1]; 14 } 15 void build(int l, int r, int rt){ 16 sum[rt] = 0; 17 if (l == r) return; 18 int m = (l + r) >> 1; 19 build(lson); 20 build(rson); 21 PushUp(rt); 22 } 23 void update(int x, int l, int r, int rt){ 24 if (l == r){ 25 sum[rt] += 1; 26 return; 27 } 28 int m = (l + r) >> 1; 29 if (x <= m) update(x, lson); 30 else update(x, rson); 31 PushUp(rt); 32 } 33 int query(int ll, int rr, int l, int r, int rt){ 34 if (ll <= l && rr >= r) return sum[rt]; 35 int m = (l + r) >> 1; 36 int ret = 0; 37 if (ll <= m) ret += query(ll, rr, lson); 38 if (rr > m) ret += query(ll, rr, rson); 39 return ret; 40 } 41 int main(){ 42 int n; 43 while (~scanf("%d", &n)){ 44 build(0, maxn, 1); 45 int x, y; 46 for (int i = 0; i < n; i++){ 47 scanf("%d%d", &x, &y); 48 int cnt = query(0, x, 0, maxn, 1); 49 ans[cnt] += 1; 50 update(x, 0, maxn, 1); 51 } 52 for (int i = 0; i < n; i++) printf("%d\n", ans[i]); 53 } 54 return 0; 55
|