这可以算作线段树的一道入门题。
我们构建一棵范围$[1, Q]$的线段树。
每个叶节点对应一次操作。
每个节点的权值对应其区间积。
每有一次$1$操作我们就把对应的位置（第几次操作）改成相应的值然后维护线段树。
设当前是第$p$次操作，则查询输出$[1, p]$的积即可。
而$2$操作时我们先把当前位置设成1，再把$pos$设成1即可。
查询还是$[1, p]$。
其实我们可以偷个小懒……
初始时所有叶节点的权值设为$1$，输出时只用输出$[1, Q]$的值即可（看不懂的自己思考一下）。
（~我们都是会思考的乌鸦……
#include <iostream> #include <cstdio> using namespace std; typedef long long ll; struct Segment{ ll val; }st[400010]; ll t; ll q, mod; ll opt, m[100010]; void build(ll p, ll l, ll r) { if (l == r) { st[p].val = 1; return; } ll mid = (l + r) >> 1; build(p << 1, l, mid); build(p << 1 | 1, mid + 1, r); st[p].val = (st[p << 1].val * st[p << 1 | 1].val) % mod; } void change(ll p, ll l, ll r, ll pos, ll v) { if (l == r) { st[p].val = v; return; } ll mid = (l + r) >> 1; if (pos <= mid) change(p << 1, l, mid, pos, v); else change(p << 1 | 1, mid + 1, r, pos, v); st[p].val = (st[p << 1].val * st[p << 1 | 1].val) % mod; } int main() { scanf("%lld", &t); while (t--) { scanf("%lld%lld", &q, &mod); build(1, 1, q); for (ll i = 1; i <= q; i++) { scanf("%lld%lld", &opt, &m[i]); if (opt == 1) { change(1, 1, q, i, m[i]); printf("%lld ", st[1].val); } else { change(1, 1, q, m[i], 1); printf("%lld ", st[1].val); } } } return 0; }
请大家不要抄（jie jian）我的代码（自带大常数）QWQ……