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
|
#include <cstring>
#include <algorithm>
#define ls (o<<1)
#define rs (o<<1|1)
#define lson L, M,ls
#define rson M+1, R,rs
using namespace std;
const int MOD = (int)1e4 + 7;
const int MAXN = (int)1e5 + 10;
int n, m;
struct {
int L, R;
int sum[4];
int mult, addv;
inline int length() { return R - L + 1; }
void multiply(int val) {
mult = (mult * val) % MOD;
addv = (addv * val) % MOD;
for(int i = 1; i <= 3; i++) {
for(int p = 1; p <= i; p++) {
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;
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);
}
} node[MAXN << 2];
void pushDown(int o) {
if(node[o].mult != 1 || node[o].addv != 0) {
node[ls].cal(node[o].mult, node[o].addv);
node[rs].cal(node[o].mult, node[o].addv);
node[o].mult = 1, node[o].addv = 0;
}
}
void pushUp(int o) {
for(int i = 1; i <= 3; i++) {
node[o].sum[i] = (node[ls].sum[i] + node[rs].sum[i]) % MOD;
}
}
void build(int L, int R,int o) {
node[o].L = L, node[o].R = R;
node[o].addv = 0, node[o].mult = 1;
memset(node[o].sum, 0, 4*sizeof(int));
if(L == R) return ;
int M = (L + R)/2;
build(lson);
build(rson);
}
int query(int ql, int qr, int p,int L,int R,int o) {
if(ql <= L && R <= qr) return node[o].sum[p];
int M = (L + R)/2, ret = 0;
pushDown(o);
if(ql <= M) ret = (ret + query(ql, qr, p,lson)) % MOD;
if(qr > M) ret = (ret + query(ql, qr, p,rson)) % MOD;
return ret;
}
void modify(int ql, int qr, int val, int op ,int L, int R,int o) {
if(ql <= L && R <= qr) {
if(op == 1) node[o].cal(1, val);
else if(op == 2) node[o].cal(val, 0);
else node[o].cal(0, val);
return ;
}
int M = (L + R)/2;
pushDown(o);
if(ql <= M) modify(ql, qr, val, op,lson);
if(qr > M) modify(ql, qr, val, op,rson);
pushUp(o);
}
int main() {
int op, ql, qr, val;
while(~scanf("%d%d", &n, &m) && (n || m)) {
build(1, n,1 );
while(m--) {
scanf("%d%d%d%d", &op, &ql, &qr, &val);
if(op == 4) {
printf("%dn", query(ql, qr, val,1,n,1) % MOD);
}else {
modify(ql, qr, val, op,1,n,1);
}
}
}
return 0;
}
|
近期评论