洛谷刷题笔记——P4588 [TJOI2018]数学计算

题目传送门

[TJOI2018]数学计算

题目描述

小豆现在有一个数 $x$，初始值为 $1$。小豆有 $Q$ 次操作，操作有两种类型：

1 m：将 $x$ 变为 $x\times m$，并输出 $x\mathrm{mod}M$

2 pos：将 $x$ 变为 $x$ 除以第 $pos$ 次操作所乘的数（保证第 $pos$ 次操作一定为类型 1，对于每一个类型 1 的操作至多会被除一次），并输出 $x\mathrm{mod}M$。

输入格式

一共有 $t$ 组输入。

对于每一组输入，第一行是两个数字 $Q,M$。

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

输出格式

对于每一个操作，输出一行，包含操作执行后的 $x\mathrm{mod}M$ 的值。

样例 #1

样例输入 #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

2
1
2
20
10
1
6
42
504
84

提示

对于 $20\%$ 的数据，$1\le Q\le 500$。

对于 $100\%$ 的数据，$1\le Q\le 10^5$，$t\le 5,M\le 10^9$，$0<m\le 10^9$。

思路

首先说明本题为什么不能通过暴力模拟解决：显然，如果不将x对M取模，在执行若干次1操作后，x很可能会超过整型的表示范围。如果，在每次执行1操作后，都将x对M取模，则取模后的x可能会丢失某个因子m_i，如果以后的操作要求x/m_i，显然，此时将不能整除，产生错误！

本题可以通过线段树来解决：叶子结点记录1操作带来的因子m（根据操作的序号修改对应叶子的结点的值），中间结点记录区间乘积，并对M取模。具体来说，当第i个操作1 m到来后，就执行函数将l==r && l==i的叶子结点的值修改为m，即modify(1, i, i, m)；当第j个操作2 m到来后，就将l==r && l== m的叶子结点的值修改为$1$，即modify(1, m, m, 1)

具体细节见代码

代码

#include
#define maxn 100005
#define int long long 
using namespace std;

int t, Q, M;

struct node{
	int l, r;
	int v;
}tree[maxn<<3];

void pushUp(int i){
	int lc = i<<1, rc = i<<1|1;
	tree[i].v = tree[lc].v*tree[rc].v;
	tree[i].v %= M;
}

void build(int i, int l, int r){
	tree[i].l = l, tree[i].r = r;
	if(l==r){
		tree[i].v = 1;
		return;
	}else{
		int mid = (l+r)>>1;
		build(i<<1, l, mid);
		build(i<<1|1, mid+1, r);
		pushUp(i);
	}
}

void modify(int i, int l, int r, int m){
	if(tree[i].l>r||tree[i].r<l){
		return;
	}else if(tree[i].l>=l&&tree[i].r<=r){
		tree[i].v = m;
	}else{
		modify(i<<1, l, r, m);
		modify(i<<1|1, l, r, m);
		pushUp(i);
	}
}

signed main(){
	cin>>t;
	while(t--){
		cin>>Q>>M;
		build(1, 1, Q);
		for(int i=1;i<=Q;i++){
			int op, m;
			cin>>op>>m;
			if(op==1){
				modify(1, i, i, m);
			}else{
				modify(1, m, m, 1);
			}
			cout<<tree[1].v<<'\n';
		}
	}
	return 0;
}