poj2481——Cows
题意：给定区间，问这个区间被完全覆盖多少次。注意：如果有另一区间也是，他们不互相覆盖。思路：树状数组，E从小到大排序，如果E相等，则S从大到小排序。从后往前遍历，这样保证先遍历的一定不被后面的覆盖。
#include<algorithm>#include<iostream>#include<cstdio>#include<string>using namespace std;class node{public:int s,e;int id;};#define maxn 100002node p;int c,out;bool cmp(node &a,node &b){if(a.e <b.e )return true;if(a.e ==b.e &&a.s >b.s )return true;return false;}int lowbit(int x){return x&(x^(x-1));}int getsum(int t){int sum=0;while(t>0){sum+=c;t-=lowbit(t);}return sum;}void Modify(int t){while(t<maxn){c++;t+=lowbit(t);}}int main(){int n;while(scanf("%d",&n)&&n){int i;for(i=0;i<n;i++){scanf("%d%d",&p.s ,&p.e );p.s ++;p.e ++;p.id =i;}sort(p,p+n,cmp);memset(c,0,sizeof(c));memset(out,0,sizeof(out));for(i=n-1;i>=0;i--){if(i!=n-1&&p.s ==p.s &&p.e ==p.e ){out.id] =out.id ];}else {out.id ]= getsum(p.s );}Modify(p.s );}for(i=0;i<n;i++)printf("%d ",out);printf("\n");}return 0;}
页:
[1]