今天聯(lián)系樹狀數(shù)組，但是我發(fā)現(xiàn)我真的很笨，做了好幾道了還是不熟。這個(gè)題和前邊的也沒什么分別，是說每個(gè)牛有一個(gè)區(qū)間[s,e],兩個(gè)牛[s1,e1], [s2,e2]，當(dāng)s1<=s2并且e1>=e2并且e1-s1>e2-s2時(shí)，我們說牛1比牛2強(qiáng)，給N個(gè)牛的區(qū)間，對(duì)于每個(gè)牛，輸出比這個(gè)牛強(qiáng)的牛的個(gè)數(shù)。
還是需要預(yù)處理，先對(duì)每個(gè)牛的e進(jìn)行降序排序，e相同時(shí)對(duì)s進(jìn)行升序排列，這樣循環(huán)時(shí)可以保證后邊的牛絕對(duì)不比前邊的牛強(qiáng)。在循環(huán)時(shí)，只需找出比當(dāng)前牛s小的牛的個(gè)數(shù)。如果遇到特殊情況，即兩個(gè)牛區(qū)間完全一樣，賦值就可以了。哎，加油吧~
Code：
1 #include<iostream>
2 #include<algorithm>
3 #include<map>
4 #define MAX 100002
5 using namespace std;
6 int c[MAX],ans[MAX],n,imax;
7 struct cow
8 {
9 int l,r,id;
10 }a[MAX];
11 bool cmp(cow a,cow b){
12 if(a.r==b.r) //如果兩個(gè)牛區(qū)間右邊界相同，按左邊界的升序排列
13 return a.l<b.l;
14 return a.r>b.r; //按右邊界的降序排列
15 }
16 int lowbit(int t){
17 return t&(t^(t-1));
18 }
19 int sum(int t){
20 int total=0;
21 while(t>0){
22 total+=c[t];
23 t-=lowbit(t);
24 }
25 return total;
26 }
27 void modify(int posi,int key){
28 while(posi<=imax){
29 c[posi]+=key;
30 posi+=lowbit(posi);
31 }
32 }
33 int main()
34 {
35 int i,j,k,n;
36 while(scanf("%d",&n),n){
37 memset(c,0,sizeof(c));
38 imax=0;
39 for(i=1;i<=n;i++){
40 scanf("%d%d",&a[i].l,&a[i].r);
41 a[i].id=i; //每個(gè)牛有個(gè)id防止排序完順序變亂
42 ++a[i].l; ++a[i].r;
43 if(imax<a[i].l) imax=a[i].l; //用imax表示右邊界最大值，即求和時(shí)的邊界
44 }
45 sort(a+1,a+n+1,cmp);
46 for(i=1;i<=n;++i){
47 if(i==1){
48 ans[a[i].id]=sum(a[i].l); //這里注意是ans[a[i].id]而不是ans[i]
49 modify(a[i].l,1);
50 }
51 else{
52 if(a[i].l==a[i-1].l&&a[i].r==a[i-1].r) //如果兩個(gè)牛完全相同，直接賦值
53 ans[a[i].id]=ans[a[i-1].id];
54 else
55 ans[a[i].id]=sum(a[i].l); //否則找出左邊界l比這個(gè)牛小的
56 modify(a[i].l,1);
57 }
58 }
59 for(i=1;i<n;++i)
60 printf("%d ",ans[i]);
61 printf("%d\n",ans[i]);
62 }
63 }
64