# [树状数组] 树状数组基础练习题题解（二）

POJ 2481 – Cows

Time Limit: 3000MS
Memory Limit: 65536K

## Description

Farmer John’s cows have discovered that the clover growing along the ridge of the hill (which we can think of as a one-dimensional number line) in his field is particularly good.

Farmer John has N cows (we number the cows from 1 to N). Each of Farmer John’s N cows has a range of clover that she particularly likes (these ranges might overlap). The ranges are defined by a closed interval [S,E].

But some cows are strong and some are weak. Given two cows: cowi and cowj, their favourite clover range is [Si, Ei] and [Sj, Ej]. If Si <= Sj and Ej <= Ei and Ei – Si > Ej – Sj, we say that cowi is stronger than cowj.

For each cow, how many cows are stronger than her? Farmer John needs your help!

## Input

The input contains multiple test cases.
For each test case, the first line is an integer N (1 <= N <= 105), which is the number of cows. Then come N lines, the i-th of which contains two integers: S and E(0 <= S < E <= 105) 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 cowi.

## Sample Input

3
1 2
0 3
3 4
0


## Sample Output

1 0 0


## Hint

Huge input and output,scanf and printf is recommended.

## Source

POJ Contest,Author:Mathematica@ZSU

#include
#include
#include
#include
#include
#include
#define LL long long

using namespace std;

int x = 0;
int p = 1;
char ch = getchar();

while(ch < '0' || ch > '9'){
if(ch == '-')
p = -1;
ch = getchar();
}

while('0' <= ch && ch <= '9'){
x = x*10 + ch - '0';
ch = getchar();
}

return x*p;
}

const int MAXN = 100000;

struct Cow{
int start;
int end;
int id;
};

Cow cow[MAXN+10];

int tree[MAXN + 10];
int ans[MAXN + 10];
int n;

inline bool cmp(Cow x,Cow y){
if(x.end == y.end)
return x.start < y.start;
return x.end > y.end;
}

inline int lowbit(int x){
return x & (-x);
}

inline void update(int i,int x){
while(i<=MAXN){
tree[i] += x;
i += lowbit(i);
}
}

inline int sum(int i){
int ans = 0;

while(i){
ans += tree[i];
i -= lowbit(i);
}

return ans;
}

int main(){

while(scanf("%d",&n) && n){
memset(cow,0,sizeof(cow));
memset(ans,0,sizeof(ans));
memset(tree,0,sizeof(tree));

for(int i=0;i
 
 
 文章导航 [树状数组] 树状数组基础练习题题解（一）[树状数组] 树状数组基础练习题题解（三） (adsbygoogle =window.adsbygoogle ||[]).push({});