首页 > 代码库 > POJ 2481 Cows（树状数组）

POJ 2481 Cows（树状数组）

2024-09-20 07:07:56   206人阅读

http://poj.org/problem?id=2481

题意：

有n头牛，每头牛有一个区间[S，E]，求每头牛比它区间大的牛的个数。

 

思路：

先对数据进行一下排序，先按右坐标按降序排列，那么接下来我们只需要比较左坐标的数值大小就可以了。

 1 #include<iostream> 2 #include<algorithm> 3 #include<cstring> 4 #include<cstdio> 5 #include<vector> 6 #include<queue> 7 #include<cmath> 8 #include<map> 9 #include<stack>10 using namespace std;11 12 const int maxn=1e5+5;13 14 int n;15 int c[maxn];16 int ans[maxn];17 int MAX;18 19 struct node20 {21     int l,r,id;22 }a[maxn];23 24 25 bool cmp(node a,node b)26 {27     return a.r>b.r||(a.r==b.r&&a.l<b.l);28 }29 30 int lowbit(int x)31 {32     return x&-x;33 }34 35 int sum(int x)36 {37     int ret=0;38     while(x>0)39     {40         ret+=c[x];41         x-=lowbit(x);42     }43     return ret;44 }45 46 void add(int x,int d)47 {48     while(x<=MAX+1)49     {50         c[x]+=d;51         x+=lowbit(x);52     }53 }54 55 int main()56 {57     //freopen("D:\\input.txt","r",stdin);58     while(scanf("%d",&n))59     {60         if(n==0)  break;61         memset(c,0,sizeof(c));62         memset(ans,0,sizeof(ans));63         MAX=0;64         for(int i=1;i<=n;i++)65         {66             scanf("%d%d",&a[i].l,&a[i].r);67             a[i].l++; a[i].r++;68             a[i].id=i;69             MAX=max(MAX,a[i].r);70         }71         sort(a+1,a+1+n,cmp);72         ans[a[1].id]=0;73         add(a[1].l,1);74         for(int i=2;i<=n;i++)75         {76             if(a[i].l==a[i-1].l && a[i].r==a[i-1].r)   ans[a[i].id]=ans[a[i-1].id];77             else78             {79                 ans[a[i].id]=sum(a[i].l);80             }81             add(a[i].l,1);82         }83         for(int i=1;i<=n;i++)84         {85             if(i!=1)   printf(" ");86             printf("%d",ans[i]);87         }88         printf("\n");89     }90     return 0;91 }

 

POJ 2481 Cows（树状数组）


联系
我们