\(\large\mathcal{Description}\)
有一个数 \(x\),初始值为 \(1\). 有 \(Q\) 次操作,操作有两种类型:
1 m
:将 \(x\) 变为 \(x \times m\),并输出 \(x \bmod M\).
2 pos
:将 \(x\) 变为 \(x\) 除以第 \(pos\) 次操作所乘的数(保证第 \(pos\) 次操作一定为类型 \(1\),对于每一个类型 \(1\) 的操作至多会被除一次),并输出 \(x \bmod M\).
\(\large\mathcal{Solution}\)
感觉 ... 比较妙吧(
按时间轴建一颗线段树,初始值全是 \(1\). 叶子节点是第 \(i\) 次询问乘的数,然后区间乘维护一下没了。
具体来说。
-
1 m
: 将代表此次操作的叶子节点更新为 \(m\). 维护一下。 -
2 pos
: 将代表第 \(pos\) 次操作的叶子节点更新为 \(1\). 维护一下。
然后真没了。
\(\large\mathcal{Code}\)
#include <bits/stdc++.h>
#define reg register
using namespace std;
typedef long long LL;
typedef long double LDB;
const int N = 100010;
int T, Q, M;
struct SegmentTree // 线段树
{
struct name
{
int l, r, val;
} node[N << 2];
inline int lson(reg int p) {return p << 1;}
inline int rson(reg int p) {return p << 1 | 1;}
void build(reg int p, reg int l, reg int r)
{
node[p].l = l; node[p].r = r;
if (l == r) {node[p].val = 1; return;}
reg int mid = (l + r) >> 1;
build(lson(p), l, mid);
build(rson(p), mid + 1, r);
node[p].val = 1ll * node[lson(p)].val * node[rson(p)].val % M;
}
void change(reg int p, reg int x, reg int v)
{
if (node[p].l == node[p].r) {node[p].val = v; return;}
reg int mid = (node[p].l + node[p].r) >> 1;
if (x <= mid) change(lson(p), x, v);
else change(rson(p), x, v);
node[p].val = 1ll * node[lson(p)].val * node[rson(p)].val % M;
}
} S;
int main()
{
scanf("%d", &T);
while (T -- )
{
scanf("%d %d", &Q, &M);
S.build(1, 1, Q);
for (reg int i = 1; i <= Q; ++ i)
{
reg int opt, x;
scanf("%d %d", &opt, &x);
if (opt == 1) S.change(1, i, x);
else S.change(1, x, 1);
printf("%d\n", S.node[1].val);
}
}
return 0;
}