给你一个序列：a1 a2 a3 : : : an，有m 个操作，操作如下：
modify l r x 将区间[l; r] 中的每个数修改为x change l r x 将区间[l; r] 中的每个数加上x query l r 询问区间[l; r] 中的和
要维护几个东西： • sum 表示区间的和 • type 表示现在的标记类型（可以是没有标记，可以是增量标记，可以是 赋值标记） • delta 如果是增量标记，那么这个里面存的增量 • value 如果是赋值标记，那么这里面就存的是那个值 然后就秩序要讨论一下发现： • 空标记+ 赋值操作= 赋值标记 • 空标记+ 增量操作= 增量标记 • 增量标记+ 赋值操作= 赋值标记 • 增量标记+ 增量操作= 增量标记 • 赋值标记+ 增量操作= 赋值标记 • 赋值标记+ 赋值操作= 赋值标记 因为它们之间能和谐共处（如果A 标记遇见B 操作无法转化为一种现有的标 记，那么他们就不能同时用线段树实现），所以就能完成两种操作同时进行。具 体看代码是怎样合并的。
#include "ctime" #include "cctype" #include "cstdio" #include "cstdlib" #define rep(i, m, n) for(register int i = (m); i <= (n); ++i) template <class T> inline bool readIn(T& x) { char ch; int opt = 1; while(!isdigit((ch = getchar())) && ch != '-' && ch != -1); if(ch == -1) return false; if(ch == '-') { ch = getchar(); opt = -1; } for(x = ch - '0'; isdigit((ch = getchar())); x = (x << 1) + (x << 3) + ch - '0'); ungetc(ch, stdin); x *= opt; return true; } template <class T> inline void write(T x) { if (x > 9) write(x / 10); putchar(x % 10 + 48); } template <class T> inline bool writeIn(T x) { if (x < 0) { putchar('-'); x = -x; } write(x); return true; } typedef long long LL; const int MAXN = 100005; struct Node; void modify( Node *nd, int lf, int rg, int L, int R, LL value ); void change( Node *nd, int lf, int rg, int L, int R, LL delta ); struct Node { LL sum; int type; LL delta, value; Node *ls, *rs; void update() { sum = ls -> sum + rs -> sum; } void pushdown( int lf, int rg ) { if( type == 0 ) return; int mid = (lf + rg) >> 1; if( type == 1 ) { change( ls, lf, mid, lf, mid, delta ); change( rs, mid+1, rg, mid+1, rg, delta ); type = 0; } else { modify( ls, lf, mid, lf, mid, value ); modify( rs, mid+1, rg, mid+1, rg, value ); type = 0; } } }pool[MAXN << 1], *tail = pool, *root; int n, m, l, r, x, a[MAXN]; Node *build( int lf, int rg ) { Node *nd = ++tail; if( lf == rg ) { nd -> sum = a[lf]; nd -> type = 0; } else { int mid = (lf + rg) >> 1; nd -> ls = build( lf, mid ); nd -> rs = build( mid+1, rg ); nd -> type = 0; nd -> update(); } return nd; } void modify( Node *nd, int lf, int rg, int L, int R, LL value ) { if( L <= lf && rg <= R ) { nd -> sum = (LL)(rg - lf + 1) * value; nd -> type = 2; nd -> value = value; return; } int mid = (lf + rg) >> 1; nd -> pushdown(lf,rg); if( L <= mid ) modify( nd -> ls, lf, mid, L, R, value ); if( R > mid ) modify( nd -> rs, mid+1, rg, L, R, value ); nd -> update(); } void change( Node *nd, int lf, int rg, int L, int R, LL delta ) { if( L <= lf && rg <= R ) { nd -> sum += (LL)(rg - lf + 1) * delta; if( nd -> type == 0 ) { nd -> type = 1; nd -> delta = delta; } else if( nd -> type == 1 ) nd -> delta += delta; else if( nd -> type == 2 ) nd -> value += delta; return; } int mid = (lf + rg) >> 1; nd -> pushdown(lf,rg); if( L <= mid ) change( nd -> ls, lf, mid, L, R, delta ); if( R > mid ) change( nd -> rs, mid+1, rg, L, R, delta ); nd -> update(); } LL query( Node *nd, int lf, int rg, int L, int R ) { if( L <= lf && rg <= R ) return nd -> sum; int mid = (lf + rg) >> 1; nd -> pushdown(lf, rg); LL rt = 0; if( L <= mid ) rt += query( nd -> ls, lf, mid, L, R ); if( R > mid ) rt += query( nd -> rs, mid+1, rg, L, R ); return rt; } int main() { freopen("setmod.in", "r", stdin); freopen("setmod.out", "w", stdout); readIn(n);readIn(m); rep(i, 1, n) readIn(a[i]); root = build(1, n); while( m-- ) { static char s; while((s = (char) getchar()) == ' ' || s == '\n'); if(s == 'q') { readIn(l), readIn(r); writeIn(query(root, 1, n, l, r)); putchar(10); } else { readIn(l);readIn(r);readIn(x); if(s == 'c') change(root, 1, n, l, r, x); else modify(root, 1, n, l, r, x); } } }