题解 P1198 【[JSOI2008]最大数】

exit0 · 2020-01-26 12:40:15 · 题解

让我们来挑战一下线段树最短代码！

AC记录

起初，我打了一个大暴力，思路就是每一次更新重新建一次线段树，就像这个样子：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define N 10000100
inline int read ()
{
    int ans=0;
    int flag=1;
    char ch=getchar();
    while(ch<'0'||ch>'9')
    {
        if(ch=='-')flag=-1;
        ch=getchar ();
    }
    while(ch>='0'&&ch<='9')ans=(ans<<1)+(ans<<3)+(ch^48),ch=getchar ();
    return ans*flag;
}
int mx[N*3];int a[N];
inline void Build( int k , int l , int r )
{
    if(l==r)
    {
        mx[k]=a[l];
        return ;
    }
    int mid=l+r>>1;
    Build(k*2,l,mid);
    Build(k*2+1,mid+1,r);
    mx[k]=max(mx[k*2],mx[k*2+1]);
    return ;
}
inline int ask_max( int k , int l , int r , int x, int y )
{
    if(l==x&&r==y)return mx[k];
    int mid=l+r>>1;
    if(y<=mid)return ask_max(k*2,l,mid,x,y);
    if(x>mid)return ask_max(k*2+1,mid+1,r,x,y);
    return max( ask_max(k*2,l,mid,x,mid), ask_max(k*2+1,mid+1,r,mid+1,y) );
}
int m,d,x,n,now;
char op;
int main ()
{
    m=read();d=read();
    for(int i=1;i<=m;i++)
    {
        cin>>op;
        if(op=='A')
        {
            x=read();
            x+=now;
            x%=d;
            a[++n]=x;
            Build(1,1,n);
            continue;
        }
        //if(op=='Q')
        x=read();
        now=ask_max(1,1,n,n-x+1,n);
        printf("%d\n",now);
    }
    return 0;
}

emmm，只过了两个点，其余的TLE。

在尝试暴力失败后，开始打正解，标准的单点修改，区间查询线段树。

先说说在此题中线段树的几种操作：

区间查询：

inline int ask_max( int k , int l , int r , int x, int y )
{
    if(l==x&&r==y)return mx[k];
    int mid=l+r>>1;
    if(y<=mid)return ask_max(k<<1,l,mid,x,y);
    if(x>mid)return ask_max(k<<1|1,mid+1,r,x,y);
    return max( ask_max(k<<1,l,mid,x,mid),   ask_max(k<<1|1,mid+1,r,mid+1,y) );
}

单点修改：

void Build(int k,int l,int r,int x)
{
    if(l==r&&l==x)
    {
    mx[k]=a[l];return;
    }
    int mid=l+r>>1;
    if(x<=mid) Build(k*2,l,mid,x);
    else Build (k*2+1,mid+1,r,x);
    mx[k]=max(mx[k*2],mx[k*2+1]);
}

然后，记录一下查询得到的答案，方便在下一次用，查询的范围可以从1到m，AC代码如下：

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
int mx[10000100*3],a[10000100],m,d,x,n,now;char op;
inline void Build(int k,int l,int r,int x)
{
    if(l==r&&l==x)
    {
    mx[k]=a[l];return;
    }
    int mid=l+r>>1;
    if(x<=mid) Build(k<<1,l,mid,x);
    else Build (k<<1|1,mid+1,r,x);
    mx[k]=max(mx[k<<1],mx[k<<1|1]);
}
inline int ask_max( int k , int l , int r , int x, int y )
{
    if(l==x&&r==y)return mx[k];
    int mid=l+r>>1;
    if(y<=mid)return ask_max(k<<1,l,mid,x,y);
    if(x>mid)return ask_max(k<<1|1,mid+1,r,x,y);
    return max( ask_max(k<<1,l,mid,x,mid), ask_max(k<<1|1,mid+1,r,mid+1,y) );
}
int main ()
{
    cin>>m>>d;
    for(int i=1;i<=m;i++)
    {
        cin>>op;
        if(op=='A')
        {
            cin>>x,x+=now,x%=d,a[++n]=x;
            Build(1,1,m,n);
            continue;
        }
        cin>>x;
        now=ask_max(1,1,m,n-x+1,n);
        printf("%d\n",now);
    }
}

这样就AC了，望采纳~