题目链接：http://hihocoder.com/problemset/problem/1080 ， 两种操作的线段树(区间更新)。
这道题前一段时间一直卡着我，当时也是基础不扎实做不出来，今天又想了想其实还是比较简单的，也只能怪自己太弱了。
这道题坑就坑在是有两个操作：set和add，所以lazy标记数组就需要两个，但是有一点要考虑的是一个区间上set与add的先后关系——如果对于一个区间set和add标记同时存在，那么应该如果处理：一种情况set在add之前，那么就按照正常顺序来就可以了；另一种情况add在set之前，那么这个add操作就取消，直接set操作就可以了。
所以更新线段树的一个区间的时候，如果是set操作，那么就把add的标记清理掉；如果是add操作，那么就正常进行。这样的话就保证两个标记同时出现的时候是先set再add的，这样的话就不会出错。
#include <iostream>
#include <cstdio>
#include <vector>
#include <cmath>
#include <string>
#include <string.h>
#include <algorithm>
using namespace std;
#define LL __int64
#define eps 1e-8
#define INF INT_MAX
#define lson l , m , rt << 1
#define rson m + 1 , r , rt << 1 | 1
const int MOD = ;
const int maxn = + ;
const int N = + ;
int sum[maxn << ] , col_add[maxn << ] , col_set[maxn << ];
void PushUp(int rt)
{
sum[rt] = sum[rt << ] + sum[rt << | ];
}
void build(int l , int r , int rt)
{
if(l == r) {
scanf("%d" , &sum[rt]);
return;
}
int m = (l + r) >> ;
build(lson);
build(rson);
PushUp(rt);
}
void PushDown(int rt , int len)
{ //在PushDown()函数里就是先执行set操作再执行add操作
if(col_set[rt]) {
col_set[rt << ] = col_set[rt << | ] = col_set[rt];
col_add[rt << ] = col_add[rt << | ] = ; //同样清除掉add的标记，当时少了这句Debug了好久
sum[rt << ] = (len - (len >> )) * col_set[rt];
sum[rt << | ] = (len >> ) * col_set[rt];
col_set[rt] = ;
}
if(col_add[rt] != ) {
col_add[rt << ] += col_add[rt];
col_add[rt << | ] += col_add[rt];
sum[rt << ] += (len - (len >> )) * col_add[rt];
sum[rt << | ] += (len >> ) * col_add[rt];
col_add[rt] = ;
}
}
void update(int L , int R , int x , int ch , int l , int r , int rt)
{
if(L <= l && R >= r) {
if(ch) {
sum[rt] = (r - l + ) * x;
col_set[rt] = x;
col_add[rt] = ; //清除掉add的标记
} else {
sum[rt] += (r - l + ) * x;
col_add[rt] += x;
}
return;
}
PushDown(rt , r - l + );
int m = (l + r) >> ;
if(L > m)
update(L , R , x , ch , rson);
else if(R <= m)
update(L , R , x , ch , lson);
else {
update(L , R , x , ch , lson);
update(L , R , x , ch , rson);
}
PushUp(rt);
}
int main()
{
int n , m , a , b , c , ch;
scanf("%d %d" , &n , &m);
build( , n + , );
while(m--) {
scanf("%d %d %d %d" , &ch , &a , &b , &c);
update(a + , b + , c , ch , , n + , );
printf("%d\n" , sum[]);
}
return ;
}