#include<bits/stdc++.h>
using namespace std;
#define int long long
#define lp (p*2)
#define rp (p*2+1)
const int N=1e5+10;
struct nd{int l,r,s;}tr[N*4];int M;
void pushup(int p){tr[p].s=(tr[lp].s*tr[rp].s)%M;}
void bt(int p,int l,int r)
{
	tr[p]={l,r,1ll};
	if(l==r)return; 
	int m=(l+r)/2;
	bt(lp,l,m);bt(rp,m+1,r);
}
void chg(int p,int x,int k)
{
    if(x<tr[p].l||tr[p].r<x)return;
	if(tr[p].l==tr[p].r){tr[p].s=k;return;}
	chg(lp,x,k);chg(rp,x,k);
	pushup(p);
}
signed main()
{
	int T;scanf("%lld",&T);
	while(T--)
	{
		int n;scanf("%lld%lld",&n,&M);bt(1,1,n);
		for(int i=1,op,x;i<=n;i++)
		{
			scanf("%lld%lld",&op,&x);
			if(op==1)chg(1,i,x);
			else chg(1,x,1);
			printf("%lld\n",tr[1].s);
		}
	}
	return 0;
}

$$\color{green}{\text{思维题——洛谷P4588\ \ \ \ \ [TJOI2018]数学计算}}$$

$\color{blue}{\text{【题目】：}}$ 你有一个数 $x$，初始为 $1$。你有两种操作，分别为：

• 1. 给定一个数 $m$，把 $x$ 变成 $x \times m$，然后输出 $x$ 对 $\text{mod}$ 取模的值。
• 2. 给定一个数 $t$，把 $x$ 变为 $x/$ 第 $t$ 次操作所乘的数。如第 $t$ 次操作所乘数为 $2$，则把 $x$ 变为 $\dfrac{x}{2}$。数据保证第 $t$ 次操作一定是操作 $1$，且每个操作最多被除一次，即保证 $x$ 在任何时候都是一个整数。操作后，输出 $x$ 对 $\text{mod}$ 取模的值。

$\color{blue}{\text{【思路】：}}$ 直接模拟会因为爆 long long 的问题导致代码非常复杂，甚至无法编写。

考虑强大的数据结构——线段树。建立一棵线段树，其叶子节点都是对于的乘数，每个非叶子节点的值为其左右儿子的值的乘积对 $\text{mod}$ 取模的值。这样，任意时候都有 $x=$ 该线段树的根的值。

操作 $1$ 可以直接上，操作 $2$ 可以看做是把第 $t$ 次的乘数改为 $1$。因此，我们只需要打一个线段树修改即可。

$\color{blue}{\text{【代码】：}}$

const int N=1e5+100;
#define ll long long
ll mod;int tot,G[N];
int test_number,q;
struct Segment_tree{
	ll sum[N<<2];//记得4倍空间 
	inline void pushup(int o){
		sum[o]=sum[o<<1]*sum[o<<1|1]%mod;
	}
	inline void build(int o,int l,int r){
		if (l==r){sum[o]=1ll;return;}
		register int mid=(l+r)>>1;
		build(o<<1|1,mid+1,r);
		build(o<<1,l,mid);
		pushup(o);return;
	}
	void updata(int o,int l,int r,int p,ll v){
		if (l==r){sum[o]=v;return;}
		register int mid=(l+r)>>1;
		if (p<=mid) updata(o<<1,l,mid,p,v);
		else updata(o<<1|1,mid+1,r,p,v);
		pushup(o);return;
	}
}SGT;
#define gc getchar()
#define g(c) isdigit(c)
inline ll read(){
	char c=0;ll x=0;bool f=0;
	while (!g(c)) f=c=='-',c=gc;
	while (g(c)) x=x*10+c-48,c=gc;
	return f?-x:x;
}
namespace fast_write{
	void write(ll a,bool b){
		if (a==0){
			if (b) putchar('0');
		}
		else{
			write(a/10,false);
			putchar(a%10+'0');
		}
	}
	void print(ll a,char c){
		write(a,true);
		putchar(c);
	}
}
int main(){
	test_number=read();
	while (test_number--){
		q=read();mod=read();
		SGT.build(1,1,q);tot=0;
		memset(G,0,sizeof(G));
		for(int i=1;i<=q;i++){
			int opt=read();ll t=read();
			if (opt==2) SGT.updata(1,1,q,G[t],1);
			else SGT.updata(1,1,q,G[i]=(++tot),t%mod);
			fast_write::print(SGT.sum[1]%mod,'\n');
		}
	}
	return 0;
}

祝笔者和大家都可以 AK IOI！

C29 线段树 P4588 [TJOI2018] 数学计算

#include<bits/stdc++.h>
using namespace std;
#define lc(p) (p<<1)
#define rc(p) (p<<1|1)
typedef long long LL;
const int N= 1e5+10;
struct trnode{int l,r;LL s;}tr[N*4];LL M;
void pushup(int p){tr[p].s=(tr[lc(p)].s*tr[rc(p)].s)%M;}
void bt(int p, int l, int r)
{
	tr[p]=trnode{l,r,1};if(l==r)return; 
	int m=(l+r)/2;
	bt(lc(p),l,m);bt(rc(p),m+1,r);
}
void change(int p, int x, LL k)
{
    if(x<tr[p].l || tr[p].r<x) return ;
	if(tr[p].l==tr[p].r){tr[p].s=k;return;}
	change(lc(p),x,k);change(rc(p),x,k);
	pushup(p);
}
int main()
{
	int T;scanf("%d",&T);
	while(T--)
	{
		int n;scanf("%d%lld",&n,&M);
		bt(1,1,n);
		for (int i=1,op,x;i<=n;i++)
		{
			scanf("%d%d",&op,&x);
			if(op==1)change(1,i,x);
			else     change(1,x,1);
			printf("%lld\n",tr[1].s );
		}
	}
	return 0;
}