hihoCoder 1078 : 线段树的区间修改

#1078 : 线段树的区间修改

10000ms

1000ms

256MB

描述

对于小Ho表现出的对线段树的理解，小Hi表示挺满意的，但是满意就够了么？于是小Hi将问题改了改，又出给了小Ho：

假设货架上从左到右摆放了N种商品，并且依次标号为1到N，其中标号为i的商品的价格为Pi。小Hi的每次操作分为两种可能，第一种是修改价格——小Hi给出一段区间[L, R]和一个新的价格NewP，所有标号在这段区间中的商品的价格都变成NewP。第二种操作是询问——小Hi给出一段区间[L, R]，而小Ho要做的便是计算出所有标号在这段区间中的商品的总价格，然后告诉小Hi。

那么这样的一个问题，小Ho该如何解决呢？

输入

每个测试点（输入文件）有且仅有一组测试数据。

每组测试数据的第1行为一个整数N，意义如前文所述。

每组测试数据的第2行为N个整数，分别描述每种商品的重量，其中第i个整数表示标号为i的商品的重量Pi。

每组测试数据的第3行为一个整数Q，表示小Hi进行的操作数。

每组测试数据的第N+4~N+Q+3行，每行分别描述一次操作，每行的开头均为一个属于0或1的数字，分别表示该行描述一个询问和一次商品的价格的更改两种情况。对于第N+i+3行，如果该行描述一个询问，则接下来为两个整数Li, Ri，表示小Hi询问的一个区间[Li, Ri]；如果该行描述一次商品的价格的更改，则接下来为三个整数Li，Ri，NewP，表示标号在区间[Li, Ri]的商品的价格全部修改为NewP。

对于100%的数据，满足N<=10^5，Q<=10^5, 1<=Li<=Ri<=N，1<=Pi<=N, 0<Pi, NewP<=10^4。

输出

对于每组测试数据，对于每个小Hi的询问，按照在输入中出现的顺序，各输出一行，表示查询的结果：标号在区间[Li, Ri]中的所有商品的价格之和。

样例输入

10 4733 6570 8363 7391 4511 1433 2281 187 5166 378 6 1 5 10 1577 1 1 7 3649 0 8 10 0 1 4 1 6 8 157 1 3 4 1557

样例输出

4731 14596

/*
对于线段树中的每一个非叶子节点[a,b]， 
它的左儿子表示的区间为[a,(a+b)/2]，右儿子表示的区间为[(a+b)/2+1,b]。 
*/ 
#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;
}