hihocoder 1078 线段树区域更新 博客分类： acm acm

#include<iostream>
#include<stdio.h>
#include<string.h>
using namespace std;
#define M 1000005
struct tree{
	int left,right,sum,lazy;
};
tree g[M];
int map[M];

void pushDown(int i)
{
	if(g[i].lazy)
	{
		g[2*i].lazy=1;
		g[2*i+1].lazy=1;
		g[i].lazy=0;
		
		g[2*i].sum=g[i].sum/(g[i].right-g[i].left+1)*(g[2*i].right-g[2*i].left+1);
		g[2*i+1].sum=g[i].sum/(g[i].right-g[i].left+1)*(g[2*i+1].right-g[2*i+1].left+1);
	}
}

void buildTree(int left,int right,int i)
{
	int mid;
	g[i].lazy=0;
	g[i].left=left;
	g[i].right=right;
	if(left==right)
	{
		g[i].sum=map[left];
		return ;
	}
	mid=(left+right)/2;
	buildTree(left,mid,2*i);
	buildTree(mid+1,right,2*i+1);
	g[i].sum=g[2*i].sum+g[2*i+1].sum;
}

void insert(int l,int r,int num,int i)
{
	if(g[i].lazy) pushDown(i);
	if(l==g[i].left && g[i].right==r)
	{
		g[i].sum=(g[i].right-g[i].left+1)*num;
		g[i].lazy=1;
		return ;
	}
	
	int mid=(g[i].left+g[i].right)/2;
	if(r<=mid)
		insert(l,r,num,2*i);
	else if(mid<l)
		insert(l,r,num,2*i+1);
	else
	{
		insert(l,mid,num,2*i);
		insert(mid+1,r,num,2*i+1);
	}
	g[i].sum=g[2*i].sum+g[2*i+1].sum;
	
}

int search(int l,int r,int k)    
{    
    int mid;   
	if(g[k].lazy) pushDown(k); 
	
    if(l==g[k].left && r==g[k].right)        
        return g[k].sum;  
		 
    mid=(g[k].left+g[k].right)/2;
  
    if(r<=mid)         
        search(l,r,2*k);    
    else if(l>mid)     
        search(l,r,2*k+1);  
    else      
        return search(l,mid,2*k)+search(mid+1,r,2*k+1);     
}    
 

int main()
{
	int i,m,n,f,l,r,price; 
	while(scanf("%d",&n)!=EOF)
	{
		for(i=1;i<=n;i++)
			scanf("%d",&map[i]);
		buildTree(1,n,1);
		
		scanf("%d",&m);
		while(m--)
		{
			scanf("%d",&f);
			if(f==1)
			{
				scanf("%d%d%d",&l,&r,&price);
				insert(l,r,price,1);
			}
			else
			{
				scanf("%d%d",&l,&r);
				printf("%d\n",search(l,r,1));
			}
		} 
	}
	return 0;
}

[/size]