首页 > 代码库 > HDU 1556 - Color the ball
HDU 1556 - Color the ball
原理就是先利用两个数间的差分，因为把一段连续的数做标记相当于头差分+1，尾差分-1，然后做前缀和即可。
可以想到，相比segment tree这种个只适合于查询操作不多但修改操作很多的情况（如果保存前缀和修改又会降速），否则计算前缀和会很费时。
/*ID:esxgx1LANG:C++PROG:hdu1556*/#include <cstdio>#include <cstring>#include <iostream>#include <algorithm>using namespace std;#define NN 100000int a1[NN], a2[NN];int main(void){ #ifndef ONLINE_JUDGE freopen("in.txt", "r", stdin); #endif int N; while(scanf("%d", &N) > 0) { if (!N) break; for(int i=0; i<N; ++i) { int l, r; scanf("%d%d", &l, &r); a1[l-1]++, a1[r]--; } int sum = a1[0]; a1[0] = 0; for(int i=1; i<=N; ++i) { if (i > 1) putchar(‘ ‘); printf("%d", sum); sum += a1[i]; a1[i] = 0; } putchar(‘\n‘); } return 0;}
| 2014-07-26 15:58:25 | Accepted | 1556 | 578MS | 688K | 634 B | G++ |
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。