不要把删除操作当成模除法，而要把每次乘法看成一个位置：插入时赋值为乘数，删除时改回 1，用线段树维护全局乘积。
OJ: luogu
题目 ID: P4588
难度:普及/提高-
标签:线段树乘积建模单点修改取模
日期: 2026-06-21 02:24
题意
初始有一个数 x = 1。
接下来有 Q 次操作：
1 m：把x变成x * m2 pos：把x除以第pos次操作乘上的那个数
每次操作后都要输出当前：
x mod M
思路
先看一个可以直接验证想法的暴力：
cpp
#include <bits/stdc++.h>
using namespace std;
// brute.cpp：直接维护每次乘法操作当前是否还“有效”，
// 每次输出时重新扫描所有有效乘数并求乘积。
const int MAXQ = 100000 + 5;
long long value_arr[MAXQ];
int alive[MAXQ];
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int T;
cin >> T;
while (T--) {
int q;
long long mod_value;
cin >> q >> mod_value;
for (int i = 1; i <= q; i++) {
value_arr[i] = 1;
alive[i] = 0;
}
for (int i = 1; i <= q; i++) {
int op;
long long x;
cin >> op >> x;
if (op == 1) {
value_arr[i] = x % mod_value;
alive[i] = 1;
} else {
alive[(int)x] = 0;
}
long long ans = 1 % mod_value;
for (int j = 1; j <= q; j++) {
if (alive[j]) {
ans = ans * value_arr[j] % mod_value;
}
}
cout << ans << '\n';
}
}
return 0;
}brute.cpp 记录每次乘法操作的值，以及它当前是否还有效。
每次输出前，把所有仍然有效的乘数重新乘一遍。
这个做法是对的，但每次都重扫所有位置，复杂度太高。
这题真正的关键是：不要把第二种操作理解成模意义下的除法。
因为模数 M 不保证是质数，也不保证被删掉的数和 M 互质，所以逆元路线并不可靠。
正确理解应该是：
- 类型 1：往当前乘积集合里加入一个乘数
- 类型 2：把某次以前加入的乘数从集合里删除
于是可以把第 i 次操作映射成一个位置：
- 如果这次乘法当前有效，这个位置存它的乘数
- 如果已经删除，或者本来不是乘法位置，这个位置存
1
由于 1 是乘法单位元，把一个位置改成 1 就等价于删掉这个乘数对总乘积的贡献。
这样题目就变成了：
- 单点修改
- 维护整个数组的乘积
用线段树维护区间乘积即可：
1 m：把位置i改成m2 pos：把位置pos改成1
每次操作后，根节点存的就是当前所有有效乘数之积模 M。
代码
cpp
#include <bits/stdc++.h>
using namespace std;
const int MAXQ = 100000 + 5;
int q;
long long mod_value;
long long seg[MAXQ << 2];
void build(int u, int l, int r) {
seg[u] = 1 % mod_value;
if (l == r) {
return;
}
int mid = (l + r) >> 1;
build(u << 1, l, mid);
build(u << 1 | 1, mid + 1, r);
}
void update(int u, int l, int r, int pos, long long val) {
if (l == r) {
seg[u] = val % mod_value;
return;
}
int mid = (l + r) >> 1;
if (pos <= mid) {
update(u << 1, l, mid, pos, val);
} else {
update(u << 1 | 1, mid + 1, r, pos, val);
}
seg[u] = seg[u << 1] * seg[u << 1 | 1] % mod_value;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int T;
cin >> T;
while (T--) {
cin >> q >> mod_value;
build(1, 1, q);
for (int i = 1; i <= q; i++) {
int op;
long long x;
cin >> op >> x;
if (op == 1) {
update(1, 1, q, i, x);
} else {
// 删除第 x 次乘法操作，相当于把对应位置恢复成乘法单位元 1。
update(1, 1, q, (int)x, 1);
}
cout << seg[1] % mod_value << '\n';
}
}
return 0;
}复杂度
对于每组数据：
- 建树：
- 每次操作：
总时间复杂度：
空间复杂度：
总结
这题的核心不是线段树本身，而是先把“删除某次乘法贡献”转成“把对应位置改回 1”。
一旦完成这个建模，后面就是一个非常干净的单点修改乘积线段树。
一图流解析
这张图把本题的建模、关键转移、实现检查和训练方法压缩到一页，适合读完正文后复盘。
