ST表本身是不可修改的。

如果考虑增加一个数，可以把ST表反过来写，即f[i][j]表示i往前1<<j个数，一个数最多影响logn个数，常数非常小。

 

#include
     
      #include
      
       #include
       
        using namespace std;const int MAXN=200005;typedef long long ll;inline ll rd(){    ll ret=0,f=1;char c;    while(c=getchar(),!isdigit(c))f=c=='-'?-1:1;    while(isdigit(c))ret=ret*10+c-'0',c=getchar();    return ret*f;}ll f[MAXN][32];ll m,mod;int p;int main(){    m=rd();mod=rd();    char s[5];ll x,t=0;    while(m--){        scanf("%s",s);x=rd();        if(s[0]=='Q') {            int len=log2(x);            printf("%lld\n",t=max(f[p][len],f[p-x+(1<
        
         =0;i++) f[p][i]=max(f[p][i-1],f[p-(1<<(i-1))][i-1]);        }    }    return 0;}