题意：初始序列为1，两种操作，一种区间所有数 * 2， 一种是区间所有数 * 3 ，问最后所有数的最大公约数
题解：区间乘+区间GCD肯定不对，因为有取模操作，对乘积结果取模再求GCD肯定不对了
然后就想到维护每个结点乘2的次数和乘3的次数，分别取最小值就好了 ，ans=*,x,y分别是区间最小2的个数和3的个数
线段树区间修改+最小值
细节：快速幂记得开 LL，中间会爆int
#include <bits/stdc++.h> #define ll long long using namespace std; const int maxn = 1e5 + 5; const int INF = 0x3f3f3f3f; const int mod = 998244353; int sum2[maxn*4],lazy2[maxn*4]; int sum3[maxn*4],lazy3[maxn*4]; void pushdown(int l,int r,int p,int sum[],int lazy[]){ int mid=(l+r)/2; int pp=p; if(lazy[p]){ sum[p<<1]+=lazy[p]; sum[p<<1|1]+=lazy[p]; lazy[p<<1]+=lazy[p]; lazy[p<<1|1]+=lazy[p]; lazy[p]=0; } } void build(int l, int r,int p){ sum2[p]=sum3[p]=0; lazy2[p]=lazy3[p]=0; if(l==r){ return ; } int mid=(l+r)/2; build(l,mid,p<<1); build(mid+1,r,p<<1|1); } void update(int l,int r,int L,int R,int p,int sum[],int lazy[]){ if(L<=l&&r<=R){ sum[p]+=1; lazy[p]+=1; return ; } pushdown(l,r,p,sum,lazy); int mid=(l+r)/2; if(L<=mid) update(l,mid,L,R,p<<1,sum,lazy); if(R>mid) update(mid+1,r,L,R,p<<1|1,sum,lazy); sum[p]=min(sum[p<<1],sum[p<<1|1]); } int query(int l,int r,int L,int R,int p,int sum[],int lazy[]){ if(L<=l&&r<=R){ return sum[p]; } pushdown(l,r,p,sum,lazy); int mid=(l+r)/2; int ans=INF; if(L<=mid) ans=min(ans,query(l,mid,L,R,p<<1,sum,lazy)); if(R>mid) ans=min(ans,query(mid+1,r,L,R,p<<1|1,sum,lazy)); return ans; } ll pow(ll a,int b){ ll ans=1; while(b){ if(b&1) ans=ans*a%mod; a=a*a%mod; b=b/2; } return ans%mod; } int main(){ int t; scanf("%d",&t); while(t--){ int n; scanf("%d",&n); int m; scanf("%d",&m); build(1,n,1); while(m--){ int l,r,x; scanf("%d%d%d",&l,&r,&x); if(x==2) update(1,n,l,r,1,sum2,lazy2); else update(1,n,l,r,1,sum3,lazy3); } int xx=query(1,n,1,n,1,sum2,lazy2); int yy=query(1,n,1,n,1,sum3,lazy3); ll ans=pow(2*1ll,xx)*pow(3*1ll,yy)%mod; printf("%lld\n",ans); } return 0; } /* 2 5 3 1 3 2 3 5 2 1 5 3 6 3 1 2 2 5 6 2 1 6 2 */
