自动搬运

查看原文

来自洛谷，原作者为

	SaoFish I'm a loser. 祈祷一天能如愿

搬运于2025-08-24 21:22:21，当前版本为作者最后更新于2018-02-22 14:29:24，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

2019.7.28

upd:今天突然发现了一个错误...真的非常抱歉，本人当时很菜（现在也是），请各位见谅

这道题中，st表应该是用$f[i][j]$表示区间$[i....i-(2^j)+1]$的最值，否则就不能支持插入一个数这样的修改了。

对此感到很抱歉

看了很多AC的OIer基本是用线段树的。

这里就感觉用线段树有点大材小用了。

这里我就讲一下ST表的方法。

题目有插入和询问两个操作。

注意看题面，每次的插入是无脑在序列的尾端插入的，所以就可以用ST表了。

那么，这是为什么呢？

我们先看ST表的定义：

ST算法是用来求解给定区间RMQ的最值，用**f[i][j]表示区间[i....i+(2^j)-1]**的最值。

从中我们可以看出，当在尾端插入一个新数时，并不会影响之前所建立的ST表。 所以我们就可以用log(n)的时间复杂度来修改ST表了。

附上代码。

#include <cstdio>
#include <cmath>
#include <iostream>
#include <cstring>
#define ll long long
using namespace std;
ll a[200001],f[200001][21],t,D;
int n,m;
bool flag;
void change(int u){  //用change函数来进行修改
    f[u][0]=a[u];
    for(int i=1;u-(1<<i)>=0;i++) f[u][i]=max(f[u][i-1],f[u-(1<<(i-1))][i-1]);
}
ll find(int x,int y){
    double t=log(y-x+1)/log(2);
    int K=t;
    return max(f[y][K],f[x+(1<<K)-1][K]);
}
int main(){
    memset(f,0,sizeof(f));
    scanf("%d%lld",&m,&D);
    for (int i=1;i<=m;i++){
        char c;
        cin>>c;
        ll x;
        if (c=='A'){  //根据题面的操作，注意细节。
            scanf("%lld",&x);
            a[++n]=(x+t)%D;
            change(n);
        }else{
            int L; scanf("%d",&L);
            ll ans;
            if (L==1){
                printf("%lld\n",a[n]);
                t=a[n]; continue;
            }
            ans=find(n-L+1,n);
            printf("%lld\n",ans); t=ans;
        }
    }
    return 0;
}

完结散花