看了这篇文章复习了下数状数组：http://blog.csdn.net/clx55555/article/details/52261538
这个题的思路是在起始位置加1，结束位置的下一个减1，这样从1~n的和就是n被染色的次数。
数状数组的思想挺有意思的，不得不佩服想出这个思想的人
#include <stdio.h> #include <iostream> #include <string.h> #include <algorithm> using namespace std; const int maxn=100009; int n; int a[maxn]; int low_bit(int x) { return x&(-x); } void add(int x,int val) { for(int i=x; i<=n; i+=low_bit(i)) a[i]+=val; } int sum(int x) { int ans=0; for(int i=x; i>=1; i-=low_bit(i)) ans+=a[i]; return ans; } int main() { while(~scanf("%d",&n)&&n) { memset(a,0,sizeof(a)); int x,y; for(int i=1; i<=n; i++) { scanf("%d%d",&x,&y); add(x,1); add(y+1,-1); } for(int i=1; i<n; i++) printf("%d ",sum(i)); printf("%d\n",sum(n)); } return 0; }