pku2726source.cpp

PKU 2726 代码 树状数组的简单应用例子

//PKU2726Source 

#include<iostream>
#include<fstream>

#include<algorithm>

using namespace std;

struct hotel{
	long sea;
	long cheap;
	long seaindex;
};
long in[50000];
hotel hotels[10010];
long n;
bool cmp(hotel a,hotel b)
{
	if(a.cheap==b.cheap){
		return a.sea<b.sea;
	}
	return a.cheap<b.cheap;
}
bool cmp2(hotel a,hotel b)
{
	if(a.sea==b.sea){
		return a.cheap>b.cheap;
	}
	return a.sea>b.sea;
}

int Lowbit(int t) 
{ 
    return t & ( t ^ ( t - 1 ) ); 
} 

int Sum(int end) 
{ 
    int sum = 0; 
    while(end > 0) 
    { 
        sum += in[end]; 
        end -= Lowbit(end); 
    } 
    return sum; 
} 

void plus(int pos , int num) 
{ 
    while(pos <= n) 
    { 
          in[pos] += num; 
          pos += Lowbit(pos); 
    } 
} 
int main()
{
//	freopen("input.in","r",stdin);
	long i,j;
	while(cin>>n&&n!=0){
		memset(in,0,sizeof(in));
		for(i=1;i<=n;i++){	
			scanf("%ld%ld",&hotels[i].sea,&hotels[i].cheap);
		}
		sort(hotels+1,hotels+n+1,cmp2);
		for(i=1;i<=n;i++)
			hotels[i].seaindex=i;

		sort(hotels+1,hotels+n+1,cmp);
		long result=0;
		for(i=1;i<=n;i++){
			long sum;
			sum=Sum(hotels[i].seaindex-1);
			plus(hotels[i].seaindex,1);
			if(sum==i-1){
				result++;
			}
		}
		cout<<result<<endl;
	}
	return 0;
}