POJ 2481 Cows （树状+排序）

题意：
给定n个区间(s,e)，对于给出的每个区间，按顺序输出能够完全包含它的区间的个数，两个区间相等不算包含；

思路：
1、 先按 Cow 的s从小到大排序，再按e从大到小排序，假如 i < j, 观察 [si, ei] 和 [sj, ej]
si <= sj, 如果 ei >= ej, 则说明，区间 [si, ei] 比区间 [sj, ej] 大（当然排除 si == sj && ei == ej 也就是 区间 相等的情况）
2、 结构体排序之后，单独对 e 进行处理， 对于 点[sj, ej]， i < j, 找出 ei >= ej 的所有点。
这里使用的树状数组， small[j] 表示在j之前都比 ej 小的数， 则 在j之前都比 ej 大的数的个数 ：
j - 1 - small[j] //
3、 处理区间相等的情况，就把前面一个的结果赋给后面那个区间的结果
4、 输出答案时候，是按照输入的顺序输出的，因此 结构体 Cow.id 表示其输入的顺序号
5、poj 上，G++ 超时，C++ 通过

#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>
#define lowbit(i) ((i)&(-i)) // lowbit(x) 表示x的二进制对应的值
using namespace std;
const int MaxN = 100010;
int n;
int c[MaxN];	//树状数组的下标，从1开始的
int ans[MaxN];//getSum()函数, 返回前x个数的和
int getSum(int x)
{
    int sum = 0;for(int i = x; i > 0; i-= lowbit(i)){
    sum += c[i];}return sum;
}//update()函数，将第x个数加上v
void update(int x, int v)
{
    for(int i = x; i < MaxN; i += lowbit(i)){
    c[i] += v;}
}struct Cow
{
    int id;	//输入的id号int s;int e;bool operator<(const Cow & rhs) const{
    if(s == rhs.s){
    return e > rhs.e;}return s < rhs.s;}
}cows[MaxN];void solve()
{
    memset(c, 0, sizeof(c));memset(ans, 0, sizeof(ans));sort(cows + 1, cows + n + 1);update(cows[1].e, 1);int cnt = getSum(cows[1].e - 1);int id = cows[1].id;ans[id] = cnt;for(int i = 2; i <= n; ++i){
    update(cows[i].e, 1);if(cows[i].s == cows[i - 1].s && cows[i].e == cows[i - 1].e){
    id = cows[i].id;ans[id] = cnt;}else{
    cnt = i - 1 - getSum(cows[i].e - 1);	//get(cows[i].e - 1) 表示 cows[i].e 之前比 cows[i].e 小的数//i - 1 - getSum(cows[i].e - 1) 表示 cows[i].e 之前比 cows[i].e 大的数id = cows[i].id;						ans[id] = cnt;}}for(int i = 1; i <= n; ++i){
    printf("%d", ans[i]);if(i < n){
    printf(" ");}else{
    printf("\n");}}
}int main()
{
    while(scanf("%d", &n) != EOF && n){
    for(int i = 1; i <= n; ++i){
    scanf("%d%d", &cows[i].s, &cows[i].e);cows[i].id = i;}solve();}return 0;
}/* 3 1 2 0 3 3 4 0 *//* 1 0 0 */