Transformation

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 ak<—ak+c, k = x,x+1,…,y.
Operation 2: Multiply c to each number between ax and ay inclusive. In other words, do transformation ak<—ak×c, k = x,x+1,…,y.
Operation 3: Change the numbers between ax and ay to c, inclusive. In other words, do transformation ak<—c, k = x,x+1,…,y.
Operation 4: Get the sum of p power among the numbers between ax and ay inclusive. In other words, get the result of axp+ax+1p+…+ay p.
Yuanfang has no idea of how to do it. So he wants to ask you to help him.

思路

线段树，这题主要考验的是lazy的处理，还要平方和和立方和公式，pushup还是比较容易的，三个和都是左加右，接下来思考pushdown

  1. change直接改变整个区间的值，之前的mul标记和add标记都会失效，所有第一个应该处理change标记

    1
    2
    3
    区间和: change * 区间长度
    平方和: change * change * 区间长度
    立方和: change * change * change * 区间长度

  2. 然后是根据运算优先级优先处理mul标记

    1
    2
    3
    4
    区间和: 原区间和 * mul
    平方和: 原平方和 * mul * mul
    立方和: 原立方和 * mul * mul * mul
    add: add * mul;

  3. 最后是add操作

    1
    2
    3
    区间和: 原区间和 + add * 区间长度
    平方和: 原平方和 + add * add * 区间长度 + 2 * 原区间和 * add
    立方和: 原立方和 + 3 * 原平方和 * add * add + 3 * add * add * 原区间和 + 区间长度 * add * add * add

真的巨恶心，推公式确定没有推错就花了40min，然后写完花了30min，在之后调整pushdown又花了30min，然后因为一些编译器问题一直TLE，总耗时3h

Code

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
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
#include<bits/stdc++.h>
using namespace std;
const int N = 100010, mod = 10007;
#define int long long
struct SegTree
{
	int l, r;
	int mul, add, change;
	int sum1, sum2, sum3;
}tr[N << 2];

void pushup(int u)
{
	tr[u].sum1 = (tr[u << 1].sum1 + tr[u << 1 | 1].sum1) % mod;
	tr[u].sum2 = (tr[u << 1].sum2 + tr[u << 1 | 1].sum2) % mod;
	tr[u].sum3 = (tr[u << 1].sum3 + tr[u << 1 | 1].sum3) % mod;
}

void pushdown(int u)
{
	int llen = tr[u << 1].r - tr[u << 1].l + 1, rlen = tr[u << 1 | 1].r - tr[u << 1 | 1].l + 1;
	if(tr[u].change != 0)
	{
		tr[u << 1].mul = tr[u << 1 | 1].mul = 1;
		tr[u << 1].add = tr[u << 1 | 1].add = 0;
		tr[u << 1].sum1 = tr[u].change * llen % mod; tr[u << 1 | 1].sum1 = tr[u].change * rlen % mod;
		tr[u << 1].sum2 = tr[u].change * tr[u].change * llen % mod; tr[u << 1 | 1].sum2 = tr[u].change * tr[u].change * rlen % mod;
		tr[u << 1].sum3 = tr[u].change * tr[u].change * tr[u].change * llen % mod; tr[u << 1 | 1].sum3 = tr[u].change * tr[u].change * tr[u].change * rlen % mod;
		tr[u << 1].change = tr[u << 1 | 1].change = tr[u].change;
		tr[u].change = 0;
	}
	if(tr[u].mul != 1)
	{
		tr[u << 1].mul = tr[u << 1].mul * tr[u].mul % mod; tr[u << 1 | 1].mul = tr[u << 1 | 1].mul * tr[u].mul % mod;
		tr[u << 1].add = tr[u << 1].add * tr[u].mul % mod; tr[u << 1 | 1].add = tr[u << 1 | 1].add * tr[u].mul % mod;
		tr[u << 1].sum1 = tr[u << 1].sum1 * tr[u].mul % mod; tr[u << 1 | 1].sum1 = tr[u << 1 | 1].sum1 * tr[u].mul % mod;
		tr[u << 1].sum2 = tr[u << 1].sum2 * tr[u].mul * tr[u].mul % mod; tr[u << 1 | 1].sum2 = tr[u << 1 | 1].sum2 * tr[u].mul * tr[u].mul % mod;
		tr[u << 1].sum3 = tr[u << 1].sum3 * tr[u].mul * tr[u].mul * tr[u].mul % mod; tr[u << 1 | 1].sum3 = tr[u << 1 | 1].sum3 * tr[u].mul * tr[u].mul * tr[u].mul % mod;
		tr[u].mul = 1;
 	}
	if(tr[u].add != 0)
	{
		int a = tr[u << 1].sum1, b = tr[u << 1 | 1].sum1, c = tr[u << 1].sum2, d = tr[u << 1 | 1].sum2;
		tr[u << 1].add = (tr[u << 1].add + tr[u].add) % mod; tr[u << 1 | 1].add = (tr[u << 1 | 1].add + tr[u].add) % mod;
		tr[u << 1].sum1 = (tr[u << 1].sum1 + tr[u].add * llen) % mod; tr[u << 1 | 1].sum1 = (tr[u << 1 | 1].sum1 + tr[u].add * rlen) % mod;
		tr[u << 1].sum2 = (tr[u << 1].sum2 + tr[u].add * tr[u].add * llen  + 2 * a * tr[u].add) % mod; tr[u << 1 | 1].sum2 = (tr[u << 1 | 1].sum2 + tr[u].add * tr[u].add * rlen  + 2 * b * tr[u].add) % mod;
		tr[u << 1].sum3 = (tr[u << 1].sum3 + 3 * c * tr[u].add + 3 * a * tr[u].add * tr[u].add + llen * tr[u].add * tr[u].add * tr[u].add) % mod;
		tr[u << 1 | 1].sum3 = (tr[u << 1 | 1].sum3 + 3 * d * tr[u].add + 3 * b * tr[u].add * tr[u].add + rlen * tr[u].add * tr[u].add * tr[u].add) % mod;
		tr[u].add = 0;
	}
}

