題目鏈接：http://poj.org/problem?id=2481 我感覺(jué)這道題給那個(gè)那個(gè)差的比較就是坑爹的……我按著差寫(xiě)了大半天結(jié)果WA了個(gè)各種慘啊…… 好吧，這道題是按照權(quán)值建立線段樹(shù)，意思就是把每一個(gè)點(diǎn)加入到它應(yīng)有的大小范圍內(nèi)，線段樹(shù)上面每一個(gè)點(diǎn)維護(hù)的是該區(qū)間內(nèi)有多少個(gè)點(diǎn)，這樣很容易就能查出來(lái)比某一個(gè)元素大的元素有多少個(gè)。而且，還得先對(duì)所有的點(diǎn)排序，主排序應(yīng)該是把s從小到大排序，當(dāng)s相等的時(shí)候，e從大到小排序，這樣就必須記錄每個(gè)元素原來(lái)的位置，這樣每次插入一個(gè)新的元素的時(shí)候，在它之前插入的所有的元素s上都是滿足條件的，換言之，線段樹(shù)中只需要維護(hù)e的情況就行了。其實(shí)……e符合條件了差值自然也就符合條件了。
  view code
1 #include <iostream>
2 #include <cstdio>
3 #include <algorithm>
4 #include <cstring>
5 using namespace std;
6 #define lson l, m, rt << 1
7 #define rson m + 1, r, rt << 1 | 1
8 const int maxn = 100100;
9 struct data{
10 int s, e, i;
11 friend bool operator < (const data &a, const data &b){
12 if (a.s != b.s) return a.s < b.s;
13 return a.e > b.e;
14 }
15 }cow[maxn];
16 int num[maxn << 2], ans[maxn];
17 void build(int l, int r, int rt){
18 num[rt] = 0;
19 if (l == r) return;
20 int m = (l + r) >> 1;
21 build(lson);
22 build(rson);
23 }
24 void update(int x, int l, int r, int rt){
25 num[rt] += 1;
26 if (l == r) return;
27 int m = (l + r) >> 1;
28 if (x <= m) update(x, lson);
29 else update(x, rson);
30 }
31 int query(int ll, int rr, int l, int r, int rt){
32 if (ll <= l && rr >= r) return num[rt];
33 int m = (l + r) >> 1;
34 int ret = 0;
35 if (ll <= m) ret += query(ll, rr, lson);
36 if (rr > m) ret += query(ll, rr, rson);
37 return ret;
38 }
39 int main(){
40 int n;
41 while (~scanf("%d", &n) && n){
42 memset(ans, 0, sizeof(ans));
43 int m = 0;
44 for (int i = 0; i < n; i++){
45 scanf("%d%d", &cow[i].s, &cow[i].e);
46 cow[i].s += 1; cow[i].e += 1;
47 m = max(cow[i].e, m);
48 cow[i].i = i;
49 }
50 sort(cow, cow + n);
51 build (1, m, 1);
52 for (int i = 0; i < n; i++){
53 if (i && cow[i].s == cow[i - 1].s && cow[i].e == cow[i - 1].e){
54 ans[cow[i].i] = ans[cow[i - 1].i];
55 update(cow[i].e, 1, m, 1);
56 }
57 else{
58 ans[cow[i].i] = query(cow[i].e, m, 1, m, 1);
59 update(cow[i].e, 1, m, 1);
60 }
61 }
62 for (int i = 0; i < n; i++){
63 printf("%d", ans[i]);
64 if (i != n-1) printf(" ");
65 else printf("\n");
66 }
67 }
68 return 0;
69
|