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