首页 > 代码库 > HDU1556 Color the ball
HDU1556 Color the ball
题解:
这里是IUPQ(段更新，点求和)裸题.
这里需要一点转换
对于原数组a.建立一个新数组d
d[i]=a[i]-a[i-1],特别的d[1]=a[1]
那么，对于求a[i]就转换为求d[1]+....d[i],也就是sum(d[i])
对于a[i]到a[j]的更新,转化为d[i]到d[n]的加和d[j+1]到d[n]的减,也就是add(d[i],1),add(d[j+1],-1)
参考链接http://wenku.baidu.com/link?url=NCPx7OOakQWJwkg5y69IoRHOFzuu4Fmtsbwcl6ucxUHOJboa2c-aM333eYPLEdeU4XsZ15FRAFxMKgnrwoKdBURR26aKQl9Sy2UMq8GVWyW
这个题说了前期全部为0，就直接保证了c数组就是为d数组的性质
代码:
#include<bits/stdc++.h>using namespace std;#define LL long long const int N=100010;const int M=32100;int c[N];int n,a,b;int lowbit(int x){return x&-x;}void add(int x,int v){ while(x<=n){ c[x]+=v; x+=lowbit(x); }}int sum(int x){ int cnt=0; while(x){ cnt+=c[x]; x-=lowbit(x); } return cnt;}int main(){ while(~scanf("%d",&n)&&n){ memset(c,0,sizeof(c)); for(int i=1;i<=n;i++){ scanf("%d%d",&a,&b); add(a,1); add(b+1,-1); } for(int i=1;i<=n;i++) printf("%d%c",sum(i),(i==n?‘\n‘:‘ ‘)); } return 0;}
HDU1556 Color the ball
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。