奶牛(树状数组)

题目翻译

农夫约翰的牛发现，他的田地里沿着山脊生长的三叶草（我们可以将其视为一维数字线）特别好。

农夫约翰有N头母牛（我们将母牛的编号从1到N）。每位农夫约翰的N头母牛都有她特别喜欢的三叶草范围（这些范围可能重叠）。范围由闭合间隔[S，E]定义。

但是有些母牛很强壮，有些却很弱。给定两个母牛：母牛i和母牛j，它们最喜欢的三叶草范围是[Si，Ei]和[Sj，Ej]。如果Si <= Sj并且Ej <= Ei并且Ei-Si> Ej-Sj，我们说母牛i比母牛j强。

对于每头母牛，有几头母牛比她强？农夫约翰需要您的帮助！

输入项

输入包含多个测试用例。

对于每个测试用例，第一行是整数N（1 <= N <= 10 ^ 5），它是母牛的数量。然后是N行，其第i行包含两个整数：S和E（0 <= S<=E<=1e5 )

输入的末尾包含单个0。

输出量

对于每个测试用例，输出一行包含n个以空格分隔的整数，其中第i个数字指定比母牛i强的母牛的数量。

Sample Input

1 2

0 3

3 4

Sample Output

1 0 0

Hint

Huge input and output,scanf and printf is recommended.

Input

The input contains multiple test cases.
For each test case, the first line is an integer N (1 <= N <= 10 ⁵), which is the number of cows. Then come N lines, the i-th of which contains two integers: S and E(0 <= S < E <= 10 ⁵) specifying the start end location respectively of a range preferred by some cow. Locations are given as distance from the start of the ridge.

The end of the input contains a single 0.

Output

For each test case, output one line containing n space-separated integers, the i-th of which specifying the number of cows that are stronger than cow _i.

Sample Input

Sample Output

1 0 0

Hint

Huge input and output,scanf and printf is recommended.

Sponsor

首先，对牛排序，按e[i]从大到小，e[i]相同则s[i]从小到大。则扫描到某头牛i的时候，比它强壮的牛都在它的前面(因为s[i]==s[j]&&e[i]==e[j]不算比它强壮)而且一定有它前面的牛e值大等于e[i]，所以，只需要求s[i]小等于它的有多少个(如果牛i与牛i-1属性相同，则所求数量也相同，不用再计算)。

　　　考虑到s[i] <= 10^5，所以直接用num[10^5]记录即可，然后求前缀和。由于求前缀和的同时，也需要动态的修改，所以用树状数组。

#include<iostream>
#include<algorithm>
#include<stdio.h>
#include<cstring> 
using namespace std;
const int maxn=1e5+100;
struct node{
    int s;
    int e;
    int id;
}a[maxn];
int c[maxn];
int p[maxn];
bool cmp(node x,node y){
    if(x.e==y.e){
        return x.s<y.s;
    }
    return x.e>y.e;
} 
int lowbit(int x){
    return x&-x;
}
void add(int x,int k){
    for(int i=x;i<maxn;i+=lowbit(i)){
        c[i]+=k;
    }
}
int getsum(int x){
    int ans=0;
    for(int i=x;i>0;i-=lowbit(i)){
        ans+=c[i];
    } 
    return ans;
}
int main(){
    int n;
    while(~scanf("%d",&n)){
        memset(c,0,sizeof(c));
        if(n==0){
            break;
        }
        for(int i=1;i<=n;i++){
            scanf("%d%d",&a[i].s,&a[i].e);
            a[i].s++;
            a[i].e++;
            a[i].id=i;
        }
    
        sort(a+1,a+n+1,cmp);
        for(int i=1;i<=n;i++){
            if(i>1&&a[i].s==a[i-1].s&&a[i].e==a[i-1].e){
                p[a[i].id]=p[a[i-1].id];
            }
            else{
                int ans=getsum(a[i].s);
                p[a[i].id]=ans;
            }
            add(a[i].s,1);
        } 
        for(int i=1;i<n;i++){
            printf("%d ",p[i]);
        }
        printf("%d
",p[n]);
    }
}