P4588 [TJOI2018]数学计算
题目大意
给定 $x = 1$ 和某个模数 $MO$，有两种操作（共 $Q \le 10^5$ 次）
操作 $1$：把 $x = x*v % MO$
操作 $2$：取消第 $k$ 次操作（取消的必为操作 $1$，且某个操作 $1$ 只会最多被取消一次）
每次操作结束输出 $x$ 的值。
简要题解
因为模数不是固定的，因此处理模下除法是不方便的，因此直接用线段树维护所有操作即可。
最初把整个区间初始化为 $1$。
对于第 $i$ 次操作：
如果是操作 $1$，就把 $i$ 位置设置为 $v$
如果是操作 $2$，就把 $x$ 位置设置为 $1$
某次操作完后的结果就是整个区间的积。
其实题目中的输入是不会爆 $int$ 的，但是两个 $int$ 模下的积有可能爆，只要注意处理积的就可以了。
复杂度
$T$：$O(N \log N)$
$S$：$O(N)$
代码实现
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int M=1e5+5;
int MO;
int mul(int x,int y)
{
return 1LL*x*y%MO;
}
struct SegT
{
int tn[M*4];
void init()
{
for(int i=0;i<M*4;i++)
tn[i]=1;
}
int P,V;
void update(int o,int l,int r)
{
if(l==r)
{
tn[o]=V;
return;
}
int mid=(l+r)>>1;
if(P<=mid) update(o<<1,l,mid);
else update(o<<1|1,mid+1,r);
tn[o]=mul(tn[o<<1],tn[o<<1|1]);
}
}segt;
void solve()
{
int q;
scanf("%d%d",&q,&MO);
segt.init();
int con;
int x;
for(int i=1;i<=q;i++)
{
scanf("%d%d",&con,&x);
// cout<<x<<" "<<x%MO<<endl;
if(con==1)
{
segt.P=i;
segt.V=(int)x%MO;
segt.update(1,1,q);
}
else
{
segt.P=x;
segt.V=1%MO;
segt.update(1,1,q);
}
printf("%d\n",segt.tn[1]);
}
}
int main()
{
int t; scanf("%d",&t);
while(t--)
solve();
return 0;
}
Next: 《汇编语言》 笔记 实验 1 查看 CPU 和内存，用机器指令和汇编指令编程