[HDU - 4578] Transformation

线段树&多种毒瘤操作
柯朵莉树板题
重构了3次（我菜），旁边那位柯朵莉10minAC

HDU - 4578

题意简述

给一个长度为$n$的序列（初始都为0），要求支持区间加，区间乘，区间赋值。询问区间一次和、二次和、三次和。
$1\le n\le 100000$

题解

别慌，就是操作多了点，多打几个懒标记而已

define

设 $tagadd,tagmul$ 三种懒标记表区间加、乘。设 $sum1,sum2,sum3$ 表示区间一次和、二次和、三次和。

Q：区间赋值到哪去了？

A：这其实可以转化为区间乘0再加$v$，还能减小码量

modify

考虑如何更新节点，区间$[l,r]$，操作值为$v$，$len=r-l+1$
(刚开始一脸蒙，还来发现其实只要展开就行了)

加法

$$\begin{array}{l} sum1'=sum1+len\times v\\ sum2'=(a_l+v)^2+(a_{l+1}+v)^2+\cdots+(a_r+v)^2\\ \qquad \quad=(a_l^2+a_{l+1}^2+\cdots+a_r^2)+2v\times(a_l+a_{l+1}+\cdots+a_r)+len\times v^2\\ \qquad \quad=sum2+2v\times sum1+len\times v^2\\ sum3'=(a_l+v)^3+(a_{l+1}+v)^3+\cdots+(a_r+v)^3\\ \qquad \quad = (a_l^3+a_{l+1}^3+\cdots+a_r^3)+3v\times (a_l^2+a_{l+1}^2+\cdots+a_r^2)+3v^2\times(a_l+a_{l+1}+\cdots+a_r)+len\times v^3\\ \qquad \quad = sum3+3v\times sum2+3v^2\times sum1+len\times v^3 \end{array}$$

注意一下$sum$的更新顺序，先$sum3$开始，不然会把原来的覆盖掉。

乘法

$$\begin{array}{l} sum1'=v \times sum1\\ sum2'=(a_l\times v)^2+(a_{l+1}\times v)^2+\cdots+(a_r\times v)^2\\ \qquad\quad=v^2\times sum2\\ sum3'=(a_l\times v)^3+(a_{l+1}\times v)^3+\cdots+(a_r\times v)^3\\ \qquad\quad=v^3\times sum3\\ \end{array}$$

lazy tag

要注意懒标记的更新顺序：

加法与乘法：先乘再加，若乘在加后，将$tagadd\times val$，$tagmul\times val$

code

#include <cstdio>
#define ls (x<<1)
#define rs (x<<1|1)
using namespace std;
const int N = 100010;
const int mod = 10007;
int sum1[N<<2],sum2[N<<2],sum3[N<<3];
int add[N<<2],mul[N<<2];
int n,q;
void updata(int x,int op,int len,int t1) {
    int t2=(t1*t1)%mod;
    int t3=(t1*t2)%mod;
    if(op==1) { //add
        sum3[x]=(sum3[x]+(3*t1*sum2[x])%mod+(3*t2*sum1[x])%mod+(t3*len)%mod)%mod;
        sum2[x]=(sum2[x]+(2*t1*sum1[x])%mod+(len*t2)%mod)%mod;
        sum1[x]=(sum1[x]+(len*t1)%mod)%mod;
        add[x]=(add[x]+t1)%mod;
    }else if(op==2) { //mul
        sum3[x]=(sum3[x]*t3)%mod;
        sum2[x]=(sum2[x]*t2)%mod;
        sum1[x]=(sum1[x]*t1)%mod;
        add[x]=(add[x]*t1)%mod;
        mul[x]=(mul[x]*t1)%mod;
    }
}
void pushdown(int x,int l,int r) {
    int m=(l+r)>>1;
    if(mul[x]!=1) {
        updata(ls,2,m-l+1,mul[x]);
        updata(rs,2,r-m,mul[x]);
        mul[x]=1;
    }
    if(add[x]!=0) {
        updata(ls,1,m-l+1,add[x]);
        updata(rs,1,r-m,add[x]);
        add[x]=0;
    }
}
void pushup(int x) {
    sum1[x]=(sum1[ls]+sum1[rs])%mod;
    sum2[x]=(sum2[ls]+sum2[rs])%mod;
    sum3[x]=(sum3[ls]+sum3[rs])%mod;
}
void modify(int L,int R,int op,int v,int l=1,int r=n,int x=1) {
    if(L<=l&&r<=R) {
        updata(x,op,r-l+1,v);
        return ;
    }
    int m=(l+r)>>1;
    pushdown(x,l,r);
    if(L<=m) modify(L,R,op,v,l,m,ls);
    if(R>m) modify(L,R,op,v,m+1,r,rs);
    pushup(x);
}
int query(int L,int R,int k,int l=1,int r=n,int x=1) {
    if(L<=l&&r<=R) {
        if(k==1) return sum1[x];
        if(k==2) return sum2[x];
        if(k==3) return sum3[x];
    }
    int m=(l+r)>>1,ret=0;
    pushdown(x,l,r);
    if(L<=m) ret=query(L,R,k,l,m,ls);
    if(R>m) ret=(ret+query(L,R,k,m+1,r,rs))%mod;
    return ret;
}
void build(int l=1,int r=n,int x=1) {
    add[x]=0;mul[x]=1;
    if(l==r) {
        sum1[x]=sum2[x]=sum3[x]=0;
        return ;
    }
    int m=(l+r)>>1;
    build(l,m,ls);
    build(m+1,r,rs);
    pushup(x);
}
int main() {
    while(scanf("%d%d",&n,&q)!=EOF) {
        if(n==0&&q==0) break;
        build();
        while(q--) {
            int op,x,y,z;
            scanf("%d%d%d%d",&op,&x,&y,&z);
            if(op==4) {
                printf("%d\n",query(x,y,z));
            }
            if(op==1) {
                modify(x,y,1,z);
            }
            if(op==2) {
                modify(x,y,2,z);
            }
            if(op==3) {
                modify(x,y,2,0);
                modify(x,y,1,z);
            }
        }
    }
}