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
#include<iostream>
#include<cstring>
#include<cstdio>
#define N (100009)
using namespace std; struct Sgt{int val,ls,rs;}Segt[N*];
int T,q,MOD,sgt_num,Root,opt,m; inline int read()
{
int x=,w=; char c=getchar();
while (c<'' || c>'') {if (c=='-') w=-; c=getchar();}
while (c>='' && c<='') x=x*+c-'', c=getchar();
return x*w;
} void Pushup(int now)
{
Segt[now].val=;
int ls=Segt[now].ls,rs=Segt[now].rs;
if (ls) Segt[now].val=1ll*Segt[now].val*Segt[ls].val%MOD;
if (rs) Segt[now].val=1ll*Segt[now].val*Segt[rs].val%MOD;
} void Update(int &now,int l,int r,int x,int k)
{
if (!now) now=++sgt_num;
if (l==r) {Segt[now].val=k; return;}
int mid=(l+r)>>;
if (x<=mid) Update(Segt[now].ls,l,mid,x,k);
else Update(Segt[now].rs,mid+,r,x,k);
Pushup(now);
}
int main()
{
T=read();
while (T--)
{
memset(Segt,,sizeof(Segt));
sgt_num=; Root=;
q=read(); MOD=read();
for (int i=; i<=q; ++i)
{
opt=read(); m=read();
if (opt==) Update(Root,,q,i,m);
else Update(Root,,q,m,);
printf("%d\n",Segt[Root].val);
}
}
}