【刷题】最大数

现在请求你维护一个数列，要求提供以下两种操作：

1、 查询操作。

语法：Q L

功能：查询当前数列中末尾L个数中的最大的数，并输出这个数的值。

限制：LL不超过当前数列的长度。(L > 0)(L>0)

2、 插入操作。

语法：A n

功能：将nn加上tt，其中tt是最近一次查询操作的答案（如果还未执行过查询操作，则t=0t=0)，并将所得结果对一个固定的常数DD取模，将所得答案插入到数列的末尾。

限制：nn是整数（可能为负数）并且在长整范围内。

注意：初始时数列是空的，没有一个数。

1>暴力

没有写过暴力，就永远不会知道暴力的分有多高，实际复杂度多小...

也许跟本题的单调性（都从末尾出发）有关吧

#include<cstdio>
#include<cstdlib>
#include<iostream>
using namespace std;
int m,mod;
const int N=200003;
int mx[N],len;

int main()
{
    cin>>m>>mod;
    char op;int n,lst=0;
    for(int i=1;i<=m;i++)
    {
        cin>>op>>n;
        if(op=='A')
        {
            int t=(lst+n)%mod;
            mx[++len]=t;
            for(int j=len-1;j>0 && mx[j]<t ;j--)
                mx[j]=t;
        }
        else
        {
            lst=mx[len-n+1];
            printf("%d\n",lst);
        }
    }

    return 0;
}

2>线段树维护最小值

就是加了个优化，但是记得提前开好点

额，很尴尬的是，数据很水，速度没有变

#include<cstdio>
#include<cstdlib>
#include<iostream>
using namespace std;
int m,mod;
const int N=200003;
int len,root,cnt;
struct node
{
    int lson,rson,mx;
}tr[N<<1];

void build(int &rt,int l,int r)
{
    rt=++cnt;
    if(l==r) return ;
    int mid=(l+r)>>1;
    build(tr[rt].lson ,l,mid);
    build(tr[rt].rson ,mid+1,r);
}
void updata(int rt)
{
    tr[rt].mx =max(tr[rt].mx ,max(tr[tr[rt].lson ].mx ,tr[tr[rt].rson ].mx ));
}
void change(int rt,int l,int r,int pos,int v)
{
    if(l==r)
    {
        tr[rt].mx =v;
        return ;
    }
    int mid=(l+r)>>1;
    if(pos<=mid) change(tr[rt].lson ,l,mid,pos,v);
    else change(tr[rt].rson ,mid+1,r,pos,v);
    updata(rt);
}
int query(int rt,int l,int r,int ql,int qr)
{
    if(ql<=l && r<=qr )
        return tr[rt].mx ;

    int mid=(l+r)>>1;
    if(qr<=mid) return query(tr[rt].lson ,l,mid,ql,qr);
    else if(ql>mid) return query(tr[rt].rson ,mid+1,r,ql,qr);
    else return max( query(tr[rt].lson ,l,mid,ql,qr) , query(tr[rt].rson ,mid+1,r,ql,qr) );
}

int main()
{
    cin>>m>>mod;
    build(root,1,m);

    char op;int n,lst=0;
    for(int i=1;i<=m;i++)
    {
        cin>>op>>n;
        if(op=='A')
            change(1,1,m,++len,(lst+n)%mod);
        else
        {
            lst=query(1,1,m,len-n+1,len);
            printf("%d\n",lst);
        }
    }

    return 0;
}