這題主要是要能很好的理解，就像2352一樣。那個題一看不是樹狀數組，但是，仔細一想，是樹狀數組。這題可以用那題的一些想法，對end排序(從大到小
，如果相等的話，那么然start從小到大排序，這樣的話，用樹狀數組進行操作時后面的不會影響前面的)這樣處理之后，這題基本思路是OK了，但是可能還







不行，因為你沒有處理s，e都相等的，也就是有可能多加了東西。那么我們就要減去這些多加的，或者直接等于前一個就行了，或者可以用注釋掉的方法，
具體代碼見下














見如下代碼

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是結果
11}cow;
12cow cc[100006];//輸入數據的數組
13int tree[100006];//樹狀數組
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  這里主要是區間覆蓋的理解，這樣排序之后，后面的不會影響前面的
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{//這個排序用來正確輸出，因為在前面我們為了用樹狀數組解，打亂了原來數組的順序，這里就再排過
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,是因為會出現0,死循環
69                     ++cc[i].e;
70                     cc[i].no = i;//后來排序用
71                     cc[i].ans = 0;
72                }
73              qsort(cc,n,sizeof(cc[0]),cmp);//排序，好讓我們可以用樹狀數組操作
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);//更新樹狀數組
89                }
90              //在排序，好輸出正確的順序，前面我們排序時打亂了順序
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排序，也就是說，怎么排序好讓后面的數據不對前面的產生影響。