hdu1556

Color the ball

Time Limit: 9000/3000 MS (Java/Others)????Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 9143????Accepted Submission(s): 4677 Problem Description N個氣球排成一排，從左到右依次編號為1,2,3....N.每次給定2個整數a b(a <= b),lele便為騎上他的“小飛鴿"牌電動車從氣球a開始到氣球b依次給每個氣球涂一次顏色。但是N次以后lele已經忘記了第I個氣球已經涂過幾次顏色了，你能幫他算出每個氣球被涂過幾次顏色嗎？ Input 每個測試實例第一行為一個整數N,(N <= 100000).接下來的N行，每行包括2個整數a b(1 <= a <= b <= N)。
當N = 0，輸入結束。 Output 每個測試實例輸出一行，包括N個整數，第I個數代表第I個氣球總共被涂色的次數。 Sample Input 3 1 1 2 2 3 3 3 1 1 1 2 1 3 0 Sample Output 1 1 1 3 2 1

<pre name="code" class="cpp">#include"stdio.h" #include"string.h" #include"iostream" #include"map" #include"string" #include"queue" #include"stdlib.h" #include"math.h" #define M 100009 #define eps 1e-8 #define inf 1000000000 #define mod 1000000000 #define INF 1000000000 using namespace std; struct st {int l,r,sum,add,mark; }a[M*4]; int ans; void make(int l,int r,int k) {a[k].l=l;a[k].r=r;a[k].mark=0;a[k].add=0;if(l==r){a[k].sum=0;return ;}int mid=(l+r)/2;make(l,mid,k*2);make(mid+1,r,k*2+1);a[k].sum=a[k*2].sum+a[k*2+1].sum; } void updata(int l,int r,int p,int k) {if(a[k].l==l&&a[k].r==r){a[k].sum+=(r-l+1);a[k].add+=p;//當多次剛好更新還區間的時候，只更新到該區間，所以要連加a[k].mark=1;return;}if(a[k].mark){a[k*2].sum+=(a[k*2].r-a[k*2].l+1)*a[k].add;a[k*2].add+=a[k].add;a[k*2].mark=1;a[k*2+1].sum+=(a[k*2+1].r-a[k*2+1].l+1)*a[k].add;a[k*2+1].add+=a[k].add;a[k*2+1].mark=1;a[k].mark=0;a[k].add=0;//當向下延伸的時候，需要把當前區間賦為0，}int mid=(a[k].l+a[k].r)/2;if(r<=mid)updata(l,r,p,k*2);else if(l>mid)updata(l,r,p,k*2+1);else{updata(l,mid,p,k*2);updata(mid+1,r,p,k*2+1);}a[k].sum=a[k*2].sum+a[k*2+1].sum; } void query(int p,int k) {if(a[k].l==p&&a[k].r==p){ans+=a[k].sum;return;}if(a[k].mark){a[k*2].sum+=(a[k*2].r-a[k*2].l+1)*a[k].add;a[k*2].add+=a[k].add;a[k*2].mark=1;a[k*2+1].sum+=(a[k*2+1].r-a[k*2+1].l+1)*a[k].add;a[k*2+1].add+=a[k].add;a[k*2+1].mark=1;a[k].mark=0;a[k].add=0;}int mid=(a[k].l+a[k].r)/2;if(p<=mid)query(p,k*2);elsequery(p,k*2+1);a[k].sum=a[k*2].sum+a[k*2+1].sum; } int main() {int n,i;while(scanf("%d",&n),n){make(1,n,1);int x,y;for(i=1;i<=n;i++){scanf("%d%d",&x,&y);updata(x,y,1,1);}for(i=1;i<=n;i++){ans=0;query(i,1);if(i==1)printf("%d",ans);elseprintf(" %d",ans);}printf("\n");}return 0; }

轉載于:https://www.cnblogs.com/mypsq/p/4348194.html

總結

以上是生活随笔為你收集整理的线段树（成段更新，区间求和lazy操作 ）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。