void updateadd(int u, int l, int r, int add)
{
	if(tr[u].l >= l && tr[u].r <= r)
	{
		int len = tr[u].r - tr[u].l + 1;
		tr[u].add = (tr[u].add + add) % mod;
		tr[u].sum3 = (tr[u].sum3 + 3 * tr[u].sum2 * add + 3 * tr[u].sum1 * add * add + add * add * add *len) % mod;
		tr[u].sum2 = (tr[u].sum2 + len * add * add + 2 * add * tr[u].sum1) % mod;
		tr[u].sum1 = (tr[u].sum1 + add * len) % mod;
		return;
	} 
	pushdown(u);
	int mid = (tr[u].l + tr[u].r) >> 1;
	if(l <= mid) updateadd(u << 1, l, r, add);
	if(r > mid) updateadd(u << 1 | 1, l, r, add);
	pushup(u);
}

void updatemul(int u, int l, int r, int mul)
{
	if(tr[u].l >= l && tr[u].r <= r)
	{
		tr[u].mul = tr[u].mul * mul % mod;
		tr[u].add = tr[u].add * mul % mod;
		tr[u].sum1 = tr[u].sum1 * mul % mod;
		tr[u].sum2 = tr[u].sum2 * mul  % mod * mul % mod;
		tr[u].sum3 = tr[u].sum3 * mul  % mod * mul % mod * mul % mod;
		return;
	} 
	pushdown(u);
	int mid = (tr[u].l + tr[u].r) >> 1;
	if(l <= mid) updatemul(u << 1, l, r, mul);
	if(r > mid) updatemul(u << 1 | 1, l, r, mul);
	pushup(u);
}

void updatechange(int u, int l, int r, int c)
{
	if(tr[u].l >= l && tr[u].r <= r)
	{
		int len = tr[u].r - tr[u].l + 1;
		tr[u].mul = 1;
		tr[u].add = 0;
		tr[u].change = c;
		tr[u].sum1 = c * len % mod;
		tr[u].sum2 = c * c * len % mod;
		tr[u].sum3 = c * c * c * len % mod;
		return;
	} 
	pushdown(u);
	int mid = (tr[u].l + tr[u].r) >> 1;
	if(l <= mid) updatechange(u << 1, l, r, c);
	if(r > mid) updatechange(u << 1 | 1, l, r, c);
	pushup(u);
}

void build(int u, int l, int r)
{
	tr[u].l = l; tr[u].r = r;
	tr[u].mul = 1;
	tr[u].add = tr[u].change = tr[u].sum1 = tr[u].sum2 = tr[u].sum3 = 0;
	if(l == r) return;
	int mid = (l + r) >> 1;
	build(u << 1, l, mid);
	build(u << 1 | 1, mid + 1, r);
}

int query(int u, int l, int r, int opt)
{
	
	if(tr[u].l >= l && tr[u].r <= r)
	{

		if(opt == 1) return tr[u].sum1;
		else if(opt == 2) return tr[u].sum2;
		else return tr[u].sum3;
	}
	int res = 0;
	pushdown(u);
	int mid = (tr[u].l + tr[u].r) >> 1;
	if(l <= mid) res += query(u << 1, l, r, opt);
	if(r > mid) res += query(u << 1 | 1, l, r, opt);
	return res % mod;
}

signed main()
{
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	int n, m;
	while(cin >> n >> m, n || m)
	{
		build(1, 1, n);
		for(int i = 0; i < m; i++)
		{
			int opt, a, b ,c;
			cin >> opt >> a >> b >> c;
			//cout << opt << endl;
			if(opt == 1) updateadd(1, a, b, c);
			else if(opt == 2) updatemul(1, a, b, c);
			else if(opt == 3) updatechange(1, a, b, c);
			else cout << query(1, a, b, c) << '\n';
		}
	}
	return 0;
}