更新时间:2022-08-12 16:48:12
思路; 树状数组
分析:
1 简单的区间更新,单点查询问题
代码:
/*********************************************** * By: chenguolin * * Date: 2013-08-20 * * Address: http://blog.csdn.net/chenguolinblog * ***********************************************/ #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> using namespace std; const int MAXN = 100010; int n; int treeNum[MAXN]; int lowbit(int x){ return x&(-x); } int getSum(int x){ int sum = 0; while(x){ sum += treeNum[x]; x -= lowbit(x); } return sum; } void add(int x , int val){ while(x < MAXN){ treeNum[x] += val; x += lowbit(x); } } void solve(){ int x , y , m; memset(treeNum , 0 , sizeof(treeNum)); m = n; while(m--){ scanf("%d%d" , &x , &y); add(x , 1); add(y+1 , -1); } printf("%d" , getSum(1)); for(int i = 2 ; i <= n ; i++) printf(" %d" , getSum(i)); puts(""); } int main(){ while(scanf("%d" , &n) && n) solve(); return 0; }