考察树状数组的区间更新,单点求和,更新向下修改,查询时向上查询。
题意:每次更新(a,b)区间,更新一次加一,最后输出每个点的值。
#include <cstdio> #include <cstring> #include <string.h> #include <algorithm> using namespace std; int c[100005]; int n; int lowbit(int x) { return x&(-x); } void update(int i,int x) { while(i) { c[i]+=x; i-=lowbit(i); } } int sum(int i) { int s=0; while(i<=n) { s+=c[i]; i+=lowbit(i); } return s; } int main() { int a,b; while(scanf("%d",&n),n) { memset(c,0,sizeof(c)); for(int i=0;i<n;i++) { scanf("%d%d",&a,&b); update(b,1); update(a-1,-1); } for(int i=1;i<n;i++) { printf("%d ",sum(i)); } printf("%d\n",sum(n)); } }