#1080 : 更為複雜的買賣房屋姿勢(線段樹區間add和區間set)

10000ms

1000ms

256MB

描述

小Hi和小Ho都是遊戲迷，“模拟都市”是他們非常喜歡的一個遊戲，在這個遊戲裡面他們可以化身上帝模式，買賣房産。

在這個遊戲裡，會不斷的發生如下兩種事件：一種是房屋自發的漲價或者降價，而另一種是政府有關部門針對房價的硬性調控。房價的變化自然影響到小Hi和小Ho的決策，是以他們希望能夠知道任意時刻某個街道中所有房屋的房價總和是多少——但是很不幸的，遊戲本身并不提供這樣的計算。不過這難不倒小Hi和小Ho，他們将這個問題抽象了一下，成為了這樣的問題：

小Hi和小Ho所關注的街道的長度為N米，從一端開始每隔1米就有一棟房屋，依次編号為0..N，在遊戲的最開始，每棟房屋都有一個初始價格，其中編号為i的房屋的初始價格為p_i，之後共計發生了M次事件，所有的事件都是對于編号連續的一些房屋發生的，其中第i次事件如果是房屋自發的漲價或者降價，則被描述為三元組(L_i, R_i, D_i)，表示編号在[L_i, R_i]範圍内的房屋的價格的增量（即正數為漲價，負數為降價）為D_i；如果是政府有關部門針對房價的硬性調控，則被描述為三元組(L_i, R_i, V_i)，表示編号在[L_i, R_i]範圍内的房屋的價格全部變為V_i。而小Hi和小Ho希望知道的是——每次事件發生之後，這個街道中所有房屋的房價總和是多少。

​​提示：這是練習向的一周~​​

輸入

每個測試點（輸入檔案）有且僅有一組測試資料。

每組測試資料的第1行為兩個整數N、M，分别表示街道的長度和總共發生的事件數。

每組測試資料的第2行為N+1個整數，其中第i個整數位p_i，表示編号為i的房屋的初始價格。

每組測試資料的第3-M+2行，按照發生的時間順序，每行描述一個事件，如果該行描述的事件為，“房屋自發的漲價或者降價”，則該行為4個整數0, L_i, R_i, D_i，意義如前文所述；如果該行描述的事件為“政府有關部門針對房價的硬性調控”，則該行為4個整數1, L_i, R_i, V_i，意義如前文所述。

對于100%的資料，滿足N<=10^5，1<=p_i, |D_i|, V_i<=10^4，0<=l_i<r_i<=n。<>

對于100%的資料，滿足在任意時刻，任何房屋的價格都處于[1, 10^4]内。

輸出

對于每組測試資料，輸出M行，其中第i行為一個整數Ans_i，表示第i次事件發生之後，這個街道中所有房屋的房價總和。

樣例輸入

10 6
3195 2202 4613 3744 2892 4858 619 5079 9478 7366 8942 
0 1 6 886
1 0 2 9710
1 0 10 7980
0 4 9 -7594
0 2 8 1581
0 4 4 -1010      

樣例輸出

58304
75652
87780
42216
53283
52273      

題目大概：

線段樹區間指派和區間加。

思路：

平常的模闆題隻是區間指派，或隻用區間加，這裡有兩種操作。

還要注意這兩種操作的關系，

當同一區間進行了add，再進行set時，add操作要清零。

                進行了set，再進行add時，set操作不用管。

當進行pushdown的時候如果進行了set操作，那麼孩子節點的add要清空，很好了解，畢竟重置了嗎，以前的都要清空。

代碼：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define lson 2*rt,l,m
#define rson 2*rt+1,m+1,r
using namespace std;
const int maxn=1100000;
int sum[maxn<<2];
int add[maxn<<2],set[maxn<<2];
void pushup(int rt)
{
    sum[rt]=sum[rt<<1]+sum[rt<<1|1];
}
void pushdown1(int rt,int n)
{
    if(set[rt])
    {
        set[rt<<1]=set[rt];
        set[rt<<1|1]=set[rt];
        add[rt<<1]=0;
        add[rt<<1|1]=0;
        sum[rt<<1]=set[rt]*(n-(n>>1));
        sum[rt<<1|1]=set[rt]*(n>>1);
        set[rt]=0;
    }
    if(add[rt])
    {
        add[rt<<1]+=add[rt];
        add[rt<<1|1]+=add[rt];
        sum[rt<<1]+=add[rt]*(n-(n>>1));
        sum[rt<<1|1]+=add[rt]*(n>>1);
        add[rt]=0;
    }
}

void build(int rt,int l,int r)
{
    add[rt]=set[rt]=0;
    if(l==r)
    {
        scanf("%d",&sum[rt]);
        return;
    }
    int m=(l+r)>>1;

    build(lson);
    build(rson);
    pushup(rt);

}
void updata1(int rt,int l,int r,int L,int R,int c)
{
    //cout<<11<<endl;
    //pushdown1(rt,r-l+1);
    if(L<=l&&r<=R)
    {
        add[rt]+=c;
        //set[rt]=0;
        sum[rt]+=c*(r-l+1);
        return;
    }
    pushdown1(rt,r-l+1);
    int m=(l+r)>>1;
    if(L<=m)updata1(lson,L,R,c);
    if(m<R)updata1(rson,L,R,c);
    pushup(rt);

}
void updata2(int rt,int l,int r,int L,int R,int c)
{
    //cout<<11<<endl;
    //pushdown1(rt,r-l+1);
    if(L<=l&&r<=R)
    {
        set[rt]=c;
        add[rt]=0;
        sum[rt]=c*(r-l+1);
        return;
    }
    pushdown1(rt,r-l+1);
    int m=(l+r)>>1;
    if(L<=m)updata2(lson,L,R,c);
    if(m<R)updata2(rson,L,R,c);
    pushup(rt);

}
int main()
{
    int n,m;
    scanf("%d%d",&n,&m);
    build(1,0,n);
    int q,l,r,v;
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d%d%d",&q,&l,&r,&v);
        if(q==0)
        {
            updata1(1,0,n,l,r,v);
            printf("%d\n",sum[1]);
        }
        else
        {
            updata2(1,0,n,l,r,v);
            printf("%d\n",sum[1]);
        }
    }

    return 0;
}