BZOJ5334:[TJOI2018]数学计算(线段树)

Description

小豆现在有一个数x，初始值为1. 小豆有Q次操作，操作有两种类型: 
1 m: x = x  *  m ，输出 x%mod;
2 pos: x = x /  第pos次操作所乘的数（保证第pos次操作一定为类型1，对于每一个类型1 的操作至多会被除一次），输出x%mod

Input

一共有t组输入（t ≤ 5）
对于每一组输入，第一行是两个数字Q, mod(Q ≤ 100000, mod  ≤ 1000000000); 
接下来Q行，每一行为操作类型op，操作编号或所乘的数字m（保证所有的输入都是合法的）.
1 ≤ Q ≤ 100000

Output

对于每一个操作，输出一行，包含操作执行后的x%mod的值

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

2

1

2

20

10

1

6

42

504

84

Solution

一开始以为是个数学题……

后来发现就是以操作序号为下标建线段树，修改就单点修改，查询就是查询线段树根的乘积。

Code

1 #include
2 #include
3 #include
4 #define N (100009)
5 using namespace std;
6
7 struct Sgt{int val,ls,rs;}Segt[N*20];
8 int T,q,MOD,sgt_num,Root,opt,m;
9
10 inline int read()
11 {
12 int x=0,w=1; char c=getchar();
13 while (c<'0' || c>'9') {if (c=='-') w=-1; c=getchar();}
14 while (c>='0' && c<='9') x=x*10+c-'0', c=getchar();
15 return x*w;
16 }
17
18 void Pushup(int now)
19 {
20 Segt[now].val=1;
21 int ls=Segt[now].ls,rs=Segt[now].rs;
22 if (ls) Segt[now].val=1ll*Segt[now].val*Segt[ls].val%MOD;
23 if (rs) Segt[now].val=1ll*Segt[now].val*Segt[rs].val%MOD;
24 }
25
26 void Update(int &now,int l,int r,int x,int k)
27 {
28 if (!now) now=++sgt_num;
29 if (l==r) {Segt[now].val=k; return;}
30 int mid=(l+r)>>1;
31 if (x<=mid) Update(Segt[now].ls,l,mid,x,k);
32 else Update(Segt[now].rs,mid+1,r,x,k);
33 Pushup(now);
34 }
35 int main()
36 {
37 T=read();
38 while (T--)
39 {
40 memset(Segt,0,sizeof(Segt));
41 sgt_num=0; Root=0;
42 q=read(); MOD=read();
43 for (int i=1; i<=q; ++i)
44 {
45 opt=read(); m=read();
46 if (opt==1) Update(Root,1,q,i,m);
47 else Update(Root,1,q,m,1);
48 printf("%d\n",Segt[Root].val);
49 }
50 }
51 }