利用线段树，，用做模板！
#include<stdio.h> #include<string.h> #define MAXN 100005 struct ST //存储类型 { int l,r,num; //max表示当前节点的最大值 }st[4*MAXN]; int ans[MAXN]; void build(int ll,int rr,int n) //初始化建立线段树 { st[n].l=ll; //表示当前节点的最左端， st[n].r=rr; //表示当前节点的最右端， st[n].num=0; //当前节点的值，初始化全为零， if (ll==rr) return ; //如果遇到了根节点 int mid=(ll+rr)>>1; //将当前节点分开，mid为左孩子的右端点，为右孩子的左端点； build(ll,mid,2*n); //先遍历左边的树 build(mid+1,rr,2*n+1); //再遍历右边的树 } void insert(int ll,int rr,int n) // 更新 { if (st[n].l==ll&&st[n].r==rr) st[n].num++;//表示区间的值，即这个区间的值都加一，在后面加 else { int mid=(st[n].l+st[n].r)>>1; if (rr<=mid) //如果右端点比他的中间区分值mid还小，那么久插到左边， insert(ll,rr,2*n); else if (ll>=mid+1) //如果左端点比他的中间区分值mid还大，那么久插到右边， insert(ll,rr,2*n+1); else { //表示中间分开的 insert(ll,mid,2*n); insert(mid+1,rr,2*n+1); } } } void fin(int x) { for(int i=st[x].l;i<=st[x].r;i++) ans[i]+=st[x].num; //更新区间的值； if(st[x].l==st[x].r) return ; fin(2*x); //再查找左边的结点 fin(2*x+1); //右边的节点； } int main() { int n,m,a,b,i; while (scanf("%d",&n)!=EOF&&n) { build(1,n,1); memset(ans,0,sizeof(ans)); for (i=1;i<=n;++i) { scanf("%d %d",&a,&b); insert(a,b,1); } fin(1); printf("%d",ans[1]); for (i=2;i<=n;++i) { printf(" %d",ans[i]); } printf("\n"); } return 0; }
