Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

线段树区间更新朴素的AC代码

Posted by joseph_chiang at 2017-02-05 09:56:04 on Problem 3468
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
using namespace std;

#define LL long long
const int maxn = 100005;
 LL sum[ maxn*4 ];
 LL col[ maxn*4 ];


 void build( int root,int left,int right )
 {
     sum[ root ]=0;
     col[ root ]=0;
     if( left==right )
     {
     	scanf("%lld",&sum[root]);
        return;
     }
     int mid;
     mid=(left+right)/2;
     build( root*2,left,mid );
     build( root*2+1,mid+1,right );
     sum[root] = sum[root*2] + sum[root*2+1];
     return ;
 }

 void update(int a,int b,LL value,int root,int left,int right)
 {
     if(a<=left && b>=right)
     {
          col[root]+=value;
          sum[ root ]+=(right-left+1)*value;
          return;
     }
	 
	 int mid=(left+right)/2;
	 
     if( col[ root ] !=0)
     {
        col[root*2] += col[root];
        col[root*2+1] += col[root];
        sum[root*2] += col[root] * (mid-left+1);
        sum[root*2+1] += col[root] * (right-mid);
        col[root] = 0;
     }

     
     if(a<=mid)
          update(a,b,value,root*2,left,mid);
     if(b>mid)
          update(a,b,value,root*2+1,mid+1,right);

     sum[ root ]=sum[ root*2 ]+sum[ root*2+1 ];
     return;
 }

 LL query( int a,int b,int root,int left,int right )
{
     if( a==left && b==right )
     {
         return sum[ root ];
     }
     int mid;
     mid=(left+right)/2;
    if( col[ root ] !=0)
     {
        col[root*2] += col[root];
        col[root*2+1] += col[root];
        sum[root*2] += col[root] * (mid-left+1);
        sum[root*2+1] += col[root] * (right-mid);
        col[root] = 0;
     }
     int t1,t2;
     if( b<=mid ) 
     	return query( a,b,root*2,left,mid );
     else if( a>mid ) 
     	return query( a,b,root*2+1,mid+1,right );
     else return query( a,mid,root*2,left,mid )+query( mid+1,b,root*2+1,mid+1,right );
     
 }        

 int main()
{
     int n, q, t1, t2;
     long long t3;
     char a;
     scanf("%d%d",&n,&q);
     build(1, 1, n);
     while(q--)
     {

        scanf("%s", &a);
        if(a == 'C')
        {
            scanf("%d %d %lld", &t1, &t2, &t3);
            update(t1,t2,t3,1,1,n);
        }
        else if(a == 'Q')
        {
            scanf("%d %d", &t1,&t2);
            t3 = query(t1,t2,1,1,n);
            printf("%lld\n", t3);
        }
    }
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator