再次难受，这个题刚看线段树的时候写过一次，为了熟悉线段树看的题解，感觉挺简单就写上了，现在一看，发现事情并不简单，这个是区间更新，查询单点，第一次接触，发现，区间跟新只是更新区间内一个点，并不是区间内每个点都更新，而是在查询到区间内在某个点时，查到谁，谁就把这个点拿去用（暂时理解这么个意思，要是错了请指出，我是新手）。0
#include <iostream> #include <cstring> #include <cstdio> #include <algorithm> using namespace std; const int maxn=100000+10; int c[maxn]; int n,a,b; int lowbit(int x) { return x&-x; } void add(int i,int x) { while(i<=n) { c[i]+=x; i+=lowbit(i); } } int sum(int i) { int sum=0; while(i>0) { sum+=c[i]; i-=lowbit(i); } return sum; } int main() { while(~scanf("%d",&n)&&n) { memset(c,0,sizeof(c)); for(int i=0;i<n;i++) { scanf("%d%d",&a,&b); add(a,1); add(b+1,-1); } for(int i=1;i<n;i++) printf("%d ",sum(i)); printf("%d\n",sum(n)); } return 0; }
转载于:https://www.cnblogs.com/Wangwanxiang/p/7269616.html
