Cows
Time Limit: 3000MS Memory Limit: 65536K
Total Submissions: 6854 Accepted: 2211
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
題目大意：給你很多線段的頭S和尾E，問每一條線段中包含了多少個線段，（S和E相同不計在內）。這題先一看，完全不知道什麼方法，感覺非常的難辦。
但是！樹狀數組可以輕松解決這個問題！！！首先，將她們線段的s和e當做是(s,e)一個點，這樣子把所有點畫出來，你就會發現一個很神奇的現象，題目要求就會變成：問每一個點的左上角有多少個點？
！！！這樣不就和那題最簡單的stars一樣嗎？？？！！！
stars那題是問左下角有多少個點，而這題是問左上角，而且點不是有序排好的，所以有些不同，特殊處理一下就可以。
如果正常做，那個y是遞增的，所以sum和update那個方向就會相反了，這個其實沒什麼所謂，一樣的，排序的時候先y由大到小排，y相同時x由小到大排，這樣小小的處理，就變成stars那題了！！！
還有一點忘了，這題也是需要離散化的，離散化很重要很強大！！！
就這樣！走過路過不要錯過！！！
鏈接：http://poj.org/problem?id=2481
代碼：
Cpp代碼
#include <iostream>
#include <stdio.h>
#include <memory.h>
#include <algorithm>
using namespace std;
struct node
{
int x, y, id;
}a[100005];
int n, b[100005], val[100005];
bool cmp1(node a, node b) //排序很重要！！！
{
if(a.y != b.y) return a.y > b.y; //先由大到小排y
return a.x < b.x; //y相同，x由小到大排
}
int lowbit(int i)
{
return i&(-i);
}
void update(int i, int x)
{
while(i <= 100005)
{
b[i] += x;
i += lowbit(i);
}
}
int sum(int i)
{
int sum = 0;
while(i > 0)
{
sum += b[i];
i -= lowbit(i);
}
return sum;
}
int main()
{
int i;
while(scanf("%d", &n), n)
{
memset(b, 0, sizeof(b));
memset(val, 0, sizeof(val));
for(i = 0; i < n; i++)
{
scanf("%d %d", &a[i].x, &a[i].y);
a[i].id = i;
a[i].x++; a[i].y++; //x與y都有可能為0，所以都++
}
sort(a, a+n, cmp1);
val[a[0].id] = sum(a[0].x); //val[]代表各點的sum()
update(a[0].x, 1);
for(i = 1; i < n; i++)
{
if(a[i].x == a[i-1].x && a[i].y == a[i-1].y) //若兩區間相等
val[a[i].id] = val[a[i-1].id]; //該值等於上一個的值
else val[a[i].id] = sum(a[i].x);
update(a[i].x, 1); //更新該點x值
}
printf("%d", val[0]);
for(i = 1; i < n; i++)
{
printf(" %d", val[i]);
}
printf("\n");
}
return 0;
}
