HDU_4578_线段树多延迟标记

HDU 4578

  • 此题有2种延迟标记
    题意:

    1 x y val表示在区间[x,y]的每个值增加val
    2 x y val表示在区间[x,y]每个值乘val
    3 x y val表示将区间[x,y]上的每个值都修改为val
    4 x y val表示查询区间[x,y]上的每个值的p次幂的和

每个值看做ax+b,那么给线段树开2个延迟标记,

  1. add用来加(代表b)
  2. mult表示乘(代表a)
  3. 区间修改就能由add和mult组合操作而来,a=0 b=val
  1. 加val = ax+b +val
  2. 乘val = val * (ax+b) = ax * val + b * val
  3. 修改为val = 0*(ax+b)+val
  • 用数组sum[4]存3个次方的值
  1. 加上val给p次方的影响:

    $sum'[1] = len*val+sum[1]$
    $sum'[2] = sum[2] + 2 * sum[1] * val + len*b^2$
    $sum'[3] = sum[3] + 3*b^2*sum[1]+3*b*sum[2]+len*b^3$

  • 因为要用到sum[1],sum[2],从sum[3]开始求
  1. 乘上val给p次方的影响

    $sum'[1] = val*sum[1]$
    $sum'[2] = val^2*sum[2]$
    $sum'[3] = val^3*sum[3]$

  2. 直接修改成val带给p次方的影响等价于+ 和*
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    82
    83
    84
    85
    86
    87
    88
    89
    90
    91
    92
    93
    94
    95
    96
    97
    98
    99
    #include <iostream>
    #include <string.h>
    #define ls (p<<1)
    #define rs (p<<1|1)
    #define lson ls,left,mid
    #define rson rs,mid+1,right
    using namespace std;
    const int mod = (int)1e4+7;
    const int maxn = (int)1e5+10;
    int n, m;
    struct node {
    	int left, right;
    	int mult, addv;
    	int sum[4];
    	int length() { return right - left + 1; }
    	void multiply(int val) {
    		mult = (mult * val) % mod;
    		addv = (addv * val) % mod;
    		for (int i = 1; i <= 3; i++)
    			for (int j = 1; j <= i; j++)
    				sum[i] = (sum[i] * val) % mod;
    	}
    	void add(int val) {
    		int len = length();
    		addv = (addv + val) % mod;
    		
    		sum[3] = (sum[3] + 3 * val % mod * val % mod * sum[1] % mod ) % mod;
    		sum[3] = (sum[3] + 3 * val % mod * sum[2] % mod) % mod;
    		sum[3] = (sum[3] + len * val % mod * val % mod * val % mod) % mod;

    		sum[2] = (sum[2] + 2 * val % mod * sum[1] % mod) % mod; //倒序的原因是sun[1]此时要未修改的
    		sum[2] = (sum[2] + len * val % mod * val % mod) % mod;

    		sum[1] = (sum[1] + len * val % mod) % mod;
    	}
    	void cal(int MUL,int ADD) {
    		multiply(MUL);
    		add(ADD);
    	}
    }tree[maxn << 2];
    void pushDown(int p) {
    	if (tree[p].mult != 1 || tree[p].addv != 0) {
    		tree[ls].cal(tree[p].mult, tree[p].addv); //cal这个函数一次性解决+和*
    		tree[rs].cal(tree[p].mult, tree[p].addv);
    		tree[p].mult = 1; tree[p].addv = 0;
    	}
    }
    void pushUp(int p) {
    	for (int i = 1; i <= 3; i++) 
    		tree[p].sum[i] = (tree[ls].sum[i] + tree[rs].sum[i]) % mod;
    }

    void build(int p,int left,int right) {
    	tree[p].left = left; tree[p].right = right;
    	tree[p].addv = 0; tree[p].mult = 1;//初始化
    	memset(tree[p].sum,0,4 * sizeof(int));
    	if (left == right) return;
    	int mid = (left + right) / 2;
    	build(lson);
    	build(rson);
    }

    int query(int p,int left,int right,int ql,int qr,int x) {
    	if (ql <= left && right <= qr) return tree[p].sum[x];
    	int mid = (left + right) / 2, ans = 0;
    	pushDown(p);
    	if (ql <= mid) ans = (ans + query(lson,ql,qr,x)) % mod;
    	if (mid < qr)  ans = (ans + query(rson,ql,qr,x)) % mod;
    	return ans;
    }

    void modify(int p,int left,int right,int ql,int qr,int val,int op) {
    	if (ql <= left && right <= qr) {
    		if (op == 1) tree[p].cal(1, val);
    		else if (op == 2) tree[p].cal(val, 0);
    		else tree[p].cal(0, val);
    		return;
    	} 
    	int mid = (left + right) / 2;
    	pushDown(p);
    	if (ql <= mid) modify(lson,ql,qr,val,op);
    	if (mid < qr)  modify(rson,ql,qr,val,op);
    	pushUp(p);
    }

    int main() {
    	//freopen("a.txt","r",stdin);
    	int op, ql, qr, val;
    	while (scanf("%d%d",&n,&m) != EOF && (n || m)) {
    		build(1,1,n);
    		while (m--) {
    			scanf("%d%d%d%d",&op,&ql,&qr,&val);
    			if (op == 4)
    				printf("%d\n", query(1, 1, n, ql, qr, val) % mod);
    			else modify(1,1,n,ql,qr,val,op);
    		}
    	}
    	return 0;
    }