题目链接：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 = 10000007;
const int maxn = 100000 + 5;
const int N = 100000 + 5;
int sum[maxn << 2] , col_add[maxn << 2] , col_set[maxn << 2];
void PushUp(int rt)
{
sum[rt] = sum[rt << 1] + sum[rt << 1 | 1];
}
void build(int l , int r , int rt)
{
if(l == r) {
scanf("%d" , &sum[rt]);
return;
}
int m = (l + r) >> 1;
build(lson);
build(rson);
PushUp(rt);
}
void PushDown(int rt , int len)
{ //在PushDown()函数里就是先执行set操作再执行add操作
if(col_set[rt]) {
col_set[rt << 1] = col_set[rt << 1 | 1] = col_set[rt];
col_add[rt << 1] = col_add[rt << 1 | 1] = 0; //同样清除掉add的标记，当时少了这句Debug了好久
sum[rt << 1] = (len - (len >> 1)) * col_set[rt];
sum[rt << 1 | 1] = (len >> 1) * col_set[rt];
col_set[rt] = 0;
}
if(col_add[rt] != 0) {
col_add[rt << 1] += col_add[rt];
col_add[rt << 1 | 1] += col_add[rt];
sum[rt << 1] += (len - (len >> 1)) * col_add[rt];
sum[rt << 1 | 1] += (len >> 1) * col_add[rt];
col_add[rt] = 0;
}
}
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 + 1) * x;
col_set[rt] = x;
col_add[rt] = 0; //清除掉add的标记
} else {
sum[rt] += (r - l + 1) * x;
col_add[rt] += x;
}
return;
}
PushDown(rt , r - l + 1);
int m = (l + r) >> 1;
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(1 , n + 1 , 1);
while(m--) {
scanf("%d %d %d %d" , &ch , &a , &b , &c);
update(a + 1 , b + 1 , c , ch , 1 , n + 1 , 1);
printf("%d
" , sum[1]);
}
return 0;
}