HDU4578-代码一点都不长的线段树

（有任何问题欢迎留言或私聊 && 欢迎交流讨论哦

题意：传送门

原题目描述在最下面。

4种操作，1：区间加法，2：区间乘法，3：区间的所有数都变成一个数，4：访问区间每个数的p次方和(1 <= p <= 3)。

思路：

三个lazy标记：lazy1表示区间加上的数的延迟，lazy2表示区间乘上的数的延迟，lazy3表示区间变成的那个数字。初始化lazy1 = lazy3 = 0, lazy2 = 1.

如果进行3号操作，则将lazy1和lazy2全部恢复初始值。

对于1，2号操作，假设原数是x，乘上a，加上b。则 $a \Rightarrow a \times x + b$ 。

$$sum1 = \sum x \Rightarrow \sum (a\times x + b) = sum1 \times a + b \times length$$

$$sum2 = \sum x^2 \Rightarrow \sum (a\times x + b)^2 \Rightarrow \sum (a^2\times x2+2\times a\times b\times x)=sum2\times a2 \times length+2\times a\times b\times sum1

\[&emsp;$$sum3 = \sum x^3 \Rightarrow \sum (a\times x + b)^3 \Rightarrow \sum (a^3\times x^3 + b^3 + 3\times a^2\times x^2\times b+3\times a \times x\times b^2)= sum3 \times a^3 + b^3 \times length + 3\times sum2\times a^2 \times b+ 3\times sum1\times a\times b^2
\]

注意了，再进行更新sum操作时，要先更新sum3再更新sum2最后更新sum1。比如sum3式子中的sum2的含义是原始数列的sum2，不是更新后的sum2。

然后就是对于push_down中的lazy1和lazy2的处理。

$lazy1 \Rightarrow lazy1\times a + b$

$lazy2 \Rightarrow lazy2\times a $

(因为update哪里忘了写return;，导致debug一天)

AC代码：

#include <iostream>

#include <cstdio>

#include <cstring>

#include <cstdlib>

#include <cmath>

#include <vector>

#include <queue>

#include <algorithm>

#include <set>

#include<assert.h>

#define lson rt<<1

#define rson rt<<1|1

#define lowbit(x) (x)&(-(x))

using namespace std;

typedef long long LL;

const int INF = 0x3f3f3f3f;

const int N = (int)1e5+7;

const int mod = 10007;

int n, q;

int ar[N];

struct lp{

  int l,r;

  LL sum1,sum2,sum3,d;

  LL lazy1,lazy2,lazy3;

}cw[N<<2];

//pushdown先乘除后加减

//加法 lazy1 lazy2 乘法

void push_up(int rt){

  cw[rt].sum1 = (cw[lson].sum1+cw[rson].sum1)%mod;

  cw[rt].sum2 = (cw[lson].sum2+cw[rson].sum2)%mod;

  cw[rt].sum3 = (cw[lson].sum3+cw[rson].sum3)%mod;

}

void build(int l,int r,int rt){

  int m=(l+r)>>1;

  cw[rt].l=l;cw[rt].r=r;

  cw[rt].d=r-l+1;

  cw[rt].sum1 = cw[rt].sum2 = cw[rt].sum3=0;

  cw[rt].lazy1 = cw[rt].lazy3 = 0;

  cw[rt].lazy2 = 1;

  if(l==r){return;}

  build(l,m,lson); build(m+1,r,rson);

  push_up(rt);

}

//pushdown先乘除后加减

void push_down(int rt){

  if(cw[rt].lazy3){

    LL tmp = cw[rt].lazy3*cw[rt].lazy3%mod*cw[rt].lazy3%mod;

    cw[lson].lazy1=cw[rson].lazy1=0;

    cw[lson].lazy2=cw[rson].lazy2=1;

    cw[lson].lazy3=cw[rson].lazy3=cw[rt].lazy3;

    cw[lson].sum3 = cw[lson].d*tmp%mod;

    cw[rson].sum3 = cw[rson].d*tmp%mod;

    cw[lson].sum2 = cw[lson].d*cw[rt].lazy3%mod*cw[rt].lazy3%mod;

    cw[rson].sum2 = cw[rson].d*cw[rt].lazy3%mod*cw[rt].lazy3%mod;

    cw[lson].sum1 = cw[lson].d*cw[rt].lazy3%mod;

    cw[rson].sum1 = cw[rson].d*cw[rt].lazy3%mod;

    cw[rt].lazy3 = 0;

  }

  if(cw[rt].lazy1!=0||cw[rt].lazy2!=1){

    LL add = cw[rt].lazy1, mul = cw[rt].lazy2;

    LL l1=cw[lson].sum1,l2=cw[lson].sum2,l3=cw[lson].sum3;

    LL r1=cw[rson].sum1,r2=cw[rson].sum2,r3=cw[rson].sum3;

    LL tmp = mul*mul%mod*mul%mod;

    cw[lson].lazy1=(cw[lson].lazy1*mul%mod+add)%mod;

    cw[rson].lazy1=(cw[rson].lazy1*mul%mod+add)%mod;

    cw[lson].lazy2=cw[lson].lazy2*mul%mod;

    cw[rson].lazy2=cw[rson].lazy2*mul%mod;

    cw[lson].sum3=(cw[lson].sum3*tmp%mod + add*add%mod*add%mod*cw[lson].d%mod + 3*cw[lson].sum2*mul%mod*mul%mod*add%mod + 3*cw[lson].sum1*mul%mod*add%mod*add%mod)%mod;

    cw[rson].sum3=(cw[rson].sum3*tmp%mod + add*add%mod*add%mod*cw[rson].d%mod + 3*cw[rson].sum2*mul%mod*mul%mod*add%mod + 3*cw[rson].sum1*mul%mod*add%mod*add%mod)%mod;

    cw[lson].sum2=(cw[lson].sum2*mul%mod*mul%mod + add*add%mod*cw[lson].d%mod + 2*mul*add*cw[lson].sum1)%mod;

    cw[rson].sum2=(cw[rson].sum2*mul%mod*mul%mod + add*add%mod*cw[rson].d%mod + 2*mul*add*cw[rson].sum1)%mod;

    cw[lson].sum1=(cw[lson].sum1*mul+add*cw[lson].d)%mod;

    cw[rson].sum1=(cw[rson].sum1*mul+add*cw[rson].d)%mod;

    cw[rt].lazy1 = 0;cw[rt].lazy2 = 1;

  }

}

