题解 P1198 【[JSOI2008]最大数】

· · 题解

看到了每次都在区间最后加入一个值,我想到了树状数组!

看了很多讨论和题解,发现都是用 线段树 或者 单调栈 或者 分块做的
但是我却想到的是用树状数组维护最大值,看看题解,竟然没有!!!
那我来水一篇树状数组的题解吧

首先我们需要明确的是,树状数组是支持区间减法操作的
区间减法的含义就是在已知 [1,l-1]和[1,r]的情况下可以求解出[l,r]的区间值
但是取max和求和操作是不一样的,求和支持区间减法,但是取max不支持.

这个时候就是展现人类智慧的时候了

我们可以分类讨论一下:
当max[1,r] \gt max[1,l-1] 时,我们可以推出 max[l,r] == max[1,r],因为max[1,l-1]不贡献最大值
当max[1,l-1] == max[1,r] 时,我们不能直接得到max[l,r] == max[1,r],因为max[1,l-1]参与贡献最大值了,但是我们可以枚举每个 i\in [l,r] 从中寻找最大值,而树状数组的优势就在于可以在i - l\gelowbit(i)直接获取max[i+1-lowbit(i) , i]

于是问题迎刃而解!!!

因为上面说的很明白,代码中就是上面分类讨论的实现,就没有再多费时间码字了(就是懒,没别的)

Code:

#include <algorithm>
#include <iostream>
#include <cstdio>

const int maxn = 2e5+7 ;
#define lowbit(x) (x & (-x))
using namespace std ;

int n,mod;
int T,tot;
int num[maxn];
//num[i]表示在i这个位置的数 
int t[maxn] ;
//t[]是树状数组,也就是储存max[1,i] 

inline int query(int l , int r)
{
    int ans = 0;
    while(l <= r)
    {
        ans = max(ans , num[r]) ;
        for(--r ; r-l >= lowbit(r) ; r-=lowbit(r))
        //枚举i的过程 
            ans = max(ans,t[r]);
    }
    return ans ;
}
inline void add(int x)
{
    num[++tot] = (x+T)%mod;
    t[tot] = max(num[tot],query(tot+1-lowbit(tot) , tot-1));
    //更新数状数组 
}

int main()
{
    scanf("%d%d",&n,&mod);
    while(n--)
    {
        char in;
        int x;
        cin >> in;
        scanf("%d",&x);
        if(in == 'A') add(x);
        else printf("%d\n",T=query(tot+1-x,tot));
    }
    没什么说的了 
}