这真的是道线段树……

题目描述

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

$1m:x=x\times m$ 输出 $x$%mod;

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

原题链接

Solve

说实话，一开始我是真没看出来这是道线段树。
以每一个时间节点作为叶子节点，，初始值都是1，区间求乘。

• 1操作就是在相应的时间节点，修改为$m$。
• 2操作就是在$pos$位置修改为1.

Code

#include<iostream>
#include<cstdio>
#include<cstring>
#define N 100010
#define ll long long
using namespace std;
ll t;
ll Q,mod;
ll st[N],cnt;
struct note{
	ll l,r,num;
}d[N*4];
ll op,pos;
void build(ll k,ll x,ll y){
	d[k].l=x;d[k].r=y;d[k].num=1; 
	if(x==y) return ;
	build(k*2,x,(x+y)/2);
	build(k*2+1,(x+y)/2+1,y);
}
void revise(ll k,ll x,ll z){
	if(d[k].l==d[k].r){
		d[k].num=z%mod;
		return ;
	}
	ll mid=(d[k].l+d[k].r)/2;
	if(x<=mid) revise(k*2,x,z);
	else revise(k*2+1,x,z);
	d[k].num=(d[k*2].num*d[k*2+1].num)%mod;
}
int main()
{
	scanf("%lld",&t);
	while(t--){
		scanf("%lld%lld",&Q,&mod);
		build(1,1,Q);
		for(ll i=1;i<=Q;i++){
			scanf("%lld%lld",&op,&pos);
			if(op==1) revise(1,i,pos);
			else revise(1,pos,1);
			printf("%lld\n",d[1].num);
		}
	}
	return 0;
}

后言

话说有大佬说，这个题不用建树，直接莽就行。可是不建树还是线段树吗？🙃