`tag2`本身就不对。
既然是乘法,`tag2`默认值应为$1$。
`pushdown+moveTag`部分也不正确。
所以样例都过不了,其它问题待会遇见了再说。
by williamwei @ 2023-03-21 21:09:57
@[KK_lang](/user/548203)
by williamwei @ 2023-03-21 21:10:28
@[williamwei](/user/700558) 还是没调出来,刚刚改了一个 ```pushdown```
```tag1[x] = tag2[x] = 0``` 改成了 ```tag1[x] = 0, tag2[x] = 1```
能麻烦您再看看吗 qwq
by KK_lang @ 2023-03-21 21:24:54
ok, 稍等.
by williamwei @ 2023-03-21 21:27:07
`pushdown`大改了,`build`加了个初始化。
`tip:` `build` 最前面加上 `tag2[x]=1`
估计其它地方还有问题。
`pushdown:`
```cpp
void pushdown(int x, int l, int r)
{
if (tag2[x] != 1) {
(tag2[lc(x)] *= tag2[x]) %= p; (tag2[rc(x)] *= tag2[x]) %= p;
(tag1[lc(x)] *= tag2[x]) %= p; (tag1[rc(x)] *= tag2[x]) %= p;
(seg[lc(x)] *= tag2[x]) %= p; (seg[rc(x)] *= tag2[x]) %= p;
tag2[x] = 1;
}
if (tag1[x]) {
int mid = (l + r) >> 1;
(seg[lc(x)] += tag1[x] * (mid - l + 1)) %= p; (seg[rc(x)] += tag1[x] * (r - mid)) %= p;
(tag1[lc(x)] += tag1[x]) %= p; (tag1[rc(x)] += tag1[x]) %= p;
tag1[x] = 0;
}
}
```
by williamwei @ 2023-03-21 21:34:23
样例至少过了,改了亿点。
```cpp
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int NR = 1e5;
int n, m, p, a[NR + 10];
int seg[4 * NR + 10];
int tag1[4 * NR + 10]; // +
int tag2[4 * NR + 10]; // *
int lc(int x) { return 2 * x; }
int rc(int x) { return 2 * x + 1; }
void pushup(int x)
{
seg[x] = (seg[lc(x)] + seg[rc(x)]) % p;
}
void build(int x, int l, int r)
{
tag2[x] = 1;
if (l == r)
{
seg[x] = a[l] % p;
return;
}
int mid = (l + r) / 2;
build(lc(x), l, mid);
build(rc(x), mid + 1, r);
pushup(x);
}
void pushdown(int x, int l, int r)
{
if (tag2[x] != 1) {
(tag2[lc(x)] *= tag2[x]) %= p; (tag2[rc(x)] *= tag2[x]) %= p;
(tag1[lc(x)] *= tag2[x]) %= p; (tag1[rc(x)] *= tag2[x]) %= p;
(seg[lc(x)] *= tag2[x]) %= p; (seg[rc(x)] *= tag2[x]) %= p;
tag2[x] = 1;
}
if (tag1[x]) {
int mid = (l + r) >> 1;
(seg[lc(x)] += tag1[x] * (mid - l + 1)) %= p; (seg[rc(x)] += tag1[x] * (r - mid)) %= p;
(tag1[lc(x)] += tag1[x]) %= p; (tag1[rc(x)] += tag1[x]) %= p;
tag1[x] = 0;
}
}
void mul(int k, int l, int r, int L, int R, int v) {
if (L <= l && r <= R) {
(tag1[k] *= v) %= p;
(tag2[k] *= v) %= p;
(seg[k] *= v) %= p;
return;
} pushdown(k, l, r);
int mid = (l + r) >> 1;
if (L <= mid) mul(lc(k), l, mid, L, R, v);
if (R > mid) mul(rc(k), mid + 1, r, L, R, v);
pushup(k);
}
void add(int k, int l, int r, int L, int R, int v) {
if (L <= l && r <= R) {
(seg[k] += v * (r - l + 1)) %= p;
(tag1[k] += v) %= p; return;
} pushdown(k, l, r);
int mid = (l + r) >> 1;
if (L <= mid) add(lc(k), l, mid, L, R, v);
if (R > mid) add(rc(k), mid + 1, r, L, R, v);
pushup(k);
}
int query(int x, int l, int r, int ql, int qr)
{
if (ql <= l && r <= qr) return seg[x];
pushdown(x, l, r);
int ans = 0, mid = (l + r) / 2;
if (ql <= mid) ans = (ans + query(lc(x), l, mid, ql, qr)) % p;
if (mid + 1 <= qr) ans = (ans + query(rc(x), mid + 1, r, ql, qr)) % p;
return ans;
}
signed main()
{
cin >> n >> m >> p;
for (int i = 1; i <= n; i++) cin >> a[i];
build(1, 1, n);
for (int i = 1; i <= m; i++)
{
int op, l, r, k;
cin >> op >> l >> r;
if (op == 1)
{
cin >> k;
mul(1, 1, n, l, r, k);
}
if (op == 2)
{
cin >> k;
add(1, 1, n, l, r, k);
}
if (op == 3) cout << query(1, 1, n, l, r) << endl;
}
return 0;
}
```
by williamwei @ 2023-03-21 21:39:07
@[KK_lang](/user/548203)
by williamwei @ 2023-03-21 21:39:22
目前看上去没大问题,看原来的代码,貌似懒标记和修改有些问题。
修改后码风可能略有不同。
by williamwei @ 2023-03-21 21:40:52
@[williamwei](/user/700558) 谢
by KK_lang @ 2023-03-21 22:08:07