<题解>[JSOI2008]最大数

洛谷的题目链接

看起来要维护一个很动态的结果啊

但是查询操作只有一个max,并且插入也是插到最后的,所以我们直接来一个长度无限的初始序列,每个值均为最小值,然后插入改成把第x位改成某个数字,然后随便维护一下区间最大值什么的就好了。

当然如果嫌线段树麻烦也可以用树状数组,只不过树状数组维护前缀最大值很方便,所以我们修改数字可以从后到前修改然后把查询后L个数乱转换一下就好了,速度变快,代码量极度减少。

struct TreeArr
{
    long long val[N + 10];
    inline void init(void)
    {
        for (int i = 1; i < N; ++i)
            val[i] = -__LONG_LONG_MAX__;
    }
    inline void set(int pos, long long v)
    {
        for (; pos <= N; pos += -pos & pos)
            val[pos] = std::max(val[pos], v);
    }

    inline long long get(int pos)
    {
        long long ret = -__LONG_LONG_MAX__;
        for (; pos; pos -= -pos & pos)
            ret = std::max(val[pos], ret);
        return ret;
    }
}ta;

int count;

inline long long query(int p) { return ta.get(N - count + 1 + p - 1); }

inline void update(long long v) { ta.set(N - (++count) + 1, v); }

int main(void)
{
    ta.init();
    T = read, D = read;
    while (T--)
    {
        char buf[4];
        scanf("%s", buf);
        long long get = read;
        if (*buf == 'Q')
            printf("%lld\n", C = query(get));
        else
            update((get + C) % D);
    }
}
点赞

发表评论

电子邮件地址不会被公开。必填项已用 * 标注