题解 P1198 【[JSOI2008]最大数】

· · 题解

【题目描述】

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

1、 查询操作。

语法：Q L

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

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

2、 插入操作。

语法：A n

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

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

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

【输入输出格式】

第一行两个整数，m和d，其中m表示操作的个数(d \leq 200,000)，d如上文中所述，满足(0<d<2,000,000,000)

接下来的m行，每行一个字符串，描述一个具体的操作。语法如上文所述。

对于每一个查询操作，你应该按照顺序依次输出结果，每个结果占一行。

【输入输出样例】

【说明】

[JSOI2008]

本题数据已加强。

【题解】

我会暴力！

考虑暴力加入数字以及查询，时间复杂度为\Theta(x+y \times \sum_{i=1}^{y}i),x+y=m，其中x为加入操作的次数，y为查询操作的次数，m为总操作的次数。期望得分0~50分。

我会线段树！

考虑使用线段树完成此题。我们可以先建一颗非常大的树，然后加入的时候就方便多了。由于线段树单点加入的复杂度是\Theta(log_2\;n)，其中n为当前序列的长度。区间查询的复杂度也为\Theta(log_2\;n)，不过要注意的是当L=0时输出0并记录当前的答案（可能还要用到）所以使用线段树来解决本题的时间复杂度为\Theta(log_2\;x+y \times log_2\;y),x+y=m，其中x为加入操作的次数，y为查询操作的次数，m为总操作的次数，期望得分0~100分，实际得分100分。

下面送上一组全负的数据（评测数据里没有），数据源自洛谷的@tour1st，数据如下。

【数据输入输出】

【代码】

下面上AC代码~

#include <cstdio>
struct node{ int l,r,lc,rc,c; } a[1000001];
int len=0;
int max(int x,int y)
{
    return x>y?x:y;
}
void bt(int l,int r)
{
    len++;
    a[len].l=l;
    a[len].r=r;
    a[len].lc=-1;
    a[len].rc=-1;
    a[len].c=0;
    int now=len;
    if(l<r)
    {
        int mid=(l+r)/2;
        a[len].lc=len+1;
        bt(l,mid);
        a[now].rc=len+1;
        bt(mid+1,r);
    }
}
int query(int now,int l,int r)
{
    if(a[now].l==l && a[now].r==r)
    {
        return a[now].c;
    }
    int mid=(a[now].l+a[now].r)/2;
    if(r<=mid)
    {
        return query(a[now].lc,l,r);
    }
    else if(mid+1<=l)
    {
        return query(a[now].rc,l,r);
    }
    else
    {
        return max(query(a[now].lc,l,mid),query(a[now].rc,mid+1,r));
    }
}
void change(int now,int x,int t)
{
    if(a[now].l==a[now].r)
    {
        a[now].c+=t;
        return ;
    }
    int mid=(a[now].l+a[now].r)/2;
    if(x<=mid)
    {
        change(a[now].lc,x,t);
    }
    else
    {
        change(a[now].rc,x,t);
    }
    a[now].c=max(a[a[now].lc].c,a[a[now].rc].c);
}
int main()
{
    int n=200001,m=0,d=0;
    scanf("%d %d",&m,&d);
    bt(1,n);
    int pt=0;
    len=0;
    for(int i=1;i<=m;i++)
    {
        char t[5];
        int x=0;
        scanf("%s %d",t+1,&x);
        if(t[1]=='Q')
        {
            if(x==0)
            {
                pt=0;
            }
            else
            {
                pt=query(1,len-x+1,len);
            }
            printf("%d\n",pt);
        }
        else
        {
            len++;
            change(1,len,(x+pt)%d);
        }
    }
    return 0;
}