现在有一个数x，初始值为1.有Q次操作，操作有两种类型:
1 m 表示让x = x * m
2 pos 表示让x除以第pos次操作所乘上的数（保证第pos次操作一定为类型1,对于每一个类型1的操作至多会被除一次）输出x%mod
首先考虑单纯模拟。题目要求答案取模，如果一边操作一边取模，得到的答案是错误的
比如：mod = 6，第一步让x = x * 7，第二步让x = x / 7。正确的答案应为1，但错误操作得出的答案是0（1/7下取整）
考虑线段树的特点：每次修改至多logn的节点，而且叶节点不需取模，向上维护的时候边乘边取模。
所以对1~Q建立线段树，每次如果opt=1就修改当前操作序号对应节点的值为输入的m，opt=2就修改pos对应节点的值为1。初值都设为1即可
感觉主要难度在于想到可以在操作上建立线段树。
#include <cstdio> #include <cstring> #include <cmath> #include <algorithm> #include <iostream> #include <queue> using namespace std; #define ll long long #define ull unsigned long long #define ld long double #define lowbit(x) ((x) & (-x)) #define For(x, i, j) for (int x = (i); x <= (j); x++) #define FOR(x, i, j) for (int x = (i); x >= (j); x--) #define FE(i, x) for (int i = head[x]; i; i = e[i].Next) #define ls(o) (o << 1) #define rs(o) (o << 1 | 1) #define debug(x) cout << "debug : " << x << endl; inline ll read(){ ll s=0,w=1; char ch=getchar(); while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)w=-1;ch=getchar();} while(ch>=‘0‘&&ch<=‘9‘) s=s*10+ch-‘0‘,ch=getchar(); return s*w; } #define N 100005 ll T, Q, mod; ll mul[N << 2]; void pushup(ll o) {mul[o] = mul[ls(o)] * mul[rs(o)] % mod;} void build(ll o, ll l, ll r) { if (l == r) {mul[o] = 1; return;} ll mid = (l + r) >> 1; build(ls(o), l, mid); build(rs(o), mid + 1, r); pushup(o); } void update(ll o, ll l, ll r, ll x, ll k) { if (l == r) {mul[o] = k; return;} ll mid = (l + r) >> 1; if (x <= mid) update(ls(o), l, mid, x, k); else update(rs(o), mid + 1, r, x, k); pushup(o); } ll a[N]; int main() { T = read(); while (T--) { Q = read(); mod = read(); ll opt; build(1, 1, Q); For(i, 1, Q) { opt = read(); a[i] = read(); if (opt == 1) update(1, 1, Q, i, a[i]); else update(1, 1, Q, a[i], 1); printf("%lld\n", mul[1]); } } return 0; }
原文：https://www.cnblogs.com/FL4K/p/14054450.html