传送门

---

解析：

首先，这天坑的出题人。。。

思路肯定是线段树维护区间运算结果，但是两万多的模数怎么维护？

这奇怪的光速。。。光速不是$299792458m/s$吗？怎么会变成$29393$？

是的模数是这道题解决的关键，因为$29393=7\times 13\times 17\times 19$

所以我们只需要线段树维护这四个模数的结果，再用$CRT$合并一下就行了。

虽然说更新的常数有点大（40多），但是已经比两万多不知道好到哪里去了。

---

代码：

#include<bits/stdc++.h> using namespace std; #define ll long long #define re register #define gc getchar #define pc putchar #define cs const inline int getint(){ re int num; re char c; while(!isdigit(c=gc()));num=c^48; while(isdigit(c=gc()))num=(num<<1)+(num<<3)+(c^48); return num; } inline void outint(int a){ static char ch[13]; if(a==0)pc('0'); while(a)ch[++ch[0]]=a-a/10*10,a/=10; while(ch[0])pc(ch[ch[0]--]^48); } inline int quickpow(int a,int b,int mod,int ans=1){ for(;b;b>>=1,a=a*a%mod)if(b&1)ans=ans*a%mod; return ans; } inline char getop(){ re char c; while((c=gc())!='^'&&c!='*'&&c!='+'); return c; } cs int M=29393;//7*13*17*19 cs int N=100005; struct node{int remain[4][20];}t[N<<1],Ans; cs int mod[4]={7,13,17,19}; int remain[4]; int inv[4][20]; inline int CRT(){ int ans=0; for(int re i=0;i<4;++i) ans=(ans+(M/mod[i])*inv[i][(M/mod[i])%mod[i]]%M*remain[i]%M)%M; return ans; } inline int solve(char op,int val,int now,int mod){ switch(op){ case '+':return (val+now)%mod; case '*':return val*now%mod; case '^':return quickpow(now,val,mod); } } inline void pushup(int k){ for(int re i=0;i<4;++i){ for(int re j=0;j<mod[i];++j) t[k].remain[i][j]=t[k<<1|1].remain[i][t[k<<1].remain[i][j]]; } } inline void build(int k,int l,int r){ if(l==r){ char op=getop(); int val=getint(); for(int re i=0;i<4;++i){ for(int re j=0;j<mod[i];++j) t[k].remain[i][j]=solve(op,val,j,mod[i]); } return ; } int mid=(l+r)>>1; build(k<<1,l,mid); build(k<<1|1,mid+1,r); pushup(k); } inline void update(int k,int l,int r,cs int &pos){ if(l==r){ char op=getop(); int val=getint(); for(int re i=0;i<4;++i){ for(int re j=0;j<mod[i];++j) t[k].remain[i][j]=solve(op,val,j,mod[i]); } return ; } int mid=(l+r)>>1; if(pos<=mid)update(k<<1,l,mid,pos); else update(k<<1|1,mid+1,r,pos); pushup(k); } inline void solve(int x){ for(int re i=0;i<4;++i)remain[i]=t[1].remain[i][x%mod[i]]; outint(CRT()),pc('\n'); } int n,m; signed main(){ for(int re i=0;i<4;++i)inv[i][0]=inv[i][1]=1; for(int re j=0;j<4;++j){ for(int re i=2;i<mod[j];++i){ inv[j][i]=(mod[j]-mod[j]/i)*inv[j][mod[j]%i]%mod[j]; } } n=getint(); m=getint(); build(1,1,n); while(m--){ int op=getint(),x=getint(); switch(op){ case 1:{solve(x);break;} case 2:{update(1,1,n,x);break;} } } return 0; }