题目链接：http://poj.org/problem?id=2481 我感觉这道题给那个那个差的比较就是坑爹的……我按着差写了大半天结果WA了个各种惨啊…… 好吧，这道题是按照权值建立线段树，意思就是把每一个点加入到它应有的大小范围内，线段树上面每一个点维护的是该区间内有多少个点，这样很容易就能查出来比某一个元素大的元素有多少个。而且，还得先对所有的点排序，主排序应该是把s从小到大排序，当s相等的时候，e从大到小排序，这样就必须记录每个元素原来的位置，这样每次插入一个新的元素的时候，在它之前插入的所有的元素s上都是满足条件的，换言之，线段树中只需要维护e的情况就行了。其实……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
|