P4588 [TJOI2018] 数学计算
Tag：线段树
题目描述
有一个数字 \(x\) ， 初始数值为 \(1\) ， 我们有 \(Q\) 次操作， 操作分为两种：
-
1 m把 \(x\) 变成 \(x \times m\) -
2 pos把 \(x\) 变为 \(x\) 除以第 \(pos\) 次所乘以的数字
每次操作之后输出 \(x \bmod M\)。
数据说明：
\(1 \le Q \le 10^5\)，\(t \le 5, M \le 10^9\)，\(0 < m \leq 10^9\)。
保证数据合法，即操作2的 \(pos\) 必定是一个曾经执行过操作1的位置。
分析
首先我们对题目进行分析， 如果用一个比较平凡的想法， 我们会想一路乘过去， 当我们执行操作 \(2\) 的时候我们就除以掉某个数， 这样显然是不行的，因为这道题是存在模数的， 我们在取模之后是无法通过除法复原出我们想要的数字的， 所以模拟是不可以的。
正因为本题是处于模意义下的计算， 可能会想到，我们每次执行操作 \(2\) 的时候只要乘上乘法逆元就可以了。 这样也是不可以的，因为题目数据中并没有保证到 \(m\) 是一个质数， 所以我们不能用乘法逆元来解决这道题。
我们进一步思考这个题目， 题目所执行的操作可以理解成把一堆数字排成一排， 需要你计算这些数字的乘积， 并且能够计算出消除掉曾经某个数字后这一排数字的乘积。
想到这里，如果我们在这个序列上建造一个线段树， 这个题就变成了单点修改 + 维护区间乘积的题目了。 因此我们可以使用线段树来解决这个题目。
综上所述，我们维护一个线段树， 这个线段树所有叶子结点初始值都是1， 我们的操作 \(1\) 本质上就是把一个数字变成 \(m\) ， 而操作 \(2\) 的本质就是把一个数字变成 \(1\) 。 所以我们维护一个支持单点修改， 维护一下全局乘积的线段树就可以了。
代码实现
struct SegmentTree {
#define lc (cur) << 1
#define rc (cur) << 1 | 1
int mod;
struct TreeNode{
int l,r,mul;
};
static const int TreeNodeMax = 1e5+5;
int val[TreeNodeMax];
TreeNode tree[TreeNodeMax << 2];
void build(int cur,int l,int r){
tree[cur] = {l,r,1};
if(l == r) return;
int mid = (l + r) >> 1;
build(lc,l,mid);
build(rc,mid + 1,r);
tree[cur].mul = tree[lc].mul * tree[rc].mul;
}
void pushUp(int cur){
tree[cur].mul = (tree[lc].mul * tree[rc].mul) % mod;
}
void update(int cur,int l,int r,int k){
if(l <= tree[cur].l && tree[cur].r <= r){
tree[cur].mul = k;
return;
}
int mid = (tree[cur].l + tree[cur].r) >> 1;
if(l <= mid) update(lc,l,r,k);
if(r > mid) update(rc,l,r,k);
pushUp(cur);
}
int query(int cur,int l,int r){
if(l <= tree[cur].l && tree[cur].r <= r){
return tree[cur].mul;//这里是区间信息
}
int mid = (tree[cur].l + tree[cur].r) >> 1;
int res = 1;
if(l <= mid) res *= query(lc, l, r) % mod;
if(r > mid) res *= query(rc, l, r) % mod;
return res;
}
};
SegmentTree seg;
void NeverSayNever() {
int T; cin >> T;
while(T--){
int q; cin >> q >> seg.mod;
seg.build(1,1,1e5);
for (int i = 1; i <= q; ++i) {
int op; cin >> op;
if(op == 1){
int m; cin >> m;
m %= seg.mod;
seg.update(1,i,i,m);
cout << seg.query(1,1,q) % seg.mod << endl;
}else{
int pos; cin >> pos;
seg.update(1,pos,pos,1);
cout << seg.query(1,1,q) % seg.mod << endl;
}
}
}
}
额外思考
这个题给我们带来了什么思考呢？ 我们先来思考一下这个题可不可以用 \(\text{BIT}\)（树状数组）来做。 答案是不可以，但是为什么呢？
我们考虑一下如果我们要用 \(\text{BIT}\) 来做这道题的话是什么样的，
\(\text{BIT}\) 的修改操作是从上到下的，
而这道题我们要实现的操作是从下到上的，
由于 \(\text{BIT}\) 并不支持 pushUp 操作，
所以无法做到这种从下到上的操作。
除此之外还有一个原因，就是因为本题的 \(m\) 没有保证是一个质数， 因此在这个题的背景下其操作 \(1\) 没有逆的， 因为 \(\text{BIT}\) 维护单点修改，需要你维护的东西有结合律、交换律、逆元， 而这个题的操作没有逆元，所以我们无法使用 \(\text{BIT}\) 维护。
由此我们可以进一步思考线段树和 \(\text{BIT}\) 的区别，
线段树的 pushUp 是把一路上的信息重新计算，
而 \(\text{BIT}\) 是在之前计算好的信息上进行计算，
而由于操作 \(1\) 没有逆，所以这题无法使用 \(\text{BIT}\) 来做。
日志
本页面创建于 2024/6/23 22:22
特别鸣谢:
01/Ackerlanna/Nelofus/zhafde推荐了这个题目
Jlyfish和Inkyo提供的帮助
UPD-1：2024/6/24 02:01 增加了“额外思考”，并且修改若干处笔误。