给出有多少次操作 和MOD 初始值为1
操作1 y 表示乘上y
操作2 y 表示除以第 y次操作乘的那个数
线段树的叶子结点i 表示 第i次操作乘的数 将1替换成y
遇到操作2 就把第i个结点的值 替换成1
利用线段树的性质，对整个1~n的区间进行维护，每次输出sum[1]的值即可
Sample Input
1
10 1000000000
1 2
2 1
1 2
1 10
2 3
2 4
1 6
1 7
1 12
2 7
Sample Output
Case #1:
2
1
2
20
10
1
6
42
504
84
1 # include <iostream> 2 # include <cstdio> 3 # include <cstring> 4 # include <algorithm> 5 # include <string> 6 # include <cmath> 7 # include <queue> 8 # include <list> 9 # define LL long long 10 using namespace std ; 11 12 const int maxn = 100005; 13 int MOD ; 14 15 LL sum[maxn<<2] ; //结点开4倍 16 17 void PushUP(int rt) //更新到父节点 18 { 19 sum[rt] = (sum[rt * 2] * sum[rt * 2 + 1]) % MOD ; //rt 为当前结点 20 21 } 22 23 void build(int l , int r , int rt) //构建线段树 24 { 25 if (l == r) 26 { 27 sum[rt] = 1 ; 28 return ; 29 } 30 int m = (l + r) / 2 ; 31 build(l , m , rt * 2) ; 32 build(m + 1 , r , rt * 2 +1) ; 33 PushUP(rt) ; 34 } 35 36 void updata(int p , LL v , int l , int r , int rt) 37 { 38 if (l == r) 39 { 40 sum[rt] = v % MOD ; 41 return ; 42 } 43 int m = (l + r) / 2 ; 44 if (p <= m) 45 updata(p , v , l , m , rt * 2) ; 46 else 47 updata(p , v , m + 1 , r , rt * 2 + 1) ; 48 PushUP(rt) ; 49 } 50 51 52 int main() 53 { 54 //freopen("in.txt","r",stdin) ; 55 int T ; 56 scanf("%d" , &T) ; 57 int Case = 0 ; 58 while(T--) 59 { 60 Case++ ; 61 int n ; 62 scanf("%d %d" , &n , &MOD) ; 63 build(1,n,1) ; 64 int i , op ; 65 LL y ; 66 printf("Case #%d: ", Case); 67 for (i = 1 ; i <= n ; i++) 68 { 69 scanf("%d %I64d" , &op , &y) ; 70 if (op == 1) 71 updata(i , y , 1 , n , 1) ; 72 if (op == 2) 73 updata(y , 1 , 1 , n , 1) ; 74 printf("%I64d ", sum[1]); 75 } 76 } 77 return 0; 78 }