题解 P1198 【[JSOI2008]最大数】

· · 题解

树状数组大法好

比线段树常数要小多了，而且代码量短，很容易写。

在结尾插入一个数的操作，可以转化为树状数组的单点更新。

一般树状数组是无法维护区间最大值的，因为最大值不满足区间减法。但注意到题目中的查询操作是末尾L个数，所以可以直接用下面的方式查询：

inline int query(int x){
    reg int res=0;
    for(;x;x-=lowbit(x))res=max(res,tr[x]);
    return res;
}

完整代码如下（111ms，目前2019年Rank1）。

#include<bits/stdc++.h>
using namespace std;
#define reg register
#define IOSIZE 10000000
static char in[IOSIZE],*p=in,out[IOSIZE],*q=out,ch[20],*t=ch;
inline char gc(){
    while(isspace(*p))++p;
    return *p++;
}
inline int read(){
    reg int x=0;reg char f=0;
    while(*p<48)f|=*p=='-',++p;
    while(*p>47)x=(x<<1)+(x<<3)+(*p++^48);
    return f?-x:x;
}
inline void write(int x){
    x<0&&(*q++='-',x=-x);
    !x&&(*q++=48,0);
    while(x)*t++=x%10+48,x/=10;
    while(t!=ch)*q++=*--t;
}
#define lowbit(x) (x&-x)
static int a[200001],tr[200001],n;
inline int query(int x){
    reg int res=0;
    for(;x;x-=lowbit(x))res=max(res,tr[x]);
    return res;
}
inline void upd(int l,int x){
    for(;l<200001;l+=lowbit(l))tr[l]=max(tr[l],x);
}
int main(){
    fread(in,1,IOSIZE,stdin);
    for(reg int M=read(),D=read(),t=0,tmp;M;--M){
        char c=gc();tmp=read();
        switch(c){
            case 'A':upd(200000-n,(tmp+t)%D);++n;break;
            case 'Q':t=query(200000-(n-tmp)),write(t),*q++='\n';
        }
    }fwrite(out,1,q-out,stdout);
    return 0;
}