題目鏈接：

https://vjudge.net/problem/POJ-2481

題目大意：

if Si <= Sj and Ej <= Ei and Ei - Si > Ej - Sj, we say that cow _i is stronger than cow _j.?

此處的含義就是線段[Sj, Ej]是線段[Si, Ei]的真子集，最后需要求出每條線段是多少條線段的真子集。

解題思路：

此處可以先對(duì)E坐標(biāo)從大到小排序，相同的E對(duì)S從小到大排序，排完序后直接把S放入樹(shù)狀數(shù)組中，求出當(dāng)前在樹(shù)狀數(shù)組中有多少比當(dāng)前S小的數(shù)目。

由于E坐標(biāo)從大到小，所以在某個(gè)線段放之前，終點(diǎn)在該線段的后面的線段已經(jīng)全部加入了樹(shù)狀數(shù)組。而S比當(dāng)前S小的線段一定是真包含該線段的。

WA點(diǎn)：注意此處求的是被多少線段真包含，所以在排序之后需要判斷，如果兩者線段一樣那么就直接用前面的結(jié)果更新后面的結(jié)果。

?

1 #include<cstdio> 2 #include<cstring> 3 #include<iostream> 4 #include<algorithm> 5 #include<string> 6 #include<cmath> 7 #include<set> 8 #include<queue> 9 #include<map> 10 #include<stack> 11 #include<vector> 12 #include<list> 13 #include<deque> 14 #include<sstream> 15 #include<cctype> 16 #define REP(i, n) for(int i = 0; i < (n); i++) 17 #define FOR(i, s, t) for(int i = (s); i < (t); i++) 18 using namespace std; 19 typedef long long ll; 20 int T, n, m, cases; 21 const int maxn = 100100; 22 struct node 23 { 24 int x, y, id; 25 bool operator < (const node & a)const 26 { 27 return y > a.y || (y == a.y && x < a.x); 28 } 29 }a[maxn]; 30 int tree[maxn]; 31 int ans[maxn]; 32 int lowbit(int x) 33 { 34 return x&(-x); 35 } 36 int sum(int x) 37 { 38 int ret = 0; 39 while(x > 0) 40 { 41 ret += tree[x]; 42 x -= lowbit(x); 43 } 44 return ret; 45 } 46 void add(int x, int d) 47 { 48 while(x < maxn) 49 { 50 tree[x] += d; 51 x += lowbit(x); 52 } 53 } 54 int main() 55 { 56 while(scanf("%d", &n) && n) 57 { 58 memset(tree, 0, sizeof(tree)); 59 memset(ans, 0, sizeof(ans)); 60 memset(a, 0,sizeof(a)); 61 for(int i = 1; i <= n; i++) 62 { 63 scanf("%d%d", &a[i].x, &a[i].y); 64 a[i].x++; a[i].y++; 65 a[i].id = i; 66 } 67 sort(a + 1, a + n + 1); 68 for(int i = 1; i <= n; i++) 69 { 70 if(a[i].x == a[i - 1].x && a[i].y == a[i - 1]. y)ans[a[i].id] = ans[a[i - 1].id]; 71 else ans[a[i].id] = sum(a[i].x); 72 add(a[i].x, 1); 73 } 74 for(int i = 1; i <= n; i++) 75 { 76 printf("%d ", ans[i]); 77 ///若在此處在if判斷是否輸出空格會(huì)超時(shí)，以后就先輸出a[1],然后依次輸出空格+數(shù)字 78 } 79 printf("\n"); 80 } 81 }

?

轉(zhuǎn)載于:https://www.cnblogs.com/fzl194/p/8945189.html

總結(jié)

以上是生活随笔為你收集整理的POJ-2481 Cows---树状数组的运用的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。