POJ 2481（Cows）树状数组

题目分析：题意大概是这样的，给一些组数据，每i组有两个数S(i)_和 E(i)，对于每组，求出有多少组满足 S(t) <= S(i), E(t) >= E(i), E(t)-S(t) > E(i)-S(i);

首先将S[i]降序排序，如果相等则按E[i]的升序。除去特殊情况，所有都满足公式！如果遇到完全重合的数据，则单独考虑，也就是不需求和计算，只需把前面的值赋值给他，

#include<iostream>
#include<stdio.h>
#include<algorithm>
#include<string.h>
#define lowbit(x) (x&(-x))
#define N 100010  
using namespace std;

int c[100002],sim[100002];

struct node{
	int s;
	int order;
	int e;
}s[100002];

bool cmp(struct node a,struct node b){
	if(a.e!=b.e)
		return a.e>b.e;
	else
		return a.s<b.s;	
}

int getsum(int x){
	int sum=0;
	while(x>0){
		sum+=c[x];
		x-=lowbit(x);
	}
	return sum;
}

int modify(int pos,int num){
	while(pos<N){
		c[pos]+=num;
		pos+=lowbit(pos);
	}
	return 0;
}

int main(){
	int cas,i,st,et;
	while(~scanf("%d",&cas)&&cas){
		memset(c,0,sizeof(c));
		for(i=1;i<=cas;i++){
			scanf("%d%d",&s[i].s,&s[i].e); 
			s[i].s++;	s[i].e++;
			s[i].order=i;	
		}
		sort(s+1,s+1+cas,cmp);
		int ans=getsum(s[1].s);
		sim[s[1].order]=ans;
		modify(s[1].s,1);
		st=s[1].s;	et=s[1].e;
		for(i=2;i<=cas;i++){
			if(s[i].s==st&&s[i].e==et){
				sim[s[i].order]=sim[s[i-1].order];
                             //重复的就不需要求和，直接把前面的给他
				modify(s[i].s,1);
                              //但是还得修改哦{^_^}
				continue;			
			}
			st=s[i].s;	et=s[i].e;
			int ans=getsum(s[i].s);
			sim[s[i].order]=ans;
			modify(s[i].s,1);
		}
		for(i=1; i<=cas; i++)  {  
                	if( i != 1 )  
                 		printf(" ");  
             		printf("%d",sim[i]);  
         	}	
		 printf("\n");  
	}
	return 0;
	
}