解题报告 P1198 [JSOI2008]最大数

题目内容

P1198

大意：维护一个初始为空的序列，支持以下两种操作：

• 查询最后 L 个数字中的最大数
• 将 n+t\bmod D 插入序列末尾，t 为上次查询的答案，初始为 0

解题思路

维护一个带修序列，很容易想到使用维护 RMQ 的线段树来解决问题。

每次查询操作就按照常规来，插入操作就相当于在最后一个位置加上了 n+t\bmod D，至于为什么用 cin 和 cout 是因为使用 scanf 出现了一些玄学错误。代码如下：

#include <iostream>
#define L (k<<1)
#define R (L|1)
typedef long long ll;
using namespace std;

inline ll max(ll a,ll b)
{
    return a>b?a:b;
}

const int maxn=2e5+5;
int m,d,tot;//tot存储当前序列元素个数
ll f[maxn<<2];

ll query(int i,int j,int x,int y,int k)//查询操作
{
    //printf("i:%d,j:%d,x:%d,y:%d,k:%d\n",i,j,x,y,k);
    if(i>=x &&j<=y)
        return f[k];
    int m=i+j>>1;
    ll ans=0;
    if(x<=m)
        ans=max(ans,query(i,m,x,y,L));
    if(y>m)
        ans=max(ans,query(m+1,j,x,y,R));
    return ans;
}

void add(int i,int j,int x,int k,int d)//单点修改操作
{
    if(i==j && i==x)
    {
        f[k]=d;
        return;
    }
    int m=i+j>>1;
    if(x<=m)
        add(i,m,x,L,d);
    else
        add(m+1,j,x,R,d);
    f[k]=max(f[L],f[R]);
    return;
}

int main()
{
    //freopen("1.out","w",stdout);
    ios::sync_with_stdio(false);
    cin>>m>>d;
    char c;
    int n=0,t=0;
    for(int i=1;i<=m;i++)
    {
        cin>>c>>n;
        if(c=='Q')
        {
            t=query(1,m,tot-n+1,tot,1);//查询[tot-n+1,tot]
            cout<<t<<endl;
        }
        if(c=='A')
            add(1,m,++tot,1,(n+t)%d);//插入操作
    }
    return 0;
}