题目内容

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;
}
最后修改日期:2020年3月10日

作者

留言

撰写回覆或留言

发布留言必须填写的电子邮件地址不会公开。