//op==1 加法, op==2 乘法, op==3 改变值

void update(int L,int R,int op,int z,int rt){

  int l=cw[rt].l, r=cw[rt].r, mid=(l+r)>>1;

  if(cw[rt].l>R||cw[rt].r<L)return;

  if(L<=l&&r<=R){

    LL l1 = cw[rt].sum1, l2 = cw[rt].sum2;

    if(op==1){//加法

      cw[rt].lazy1 = (z + cw[rt].lazy1)%mod;

      cw[rt].sum3 = (cw[rt].sum3 + (z*z%mod)*z%mod*cw[rt].d%mod + 3*z*(cw[rt].sum2+(cw[rt].sum1*z)%mod)%mod)%mod;

      cw[rt].sum2 = (cw[rt].sum2 + cw[rt].d*z%mod*z%mod + 2*z*cw[rt].sum1%mod)%mod;

      cw[rt].sum1 = (cw[rt].sum1 + cw[rt].d*z%mod)%mod;

    }else if(op==2){//乘法

      cw[rt].lazy1 = cw[rt].lazy1*z%mod;

      cw[rt].lazy2 = cw[rt].lazy2*z%mod;

      cw[rt].sum1 = cw[rt].sum1*z%mod;

      cw[rt].sum2 = (cw[rt].sum2*z%mod)*z%mod;

      cw[rt].sum3 = ((cw[rt].sum3*z%mod)*z%mod)*z%mod;

    }else{

      cw[rt].lazy1=0;cw[rt].lazy2=1;

      cw[rt].lazy3=z;

      cw[rt].sum3 = cw[rt].d*z%mod*z%mod*z%mod;

      cw[rt].sum2 = cw[rt].d*z%mod*z%mod;

      cw[rt].sum1 = cw[rt].d*z%mod;

    }

    return;

  }

  if(cw[rt].l==cw[rt].r)return;

  push_down(rt);

  if(L>mid)update(L,R,op,z,rson);

  else if(R<=mid)update(L,R,op,z,lson);

  else{

    update(L,mid,op,z,lson);

    update(mid+1,R,op,z,rson);

  }

  push_up(rt);

}

LL query(int L,int R,int op,int rt){

  int l=cw[rt].l, r=cw[rt].r, mid=(l+r)>>1;

  if(L<=l&&r<=R){

    if(op==1)return cw[rt].sum1;

    else if(op==2)return cw[rt].sum2;

    return cw[rt].sum3;

  }

  if(cw[rt].l==cw[rt].r)return 0;

  push_down(rt);

  LL sum = 0;

  if(L>mid) sum = query(L,R,op,rson);

  else if(R<=mid) sum = query(L,R,op,lson);

  else {

    sum = query(L,mid,op,lson);

    sum += query(mid+1,R,op,rson);

  }

  return (sum%mod);

}

int main(){

  while(~scanf("%d%d", &n,&q)&&(n+q)){

    build(1,n,1);

    while(q--){

      int op,l,r,z;

      scanf("%d%d%d%d",&op,&l,&r,&z);

      if(op<=3){

        z%=mod;

        update(l,r,op,z,1);

      }else{

        printf("%lld\n", query(l,r,z,1));

      }

    }

  }

  return 0;

}

####原题目描述：
Problem Description
Yuanfang is puzzled with the question below:
There are n integers, a1, a2, …, an. The initial values of them are 0. There are four kinds of operations.
Operation 1: Add c to each number between ax and ay inclusive. In other words, do transformation akInput

There are no more than 10 test cases.

For each case, the first line contains two numbers n and m, meaning that there are n integers and m operations. 1 <= n, m <= 100,000.

Each the following m lines contains an operation. Operation 1 to 3 is in this format: "1 x y c" or "2 x y c" or "3 x y c". Operation 4 is in this format: "4 x y p". (1 <= x <= y <= n, 1 <= c <= 10,000, 1 <= p <= 3)

The input ends with 0 0.

Output

For each operation 4, output a single integer in one line representing the result. The answer may be quite large. You just need to calculate the remainder of the answer when divided by 10007.

Sample Input

5 5

3 3 5 7

1 2 4 4

4 1 5 2

2 2 5 8

4 3 5 3

0 0

Sample Output

307

7489