题解 P1198 【[JSOI2008]最大数】

· · 题解

扫一眼题面：这不是一道线段树板子题吗？

然而数据过水导致暴力n方能过？ 请求管理加强数据QAQ

所以我们还是要用正解来做这一道题啦（线段树求区间最大值）！

主要内容是单点修改和区间查询，尤其要主要L==0的情况，不然会RE

这是用线段树做这道题的结果

这道题和线段树模板不同的是，我们的线段树的底部每次都需要新插入一个值，实际上就是对一个值为0的地方作出单点修改。也就是下面的代码：

void pplus(long long p,long long l,long long r,long long w,long long v){//加入函数
    if(l==r){t[p]=v;return;}//如果到了底部，直接赋值
    long long mid=(l+r)/2;//取中点
    if(w<=mid)pplus(p*2,l,mid,w,v);//如果在左边查询左节点
    else pplus(p*2+1,mid+1,r,w,v);//同上
    t[p]=max(t[p*2],t[p*2+1]);//当前点的值等于两个儿子节点中较大的值
}

如图（我相信关于这一点许多线段树题解都没有写到）：

#include<bits/stdc++.h>
using namespace std;
long long modd,m,tt,line;//modd:模数 m:操作数 line:长度 tt：题中t
long long t[2000001];//线段树，存最大值
//十年OI一场空，不开long long……
inline long long read(){//快读优化数据读入（数据大不能忘记）
    long long f=1,outt=0;char a=getchar();
    while(a>'9'||a<'0'){if(a=='-')f=-1;a=getchar();}
    while(a<='9'&&a>='0'){outt*=10;outt+=a-'0';a=getchar();}
    return f*outt;
}
void js(long long p,long long l,long long r){//初始化建树
    t[p]=-0x3ffffffff;//赋极小值
    if(l==r)return;
    long long mid=(l+r)/2;
    js(p*2,l,mid);//向左节点修改
    js(p*2+1,mid+1,r); //向右节点修改
}
long long ask(long long p,long long l,long long r,long long nl,long long nr){//查询函数
    if (nl<=l&&r<=nr)return t[p];//如果区间被包含，返回最大值
    long long mid=(l+r)/2;//取中点
    long long minn=-0x3ffffffff;//赋极小值
    if (nl<=mid)minn=ask(p*2,l,mid,nl,nr);//如果查询区间左节点大于等于mid，查询左区间
    if (nr>mid)minn=max(minn,ask(p*2+1,mid+1,r,nl,nr));//同上
    return minn;//返回最小值
}
void pplus(long long p,long long l,long long r,long long w,long long v){//加入函数
    if(l==r){t[p]=v;return;}
    long long mid=(l+r)/2;
    if(w<=mid)pplus(p*2,l,mid,w,v);
    else pplus(p*2+1,mid+1,r,w,v);
    t[p]=max(t[p*2],t[p*2+1]);
}
int main(){
    m=read(),modd=read();//读入操作数和模数
    for(int i=1;i<=m;i++){
        char s;//读取操作
        cin>>s;
        if(s=='A'){
            long long ls=read();
            line++;//长度++，记录当前值是第几个
            pplus(1,1,m,line,(tt+ls)%modd);//将新的值加入线段树
        }
        else {
            long long ls=read();
            if(!ls)tt=0;//如果查询为空，直接得到答案
            else
            tt=ask(1,1,m,line-ls+1,m);//进入查找
            printf("%lld\n",tt);
        }
    }
    return 0;//成功AC！
}