题解【洛谷P4588】[TJOI2018]数学计算

题目描述

小豆现在有一个数(x)，初始值为(1).小豆有(Q)次操作，操作有两种类型:

(1;m)：(x=x imes m)输出(x\%mod);

(2;pos)：(x= x/)第(pos)次操作所乘的数（保证第(pos)次操作一定为类型(1),对于每一个类型(1)的操作至多会被除一次）输出(x\%mod);

输入格式

一共有(t)组输入((tleq5));

对于每一组输入,第一行是两个数字(Q,mod)((Qleq100000,modleq100000000));

接下来(Q)行，每一行为操作类型(op),操作编号或所乘的数字(m)（保证所有的输入都是合法的）.

输出格式

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

输入输出样例

输入 #1

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

输出 #1

说明/提示

对于(20\%)的数据，(1leq Qleq500)

对于(100\%)的数据，(1leq Qleq100000)

题解

这道题目难在思维，难在怎么想到线段树。

暴力模拟很容易想到，但是，在此题中，暴力模拟是错误的！！！

一组( exttt{hack})数据：

输出应为：

9
1

貌似用高精度就可以了，但空间复杂度感人……~~

这里直接讲正解。

用一颗线段树维护操作的区间乘积，如果是(1)操作就将当前节点的值改为(m)，(2)操作就把要除的数所在的节点的值改为(1)。

输出的话……直接输出线段树根节点的值即可。

代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#define int long long//注意long long
#define itn int
#define gI gi

using namespace std;

inline int gi()//快读
{
	int f = 1, x = 0; char c = getchar();
	while (c < '0' || c > '9') {if (c == '-') f = -1; c = getchar();}
	while (c >= '0' && c <= '9') {x = x * 10 + c - '0'; c = getchar();}
	return f * x;
}

int t, q, mod, tr[400003], ans;

inline int ls(int p) {return p << 1;}//左儿子
inline int rs(itn p) {return p << 1 | 1;}//右儿子

void modify(int ql, int qr, int z, int l, int r, int p)//修改节点
{
	if (l == r && l == ql) {tr[p] = z; return;}//到了叶子节点进行修改
	int mid = (l + r) >> 1;
	if (ql <= mid) modify(ql, qr, z, l, mid, ls(p));//递归左子树
	if (qr > mid) modify(ql, qr, z, mid + 1, r, rs(p));//递归右子树
	tr[p] = (tr[ls(p)] % mod * tr[rs(p)] % mod) % mod;//上传节点
	return;
}

signed main()
{
	t = gi();
	while (t--)
	{
		q = gi(), mod = gi();
		for (int i = 1; i <= 400001; i+=1) tr[i] = 1;//注意,本题中不需要建树,只需要把所有节点的值设为1
		for (int i = 1; i <= q; i+=1)
		{
			int op = gi(), m = gi();
			if (op == 1) modify(i, i, m, 1, q, 1);//操作1,将第i个点的值修改为m
			else modify(m, m, 1, 1, q, 1);//操作2,将第m个点的值修改为1
			printf("%lld
", tr[1]);//输出
		}
	}
	return 0;
}