题目分析：
大概是考场上的签到题。首先mod不是质数，所以不能求逆元。注意到有加入操作和删除操作。一个很典型的想法就是线段树分治。建立时间线段树然后只更改有影响的节点，最后把所有标记下传。时间复杂度是O(nlogn)。
代码：
1 #include<bits/stdc++.h> 2 using namespace std; 3 4 int q,mod; 5 6 int data[405000]; 7 struct node{int l,r,d;}p[102000]; 8 9 void read(){ 10 memset(p,0,sizeof(p)); 11 memset(data,0,sizeof(data)); 12 scanf("%d%d",&q,&mod); 13 for(int i=1;i<=q;i++){ 14 int cas; scanf("%d",&cas); 15 int x; scanf("%d",&x); 16 if(cas == 1){ 17 p[i].l = i;p[i].d = x; 18 }else{p[x].r = i;} 19 } 20 } 21 22 void add(int now,int tl,int tr,int l,int r,int d){ 23 if(tl >= l && tr <= r){ 24 data[now] = (1ll*data[now]*d)%mod; 25 return; 26 } 27 if(tl > r || tr < l) return; 28 int mid = (tl+tr)/2; 29 add(now<<1,tl,mid,l,r,d); 30 add(now<<1|1,mid+1,tr,l,r,d); 31 } 32 33 void dfs(int now,int tl,int tr){ 34 if(tl == tr){printf("%d ",data[now]);return;} 35 int L = now*2,R = now*2+1; 36 data[L] = (1ll*data[L]*data[now])%mod; 37 data[R] = (1ll*data[R]*data[now])%mod; 38 data[now] = 1;int mid =(tl+tr)/2; 39 dfs(L,tl,mid); dfs(R,mid+1,tr); 40 } 41 42 void work(){ 43 for(int i=1;i<=4*q;i++) data[i] = 1; 44 for(int i=1;i<=q;i++){ 45 if(p[i].l == 0) continue; 46 if(p[i].r == 0) add(1,1,q,p[i].l,q,p[i].d); 47 else add(1,1,q,p[i].l,p[i].r-1,p[i].d); 48 } 49 dfs(1,1,q); 50 } 51 52 int main(){ 53 int t; scanf("%d",&t); 54 while(t--){ 55 read(); 56 work(); 57 } 58 return 0; 59 }