[JSOI2008] [洛谷P1198] 最大数 [80']

浏览数：31 / 时间：2015年06月09日

题目描述 Description

现在请求你维护一个数列，要求提供以下两种操作：
1、查询操作。
语法：Q L
功能：查询当前数列中末尾L个数中的最大的数，并输出这个数的值。
限制：L不超过当前数列的长度。
2、插入操作。
语法：A n
功能：将n加上t，其中t是最近一次查询操作的答案（如果还未执行过查询操作，则t=0)，并将所得结果对一个固定的常数D取模，将所得答案插入到数列的末尾。
限制：n是整数（可能为负数）并且在长整范围内。
注意：初始时数列是空的，没有一个数。

输入输出格式 Input/output

输入格式：
第一行两个整数，M和D，其中M表示操作的个数(M <= 200,000)，D如上文中所述，满足(0<D<2,000,000,000)
接下来的M行，每行一个字符串，描述一个具体的操作。语法如上文所述。
输出格式：
对于每一个查询操作，你应该按照顺序依次输出结果，每个结果占一行。

输入输出样例 Sample input/output

样例测试点#1

输入样例：

5 100
A 96
Q 1
A 97
Q 1
Q 2

输出样例：

96
93
96

分析：首先简单高效的做法为单调栈，代码短，效率高。不过本渣由于不会就写的线段树，得了80分。我想的线段树的写法是先存入各操作，建树后离线操作。每次询问后修改相关节点（具体见代码），最后两点未过，不知何因。

#include<iostream>  
#include<cstdlib>  
#include<cstdio>  
#include<cstring>  
using namespace std;  
int m,D,sum,t,x,maxn,sum1,sum2,ss,tt,num1[200001],num2[200001][2],sq[800001];  
char c;  
void build_tree(int s,int t,int now)  
{  
     int mid;  
     if (s==t)   
     {  
               sq[now]=num1[s];  
               return;  
     }  
     mid=(s+t)/2;  
     build_tree(s,mid,now*2);  
     build_tree(mid+1,t,now*2+1);  
     sq[now]=max(sq[now*2],sq[now*2+1]);     
}      
int find_tree(int s,int t,int now)  
{  
    int mid,ans;  
    if (s>=ss&&t<=tt) return sq[now];  
    mid=(s+t)/2;  
    if (ss<=mid) ans=find_tree(s,mid,now*2); else ans=-1;  
    if (tt>mid) ans=max(ans,find_tree(mid+1,t,now*2+1));  
    return ans;  
}  
void fix_tree(int s,int t,int now)  
{  
     int mid;  
     if (s==ss&&s==t)   
     {  
               sq[now]=tt;  
               return;  
     }  
     mid=(s+t)/2;  
     if (ss<=mid)  
     {  
                fix_tree(s,mid,now*2);  
                sq[now]=max(sq[now*2],sq[now*2+1]);  
     }  
     if (ss>mid)   
     {  
                 fix_tree(mid+1,t,now*2+1);  
                 sq[now]=max(sq[now*2],sq[now*2+1]);  
     }  
}   
int main()  
{  
    scanf("%d%d",&m,&D);  
    getchar();  
    t=0;  
    sum=0;  
    for (int i=1;i<=m;i++)  
    {  
        c=getchar();  
        scanf("%d",&x);  
        if (c==‘A‘)  
        {  
                   sum1++;  
                   num1[sum1]=x;  
        }  
        if (c==‘Q‘)  
        {  
                   sum2++;  
                   num2[sum2][1]=sum1-x+1;  
                   num2[sum2][2]=sum1;  
        }  
        getchar();  
    }  
    build_tree(1,sum1,1);  
    for (int i=1;i<=sum2;i++)  
    {  
        ss=num2[i][1];  
        tt=num2[i][2];  
        t=find_tree(1,sum1,1);  
        printf("%d\n",t);  
        if (num2[i][2]==sum1) continue;  
        for (int j=num2[i][2]+1;j<=num2[i+1][2];j++)  
        {  
            ss=j;  
            tt=(num1[j]%D+t%D)%D;  
            fix_tree(1,sum1,1);  
        }  
    }  
    return 0;  
}

测试点 #1：通过该测试点。 得分10，耗时187ms，内存4317kB。
测试点 #2：通过该测试点。 得分10，耗时0ms，内存2060kB。
测试点 #3：通过该测试点。 得分10，耗时0ms，内存2068kB。
测试点 #4：通过该测试点。 得分10，耗时15ms，内存2306kB。
测试点 #5：通过该测试点。 得分10，耗时93ms，内存3215kB。
测试点 #6：通过该测试点。 得分10，耗时109ms，内存3891kB。
测试点 #7：通过该测试点。 得分10，耗时202ms，内存4313kB。
测试点 #8：通过该测试点。 得分10，耗时234ms，内存3948kB。
测试点 #9：错误的答案。 得分0，耗时187ms，内存4313kB。