裸线段树，不过不是很好写，需要注意的地方挺多的。
用sum[0],sum[1],sum[2]分别记录一次方和，平方和和立方和，更新的时候推一个增量公式：
一次方：sum[0]+=(r - l + 1)*c;
二次方：
∵(a+b)2=a2+2*a*b+b2;
∴ (xl+c)2 + (xl+1+c)2+……+(xr+c)2=xl2+xl+12+……+xr2+2*c*(xl+xl+1+……+xr)+(r-l+1)*c2;
∴ sum[1] = sum[1]+2*c*sum[0]+(r-l+1)*c2;(注：此处的sum[0]是未更新前的sum[0])
三次方：
∵(a+b)3=a3+2*a2*b+2*a*b2+b3;
∴ (xl+c)3 + (xl+1+c)3+……+(xr+c)3
=xl3+xl+13+……+xr3+2*c*(xl2+xl+12+……+xr2)+2*c*c*(xl+xl+1+……+xr)+(r-l+1)*c3;
∴sum[2] = sum[2]+2*c*sum[1]+2*c*c*sum[0]+(r-l+1)*c3;
(注：此处的sum[0]和sum[1]均是未更新前的sum[0]和sum[1])
然后就是懒惰更新的标记，之前我是用了一个oper标记操作，用了一个val标记操作的值，后来发现不行，因为操作是有先后顺序的，所以在更新的时候，如果需要标记当前节点，必须先把当前节点已有的标记PushDown下去。但是这样的话，每个子树都会遇到这个问题，标记就会一直传递下去，直到叶子节点。这样就失去了懒惰标记的意义。
因此我将标记改成了a*x+c的形式，记录a和c，加操作视为1*x+c，乘操作视为a*x+0，重置操作视为0*x+c。但是我每次更新的时候直接覆盖了之前的标记，显然这样是不行的，直接覆盖的话就丢失了之前的更新信息，但是把信息PushDown下去的话又会出现跟上面一样的问题。
怎么才能做到不丢失之前的信息，又不会把更新无限传递下去呢？
还是把信息记录成a*x+b的形式，更新直接在之前的标记上迭代。乘的话直接累乘到a上，加的话直接累加到b上。但是这样又会出现一个问题：先乘后加和先加后乘是不一样的。
这个就比较好处理了：我们每次优先处理乘操作。
更新加法：ax+b+c c直接累加到加法标记b上即可
更新乘法：c*(ax+b)=c*a*x+c*b c先累乘到乘法标记a上，再乘到加法标记b上
这样所有的问题就都解决了~
还有一点小地方：
1.long long int会超时，也可能是我代码比较挫，反正我用long long超时了
2.用int的话最好一乘一取模，不然很容易溢出
#include <cstdio> #include <cstring> #include <cstdlib> #include <algorithm> #define lson l, m, rt << 1 #define rson m + 1, r, rt << 1 | 1 #define UNLABLE 1 //未标记 using namespace std; const int MAXN = 100010; const int MOD = 10007; int N, Q; int sum[3][ MAXN << 2 ]; //sum0、1、2分别代表1、2、3次方 int flag[2][MAXN << 2]; //标记操作类型 flag[0]标记加法，flag[1]标记乘法，reset转变成*0+c void build( int l, int r, int rt ) { flag[0][rt] = 0; flag[1][rt] = 1; sum[0][rt] = sum[1][rt] = sum[2][rt] = 0; if ( l == r ) return; int m = ( l + r ) >> 1; build( lson ); build( rson ); return; } inline void Add( int l, int r, int rt, int x ) { if ( x == 0 ) return; int pre0 = sum[0][rt]%MOD; int pre1 = sum[1][rt]%MOD; sum[0][rt] += ((x%MOD) * (r - l + 1)%MOD)%MOD; sum[0][rt] %= MOD; sum[1][rt] += ((((2*x)%MOD)*pre0)%MOD + (((((r-l+1)%MOD)*x)%MOD)*x )%MOD)%MOD; sum[1][rt] %= MOD; sum[2][rt] += ((((3*x)%MOD)*pre1)%MOD + ( ((((3*x)%MOD)*x)%MOD)*pre0 )%MOD + (((((((r-l+1)%MOD)*x)%MOD)*x)%MOD)*x)%MOD)%MOD; sum[2][rt] %= MOD; return; } inline void Multi( int rt, int x ) { if ( x == 1 ) return; int pre = x; x %= MOD; sum[0][rt] *= x; sum[0][rt] %= MOD; x *= pre; x %= MOD; sum[1][rt] *= x; sum[1][rt] %= MOD; x *= pre; x %= MOD; sum[2][rt] *= x; sum[2][rt] %= MOD; return; } inline void PushUp( int rt ) { int lc = rt << 1; int rc = rt << 1 | 1; for ( int i = 0; i < 3; ++i ) { sum[i][rt] = (sum[i][lc]%MOD + sum[i][rc]%MOD)%MOD; } return; } inline void PushDown( int rt, int l, int r ) { int lc = rt << 1; int rc = rt << 1 | 1; int m = ( l + r ) >> 1; if ( flag[1][rt] != 1 ) { flag[1][lc] *= flag[1][rt], flag[1][lc] %= MOD; flag[1][rc] *= flag[1][rt], flag[1][rc] %= MOD; flag[0][lc] *= flag[1][rt], flag[0][lc] %= MOD; flag[0][rc] *= flag[1][rt], flag[0][rc] %= MOD; Multi(lc, flag[1][rt]), Multi(rc, flag[1][rt]); flag[1][rt] = 1; } if ( flag[0][rt] != 0 ) { flag[0][lc] += flag[0][rt]; flag[0][lc] %= MOD; flag[0][rc] += flag[0][rt]; flag[0][rc] %= MOD; Add( lson, flag[0][rt] ), Add( rson, flag[0][rt] ); flag[0][rt] = 0; } return; } void Update( int L, int R, int op, int v, int l, int r, int rt ) { //printf( "Uppre: [%d, %d]:\n", l, r ); //printf( "sum0=%d sum1=%d sum2=%d\n", sum[0][rt], sum[1][rt], sum[2][rt] ); //printf( "flag0=%d flag1=%d\n", flag[0][rt], flag[1][rt] ); if ( L <= l && r <= R ) { switch(op) { case 1: flag[0][rt] += v; flag[0][rt] %= MOD; Add(l, r, rt, v); break; case 2: flag[0][rt] *= v; flag[0][rt] %= MOD; flag[1][rt] *= v; flag[1][rt] %= MOD; Multi(rt, v); break; case 3: flag[0][rt] = v; flag[1][rt] = 0; Multi(rt, 0); Add(l, r, rt, v); break; } //printf( "Upafter: [%d, %d]: \n", l, r ); //printf( "sum0=%d sum1=%d sum2=%d\n", sum[0][rt], sum[1][rt], sum[2][rt] ); //printf( "flag0=%d flag1=%d\n", flag[0][rt], flag[1][rt] ); return; } PushDown(rt, l, r); int m = ( l + r ) >> 1; if ( L <= m ) Update( L, R, op, v, lson ); if ( R > m ) Update( L, R, op, v, rson ); PushUp( rt ); //printf( "Upafter: [%d, %d]: \n", l, r ); //printf( "sum0=%d sum1=%d sum2=%d\n", sum[0][rt], sum[1][rt], sum[2][rt] ); //printf( "flag0=%d flag1=%d\n", flag[0][rt], flag[1][rt] ); return; } int Query( int L, int R, int p, int l, int r, int rt ) { //printf( "pre: [%d, %d]: \n", l, r ); //printf( "sum0=%d sum1=%d sum2=%d\n", sum[0][rt], sum[1][rt], sum[2][rt] ); //printf( "flag0=%d flag1=%d\n", flag[0][rt], flag[1][rt] ); if ( L <= l && r <= R ) { return sum[p - 1][rt]; } PushDown(rt, l, r); int m = ( l + r ) >> 1; int res = 0; if ( L <= m ) res += Query( L, R, p, lson ); if ( R > m ) res += Query( L, R, p, rson ); res %= MOD; PushUp(rt); //printf( "after: [%d, %d]: \n", l, r ); //printf( "sum0=%d sum1=%d sum2=%d\n", sum[0][rt], sum[1][rt], sum[2][rt] ); //printf( "flag0=%d flag1=%d\n", flag[0][rt], flag[1][rt] ); return res; } int main() { //freopen( "in.txt", "r", stdin ); //freopen( "s.txt", "w", stdout ); while ( scanf( "%d%d", &N, &Q ), N || Q ) { build( 1, N, 1 ); while ( Q-- ) { int op, a, b, c; scanf( "%d%d%d%d", &op, &a, &b, &c ); if ( op == 4 ) printf("%d\n", Query( a, b, c, 1, N, 1 ) ); else Update( a, b, op, c, 1, N, 1 ); //puts(""); } } return 0; }
转载于:https://www.cnblogs.com/GBRgbr/p/3254442.html
相关资源：数据结构—成绩单生成器