这题主要是要能很好的理解，就像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排序，也就是说，怎么排序好让后面的数据不对前面的产生影响。