牛客-热身小游戏

题目链接：热身小游戏

第一种写法：线段树

介绍第二种写法：并查集

对于一些已经查询过的点，我们可以往后跳，进行路径压缩，他们的父亲为下一个点。

a数组记录[ l , r ] 之间的乘积，初始值为1。

代码：

#include <bits/stdc++.h>
#define int long long
#define fi first
#define se second
using namespace std;
const int inf = 0x3f3f3f3f3f3f3f3f;
const int N = 3e5+5;
const int mod = 1e9+7;
int q;
int pre[N];
int a[N];int root(int x){return pre[x]=(pre[x]==x)?x:root(pre[x]);
}int qmi(int a,int b){int res = 1;while(b){if(b&1)res = (res*a)%mod;b>>=1;a=(a*a)%mod;}return res;
}void solve(){int ans = 1;cin>>q;for(int i=1;i<=q;i++){a[i] = 1;pre[i] = i;}for(int i=1;i<=q;i++){int op;cin>>op;if(op==1){int x;cin>>x;a[i] = x;ans = ans * x %mod;}else if(op==2){int l,r;cin>>l>>r;int x = l;while(root(x)<=r){x = root(x);ans = ans * qmi(a[x],mod-2) %mod;pre[x] = x+1;}}else{cout<<ans<<"\n";}}}signed main(){ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);int t=1;while(t--){solve();}return 0;
}