【题解】[TJOI 2018] 数学计算（线段树）

本文主要是介绍【题解】[TJOI 2018] 数学计算（线段树），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题面

【题目描述】
小豆现在有一个数 $x$ ，初始值为 $1$ . 小豆有 $Q$ 次操作，操作有两种类型:
$1$ $m :$ $x = x * m$ ，输出 $x$ % $m o d$ ;
$2$ $p o s :$ $x = x$ / 第 $p o s$ 次操作所乘的数（保证第 $p o s$ 次操作一定为类型 $1$ ，对于每一个类型 $1$ 的操作至多会被除一次），输出 $x$ % $m o d$
【输入】
一共有 $t$ 组输入（ $\leq 5$ ）
对于每一组输入，第一行是两个数字 $Q, m o d$ ( $\leq 100000, mod \leq 1000000000$ );
接下来 $Q$ 行，每一行为操作类型 $o p$ ，操作编号或所乘的数字 $m$ （保证所有的输入都是合法的）.
$1 \leq Q \leq 100000$
【输出】
对于每一个操作，输出一行，包含操作执行后的 $x$ % $m o d$ 的值
【样例输入】

1 
10 1000000000 
1 2 
2 1 
1 2 
1 10 
2 3 
2 4 
1 6 
1 7 
1 12 
2 7

【样例输出】

算法分析

隐藏的线段树。
纯模拟肯定不行，long long也存不下，只有高精度。需要注意，题目要求输出时取模，但是求解的时候不取模，如果一边取模一边计算就会出现取模为0后，乘以任何数都是0。
因为除法除的数都是乘过的数，那么其实可以只看乘法。例如除以第k次的乘数s，可以看作第k次乘以了1。这样，我们就将整个操作全部变成了乘法。题目就变成了，每次乘以一个数，输出结果取模。
我们需要将这些乘数都保存下了，同时要进行修改，就使用线段树。
构造一个1~n的全为1的序列A。第k次乘以数s，就将序列A[k]=s，第k次处于第t次的乘数，就将A[t]=1。
就是线段树的一个单点修改。最后的答案就是线段树的根节点S[1]，包含了所有乘数的和。

参考程序

#include <bits/stdc++.h>
using namespace std;
int n,m,T;
long long s[500010];
void built(int k,int l,int r)	//所有结点初始化为1 
{s[k]=1;if(l==r) return;int mid=(l+r)/2;built(k*2,l,mid);built(k*2+1,mid+1,r);
}
void change(int k,int l,int r,int x,int v)
{if(l==r&&x==l){s[k]=v;return;}int mid=(l+r)/2;if(l<=x&&x<=mid) change(k*2,l,mid,x,v);if(mid+1<=x&&x<=r) change(k*2+1,mid+1,r,x,v);s[k]=((s[k*2]%m)*(s[k*2+1]%m))%m;
}
int main()
{scanf("%d",&T);while(T--){scanf("%d%d",&n,&m);built(1,1,n);	//建立一个1~n的序列，全部为1，表示第i次乘的数 int x,y;for(int i=1;i<=n;i++){scanf("%d%d",&x,&y);if(x==1) change(1,1,n,i,y);	//第i次乘以y else change(1,1,n,y,1);	//除以第y次的乘数，即将其乘数变为1 printf("%lld\n",s[1]);//s[1]就是1~i所有乘数的乘积 }} return 0;
}