首页 > 代码库 > soj 1088. Cows(树状数组)
soj 1088. Cows(树状数组)
可以用树状数组解决。
先按左端点递增排序，左端点相等的按右端点降序排列。
然后从左往有扫，更新答案同时更新sum数组。
对于一只Cow i,ans[i]为f(i)-g(i).
f(i)为满足p[j].s<=p[i].s&&p[j].e>=p[i].e（0<=j<n,j!=i）的Cow只数。
g(i)为满足p[j].s==p[i].s&&p[j].e==p[i].e（0<=j<n,j!=i）的Cow只数。
开个d数组维护一下,d[i]即为g(i)..
#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>#include <cmath>using namespace std;const int maxn=100005;int sum[maxn];int ans[maxn];int d[maxn];struct node{ int s,e,id; bool operator<(const node& x)const{ return s<x.s||(s==x.s&&e>x.e); }}p[maxn];int n;int getsum(int x){ int res=0; while(x)res+=sum[x],x-=x&-x; return res;}void update(int x){ while(x<=100004)sum[x]++,x+=x&-x;}int main(){// freopen("in","r",stdin); while(scanf("%d",&n)>0&&n){ for(int i=0;i<n;i++){ scanf("%d%d",&p[i].s,&p[i].e),p[i].id=i; ++p[i].s; ++p[i].e; } sort(p,p+n); memset(sum,0,sizeof sum); for(int i=0;i<n;i++){ ans[p[i].id]=getsum(100004)-getsum(p[i].e-1); d[i]=(p[i].s==p[i-1].s&&p[i].e==p[i-1].e)?d[i-1]+1:0; ans[p[i].id]-=d[i]; update(p[i].e); } for(int i=0;i<n;i++)printf("%d\n",ans[i]); } return 0;}
soj 1088. Cows(树状数组)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。