luoguP1198 [JSOI2008]最大数
阅读原文时间:2023年07月12日阅读:1

https://www.luogu.org/problem/P1198

经过老师的讲解,惊人的发现这题有用更简单数据结构维护的解法,而越简单的数据结构(如果能够用的话),越好(实现和思维上都会好一些)。

首先,这题是强制在线的,而这类题,如果你RE了,那么说明一般是你前面加密的东西求错了(比如这题的t)。

现在进入正题:

因为题目中需要输出的是后L个数的max,我们考虑两个数x,y, 满足x < y,如果高度还a[x] < a[y], 那么a[x]就一定不会成为答案(无论x,y在没在L内)。

所以我们维护一个保存着可能为答案的点的编号的单调队列,即维护a[i]递减的,关于 i 的单调队列(因为答案要的是后L个的,所以你要维护的是编号,并且还需要一个二分来找答案)。

现在请求你维护一个数列,要求提供以下两种操作:

1、 查询操作。

语法:Q L

功能:查询当前数列中末尾L个数中的最大的数,并输出这个数的值。

限制:L不超过当前数列的长度。(L > 0)

2、 插入操作。

语法:A n

功能:将n加上t,其中t是最近一次查询操作的答案(如果还未执行过查询操作,则t=0),并将所得结果对一个固定的常数D取模,将所得答案插入到数列的末尾。

限制:n是整数(可能为负数)并且在长整范围内。

注意:初始时数列是空的,没有一个数。

操作数 <= \(2 * 10^5\)

本来是找线段树的题目做的,但这题明显大材小用了….为什么呢?

我们注意到,它插入的时候只会把这个数插到数列的末尾,而且查询的时候也只是会查询后L个数。

于是,我们可以用一个反向的st表来维护(这个是在看了题解一之后想到的…惭愧…)(反向st即表示st[i] [j]为[i-(1<<j)+1, i]的最大值)

先想怎么插入,即插入之后需要改变哪些东西。好好想想“查询后L个数中的最大值”, 得出这个st表的右边界一定是n(数的个数), 所以,我们想到了反向st表,因为这样,我们唯一需要改变的量就是st[n] […], n前面的数的st都不用修改,因为我们是反向的啊。

再想想怎么查询, 只要你把你脑子 思想倒过来,反向实现RMQ即可。

#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cmath>
using namespace std;
#define ll long long
#define MAX 200000+9

int n,m;
ll f[MAX][21], a[MAX], D;//f[i][j]表示[i-(1<<j)+1, i]的最大值

void putback(int x) {
    f[x][0] = a[x];// 别忘了放到最后
    for(int i = 1; x-(1<<i)+1 >= 1; i++) {
        f[x][i] = max(f[x][i-1], f[x-(1<<(i-1))][i-1]);
    }
}

ll RMQ(int l, int r) {
    int k = 0;
    while((1<<(k+1) <= r-l+1)) k++;
    return max(f[r][k], f[l+(1<<k)-1][k]);//始终是反向思考
}

int main() {
    scanf("%d%lld",&m,&D);
    char cmd;
    ll x, t = 0;
    for(int i = 1; i <= m; i++) {
        cin>>cmd;
        if(cmd == 'A') {
            scanf("%lld",&x);
            a[++n] = (x+t)%D;
            putback(n);
        } else {
            int L;
            scanf("%d", &L);
            if(L == 1) {
                printf("%lld\n", a[n]);
                t = a[n];
                continue;
            }
            ll ans;
            ans = RMQ(n-L+1, n);
            printf("%lld\n", ans);
            t = ans;
        }
    }
    return 0;
}

手机扫一扫

移动阅读更方便

阿里云服务器
腾讯云服务器
七牛云服务器

你可能感兴趣的文章