#include<stdio.h> #include<stdlib.h> #define N 110000 struct node { int x,y,yanchi,sum; }a[N*10]; void build(int t,int x,int y) { a[t].x=x; a[t].y=y; a[t].sum=0; a[t].yanchi=0; if(x==y)return ; int temp=t*2; int mid=(a[t].x+a[t].y)/2; build(temp,x,mid); build(temp+1,mid+1,y); return ; } void inset(int t,int x,int y) { if(a[t].x==x&&a[t].y==y) { a[t].yanchi+=1; return ; } int temp=t*2; int mid=(a[t].x+a[t].y)/2; if(x>mid) inset(temp+1,x,y); else if(y<=mid) inset(temp,x,y); else { inset(temp,x,mid); inset(temp+1,mid+1,y); } return ; } int qury(int t,int x) { if(a[t].x==a[t].y&&a[t].x==x) return a[t].sum=a[t].sum+a[t].yanchi; int temp=t*2; int mid=(a[t].x+a[t].y)/2; a[temp].yanchi+=a[t].yanchi; a[temp+1].yanchi+=a[t].yanchi; a[t].yanchi=0; if(x>mid) return qury(temp+1,x); else if(x<=mid) return qury(temp,x); } int main() { int n,i,start,end; while(scanf("%d",&n),n) { build(1,1,n); for(i=1;i<=n;i++) { scanf("%d%d",&start,&end); inset(1,start,end); } for(i=1;i<n;i++) printf("%d ",qury(1,i)); printf("%d ",qury(1,n)); } return 0; }
hdu 1556 线段树区间延迟更新好题
656mS