這題主要是要能很好的理解，就像2352一樣。那個(gè)題一看不是樹狀數(shù)組，但是，仔細(xì)一想，是樹狀數(shù)組。這題可以用那題的一些想法，對end排序(從大到小
，如果相等的話，那么然start從小到大排序，這樣的話，用樹狀數(shù)組進(jìn)行操作時(shí)后面的不會(huì)影響前面的)這樣處理之后，這題基本思路是OK了，但是可能還
不行，因?yàn)槟銢]有處理s，e都相等的，也就是有可能多加了東西。那么我們就要減去這些多加的，或者直接等于前一個(gè)就行了，或者可以用注釋掉的方法，
具體代碼見下
見如下代碼
CODE
1/**//*
2
ID:Klion
3 PROG:POJ_2481
4 LANG:C++
5
*/
6
#include <iostream>
7using namespace std;
8typedef struct
9
{
10 int s,e,no,ans;//記錄start，end，no，ans，no用來排序，ans是結(jié)果
11}cow;
12cow cc[100006];//輸入數(shù)據(jù)的數(shù)組
13int tree[100006];//樹狀數(shù)組
14void update(int x,int val)
15{
16 while(x <= 100006)
17
{
18 tree[x] += val;
19 x += (x & -x);
20
}
21 return;
22}
23int read(int x)
24{
25 int ret = 0;
26 while(x > 0)
27 {
28 ret += tree[x];
29 x -= (x & -x);
30 }
31 return ret;
32}
33int cmp(const void *a,const void *b)
34{//先按e從大到小排序，如果相等的話，那么按s從小到大排序
35 這里主要是區(qū)間覆蓋的理解，這樣排序之后，后面的不會(huì)影響前面的
36 cow * c = (cow *)a;
37 cow * d = (cow *)b;
38 if(c->e == d->e)
39 {
40 return c->s - d->s;
41 }
42 if(d->e > c->e)
43 return 1;
44 else
45 return -1;
46}
47int cmp1(const void *a,const void *b)
48{//這個(gè)排序用來正確輸出，因?yàn)樵谇懊嫖覀優(yōu)榱擞脴錉顢?shù)組解，打亂了原來數(shù)組的順序，這里就再排過
49 cow * c = (cow *)a;
50 cow * d = (cow *)b;
51 if(c->no == d->no)
52 return 0;
53 if(c->no > d->no)
54 return 1;
55 else
56 return -1;
57}
58int main(void)
59{
60 freopen("2481.in","r",stdin);
61 freopen("2481.out","w",stdout);
62 int n;
63 while(EOF != scanf("%d",&n) && n)
64 {
65 for(int i = 0;i < n;i++)
66 {
67 scanf("%d%d",&cc[i].s,&cc[i].e);
68 ++cc[i].s;//都加1,是因?yàn)闀?huì)出現(xiàn)0,死循環(huán)
69 ++cc[i].e;
70 cc[i].no = i;//后來排序用
71 cc[i].ans = 0;
72 }
73 qsort(cc,n,sizeof(cc[0]),cmp);//排序，好讓我們可以用樹狀數(shù)組操作
74 memset(tree,0,sizeof(tree));
75 for(int i = 0;i < n;i++)
76 {
77
78 if(0 != i && cc[i].e == cc[i-1].e && cc[i].s == cc[i-1].s)//如果算過一次了
79 cc[i].ans = cc[i-1].ans;
80 else
81 cc[i].ans = read(cc[i].s);
82 /**//*
83 cc[i].ans = read(cc[i].s);
84 int j = i;
85 while(j > 0 && cc[j].s == cc[j-1].s && cc[j].e == cc[j-1].e)
86 j--;
87 cc[i].ans = cc[i].ans - (i-j);*/
88 update(cc[i].s,1);//更新樹狀數(shù)組
89 }
90 //在排序，好輸出正確的順序，前面我們排序時(shí)打亂了順序
91 qsort(cc,n,sizeof(cc[0]),cmp1);
92 printf("%d",cc[0].ans);
93 for(int i = 1;i < n;i++)
94 printf(" %d",cc[i].ans);
95 printf("\n");
96 }
97 return 0;
98}
99
如果是找那些cow比自己弱的話，那么就可以先對s排序，然后再對e排序，也就是說，怎么排序好讓后面的數(shù)據(jù)不對前面的產(chǎn)生影響。