自己写了一个带结构体的WA了7.8次 但是测了几组小数据都对。。感觉问题应该出在模运算那里。写完这波题解去对拍一下。
以后线段树绝不写struct！一般的struct都带上l,r 但是一条线段的长度确定的话，每一个节点的l,r都可以确定的，没必要用struct存上，如果不带上l，r那不是更没必要用结构体hhh
这道题有点坑的地方就是顺序问题
pushdown就是一个最大的难点
change表示改数字 add表示加上数字 multiply表示乘以一个数字
正确的方法应该是 先change 再multiply 再add
先看multiply和add的关系
现在p的数字是x 先add a 然后multiply b 就会变成 b*(x+a)假如我们采用保留括号的方法 那么先multiply后add会变得异常麻烦
因为先multiply后add是b*x+a 再搞出一个括号来会有误差 所以我们选择不保留括号 如果先add后multiply的话 add的数字就乘上multiply的数字
这样就不会有误差 所以在pushdown操作里面 我们就先multiply后add 因为多项式是bx+a嘛 肯定是先乘后加
再看change操作
假如现在p有change标记以及multiply || add操作(我们已经搞清楚multiply和add操作了，就可以把他们看成一个操作ma就好了)
如果先change后ma 我们对lp、rp是不是就得先change后ma 相当于把 x1 x2都改成a 再乘4 相当于x1改成a乘4 x2改成a乘4
如果先ma后change 我们是不是ma的标记全被清空了 这样先change的话也没问题 因为对lp rp根本不会进行ma操作，因为标记都清空了
具体对于每个操作
change就是区间长度乘以对应的x的次数咯
multiply就是原来的和乘以对应的x的次数咯
add的话就要用到一点点初中还是高中知识
一次的话就没得说 原来的和加上区间长度乘以x
二次三次见下述公式
$\begin{aligned}\left( x_{1}+a\right) ^{2}+\left( x_{2}+a\right) ^{2}+\ldots +\left( x_{n}+a\right)^{2} = \left( x^{2}_{i}+x^{2}_{2}+\ldots +x^{2}_{n}\right) +2a\left( x_{1}+x_{2}+\ldots +x_{n}\right) +na^{2}\end{aligned}$
$\begin{aligned}\left( x_{1}+a\right) ^{3}+\left( x_{2}+a\right) ^{3}+\ldots +\left( x_{n}+a\right)^{3} = \left( x^{3}_{i}+x^{3}_{2}+\ldots +x^{3}_{n}\right) +3a^{2}\left( x_{1}+x_{2}+\ldots +x_{n}\right) + 3a\left( x^{2}_{1}+x^{2}_{2}+\ldots +x^{2}_{n}\right) +na^{2}\end{aligned}$
提取一下公因数
$\begin{aligned}\left( x_{1}+a\right) ^{3}+\left( x_{2}+a\right) ^{3}+\ldots +\left( x_{n}+a\right)^{3} = \left( x^{3}_{i}+x^{3}_{2}+\ldots +x^{3}_{n}\right) +3a\left( x^{2}_{1}+x^{2}_{2}+\ldots +x^{2}_{n}+ a\left(x_{1} + x_{2} + \ldots + x_{n}\right)\right) +na^{2}\end{aligned}$
因为求三次需要二次的和 求二次需要一次的和 那么就先算3次再算2次最后算1次
模运算部分因为太多项了。所以犯晕。保险的办法就是加括号后加一个%MOD 这样就比较保险
add和change清除后是0，multiply清楚后是1
代码如下
#include <cstdio>
#include <cstring>
#include <algorithm>
#define lp p<<1
#define rp p<<1|1
#define ll long long
#define MOD 10007
using namespace std;
const int maxn = 1e5 + ; ll add[maxn<<], multiply[maxn<<], change[maxn<<];
ll sum[maxn<<][];
inline void pushup(int p) {
for (int i = ; i <= ; i++) {
sum[p][i] = (sum[lp][i] + sum[rp][i]) % MOD;
}
}
void pushdown(int p, int llen, int rlen) {
if (change[p]) {
change[lp] = change[rp] = change[p];
multiply[lp] = multiply[rp] = ;
add[lp] = add[rp] = ;
sum[lp][] = (((((llen * change[p] % MOD) % MOD) * change[p] % MOD) % MOD) * change[p] % MOD) % MOD;
sum[rp][] = (((((rlen * change[p] % MOD) % MOD) * change[p] % MOD) % MOD) * change[p] % MOD) % MOD;
sum[lp][] = (((llen * change[p] % MOD) % MOD) * change[p] % MOD) % MOD;
sum[rp][] = (((rlen * change[p] % MOD) % MOD) * change[p] % MOD) % MOD;
sum[lp][] = (llen * change[p] % MOD) % MOD;
sum[rp][] = (rlen * change[p] % MOD) % MOD;
change[p] = ;
}
if (multiply[p] != ) {
if (add[lp]) add[lp] = add[lp] * multiply[p] % MOD;
if (add[rp]) add[rp] = add[rp] * multiply[p] % MOD;
multiply[lp] = multiply[lp] * multiply[p] % MOD;
multiply[rp] = multiply[rp] * multiply[p] % MOD;
sum[lp][] = ((((((sum[lp][] % MOD) * multiply[p] % MOD) % MOD) * multiply[p] % MOD) % MOD) * multiply[p] % MOD) % MOD;
sum[rp][] = ((((((sum[rp][] % MOD) * multiply[p] % MOD) % MOD) * multiply[p] % MOD) % MOD) * multiply[p] % MOD) % MOD;
sum[lp][] = ((((sum[lp][] % MOD) * multiply[p] % MOD) % MOD) * multiply[p] % MOD) % MOD;
sum[rp][] = ((((sum[rp][] % MOD) * multiply[p] % MOD) % MOD) * multiply[p] % MOD) % MOD;
sum[lp][] = ((sum[lp][] % MOD) * multiply[p] % MOD) % MOD;
sum[rp][] = ((sum[rp][] % MOD) * multiply[p] % MOD) % MOD;
multiply[p] = ;
}
if (add[p]) {
add[lp] = (add[lp] + add[p]) % MOD;
add[rp] = (add[rp] + add[p]) % MOD;
int temp = ((add[p] * add[p] % MOD) * add[p]) % MOD;
sum[lp][] = ((sum[lp][] + (temp * llen) % MOD) % MOD + (( * add[p] % MOD) * (sum[lp][] + sum[lp][] * add[p]) % MOD)) % MOD;
sum[rp][] = ((sum[rp][] + (temp * rlen) % MOD) % MOD + (( * add[p] % MOD) * (sum[rp][] + sum[rp][] * add[p]) % MOD)) % MOD;
sum[lp][] = (sum[lp][] + ((llen * add[p] % MOD) * add[p] % MOD) + (( * add[p] * sum[lp][]) % MOD)) % MOD;
sum[rp][] = (sum[rp][] + ((rlen * add[p] % MOD) * add[p] % MOD) + (( * add[p] * sum[rp][]) % MOD)) % MOD;
sum[lp][] = (sum[lp][] + ((llen * add[p]) % MOD)) % MOD;
sum[rp][] = (sum[rp][] + ((rlen * add[p]) % MOD)) % MOD;
add[p] = ;
}
}
void build(int p, int l, int r) {
multiply[p] = ;
add[p] = change[p] = ;
if (l == r) {
sum[p][] = sum[p][] = sum[p][] = ;
return;
}
int mid = l + r >> ;
build(lp, l, mid);
build(rp, mid + , r);
pushup(p);
}
void update(int p, int l, int r, int x, int y, int z, int type) {
if (x <= l && y >= r) {
if (type == ) {
add[p] += z; add[p] %= MOD;
sum[p][] = (sum[p][] + ((((((r - l + ) * z) % MOD) * z) % MOD) * z) % MOD + (( * z) % MOD) * (sum[p][] + (sum[p][] * z) % MOD)) % MOD;
sum[p][] = (sum[p][] + ((((r - l + ) * z) % MOD) * z) % MOD + ( * z * sum[p][] % MOD)) % MOD;
sum[p][] = (sum[p][] + ((r - l + ) * z) % MOD) % MOD;
} else if (type == ) {
multiply[p] = multiply[p] * z % MOD;
if (add[p]) add[p] = add[p] * z % MOD;
sum[p][] = (((((sum[p][] * z) % MOD) * z) % MOD) * z) % MOD;
sum[p][] = (((sum[p][] * z) % MOD) * z) % MOD;
sum[p][] = (sum[p][] * z) % MOD;
} else if (type == ) {
change[p] = z;
add[p] = ;
multiply[p] = ;
sum[p][] = ((((((r - l + ) * z) % MOD) * z) % MOD) * z) % MOD;
sum[p][] = ((((r - l + ) * z) % MOD) * z) % MOD;
sum[p][] = ((r - l + ) * z) % MOD;
}
return;
}
int mid = l + r >> ;
pushdown(p, mid - l + , r - mid);
if (x <= mid) update(lp, l, mid, x, y, z, type);
if (y > mid) update(rp, mid + , r, x, y, z, type);
pushup(p);
}
ll query(int p, int l, int r, int x, int y, int z) {
if (x <= l && y >= r) return sum[p][z] % MOD;
int mid = l + r >> ;
pushdown(p, mid - l + , r - mid);
ll res = ;
if (x <= mid) res = (res + query(lp, l, mid, x, y, z)) % MOD;
if (y > mid) res = (res + query(rp, mid + , r, x, y, z)) % MOD;
return res % MOD;
}
int main() {
int n, m;
while (~scanf("%d%d", &n, &m) && n || m) {
build(, , n);
int t, x, y, c;
while (m--) {
scanf("%d%d%d%d", &t, &x, &y, &c);
if (t == ) {
printf("%lld\n", query(, , n, x, y, c));
} else {
update(, , n, x, y, c, t);
}
}
}
return ;
}