题目链接 \(1\) 题目链接 \(2\)
题解
设一个区间的和、平方和、立方和分别是 \(sum_0,sum_1,sum_2\)
对于 \(add\) 操作，推推公式可知 \(\begin{cases}newsum_2=sum_2+val^3\times len+3\times val\times sum_1+3\times val^2\times sum_0\\
newsum_1=sum_1+val^2 \times len + 2\times val \times sum_0\\
newsum_0=sum_0+val\times len
\end{cases}\)
对于 \(tim,tag\) 的操作很好维护。
注意在修改时，修改区间要加懒标记，尤其是 \(tim\) 操作时要记得 \(add\times=val\)。
代码
#include <iostream>
using namespace std;
typedef long long LL;
const int N = 100010,MOD = 10007,INF = 2e9;
int n,m;
struct segment_tree_node {
int l,r;
LL sum[3];
LL add,tim,tag;
}tr[4 * N];
void push_up (int u) {
for (int i = 0;i <= 2;i++) tr[u].sum[i] = (tr[u << 1].sum[i] + tr[u << 1 | 1].sum[i]) % MOD;
}
LL power (LL x,int d) {
LL ans = 1;
while (d--) ans = ans * x % MOD;
return ans;
}
void opt_tim (int u,LL val) {
for (int i = 0;i <= 2;i++) tr[u].sum[i] = tr[u].sum[i] * power (val,i + 1) % MOD;
}
void opt_add (int u,LL val) {
int len = tr[u].r - tr[u].l + 1;
tr[u].sum[2] = (tr[u].sum[2] + power (val,3) * len % MOD + 3 * val % MOD * (tr[u].sum[1] + tr[u].sum[0] * val % MOD) % MOD) % MOD;
tr[u].sum[1] = (tr[u].sum[1] + power (val,2) * len % MOD + 2 * val * tr[u].sum[0] % MOD) % MOD;
tr[u].sum[0] = (tr[u].sum[0] + val * len % MOD) % MOD;
}
void opt_tag (int u,LL val) {
int len = tr[u].r - tr[u].l + 1;
for (int i = 0;i <= 2;i++) tr[u].sum[i] = power (val,i + 1) * len % MOD;
}
void push_down (int u) {
if (tr[u].tag != INF) {
tr[u << 1].tag = tr[u << 1 | 1].tag = tr[u].tag;
tr[u << 1].add = tr[u << 1 | 1].add = 0;
tr[u << 1].tim = tr[u << 1 | 1].tim = 1;
opt_tag (u << 1,tr[u].tag),opt_tag (u << 1 | 1,tr[u].tag);
tr[u].tag = INF;
}
if (tr[u].tim != 1) {
tr[u << 1].add = tr[u << 1].add * tr[u].tim % MOD,tr[u << 1 | 1].add = tr[u << 1 | 1].add * tr[u].tim % MOD;
tr[u << 1].tim = tr[u << 1].tim * tr[u].tim % MOD,tr[u << 1 | 1].tim = tr[u << 1 | 1].tim * tr[u].tim % MOD;
opt_tim (u << 1,tr[u].tim),opt_tim (u << 1 | 1,tr[u].tim);
tr[u].tim = 1;
}
if (tr[u].add) {
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;
opt_add (u << 1,tr[u].add),opt_add (u << 1 | 1,tr[u].add);
tr[u].add = 0;
}
}
void build_segment_tree (int u,int l,int r) {
if (l == r) {
tr[u] = {l,r,{0,0,0},0,1,INF};
return ;
}
tr[u] = {l,r,{0,0,0},0,1,INF};
int mid = l + r >> 1;
build_segment_tree (u << 1,l,mid),build_segment_tree (u << 1 | 1,mid + 1,r);
}
void modify_add (int u,int l,int r,int d) {
if (l <= tr[u].l && tr[u].r <= r) {
opt_add (u,d);
tr[u].add = (tr[u].add + d) % MOD;
return ;
}
push_down (u);
int mid = tr[u].l + tr[u].r >> 1;
if (l <= mid) modify_add (u << 1,l,r,d);
if (r >= mid + 1) modify_add (u << 1 | 1,l,r,d);
push_up (u);
}
void modify_tim (int u,int l,int r,int d) {
if (l <= tr[u].l && tr[u].r <= r) {
opt_tim (u,d);
tr[u].tim = tr[u].tim * d % MOD;
tr[u].add = tr[u].add * d % MOD;
return ;
}
push_down (u);
int mid = tr[u].l + tr[u].r >> 1;
if (l <= mid) modify_tim (u << 1,l,r,d);
if (r >= mid + 1) modify_tim (u << 1 | 1,l,r,d);
push_up (u);
}
void modify_tag (int u,int l,int r,int d) {
if (l <= tr[u].l && tr[u].r <= r) {
opt_tag (u,d);
tr[u].tag = d,tr[u].add = 0,tr[u].tim = 1;
return ;
}
push_down (u);
int mid = tr[u].l + tr[u].r >> 1;
if (l <= mid) modify_tag (u << 1,l,r,d);
if (r >= mid + 1) modify_tag (u << 1 | 1,l,r,d);
push_up (u);
}
LL query (int u,int l,int r,int p) {
if (l <= tr[u].l && tr[u].r <= r) return tr[u].sum[p] % MOD;
push_down (u);
int mid = tr[u].l + tr[u].r >> 1;
LL ans = 0;
if (l <= mid) ans = (ans + query (u << 1,l,r,p)) % MOD;
if (r >= mid + 1) ans = (ans + query (u << 1 | 1,l,r,p)) % MOD;
return ans;
}
int main () {
ios :: sync_with_stdio (false),cin.tie (0),cout.tie (0);
while (cin >> n >> m,n || m) {
build_segment_tree (1,1,n);
while (m--) {
int op,l,r,d;
cin >> op >> l >> r >> d;
if (op == 1) modify_add (1,l,r,d);
else if (op == 2) modify_tim (1,l,r,d);
else if (op == 3) modify_tag (1,l,r,d);
else cout << query (1,l,r,d - 1) << endl;
}
}
return 0;
}