题解 P1198 【[JSOI2008]最大数】

· · 题解

线段树华丽丽的登场了！

【题目大意】

1、查询操作。语法：Q L功能：查询当前数列中末尾L个数中的最大的数，并输出这个数的值。

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

【算法讨论】

运用线段树的算法。首先建树，把所有的节点的值赋成min_int。用[i,j]表示该区间的最大值。

1）读入Q L操作。用len表示区间的大小，在len+1的位置放入（L+T)%D的值。

2）读入A n操作。输出区间[len-n+1,len]这个区间中的最大值，并把t的值进行更新。

得分：100

时间复杂度：O(nlogn)

空间复杂度：O(4*n)

【C++代码】


#include<iostream>
#include<cstdlib>
#include<cstdio>
#define maxn 200001
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
using namespace std;
const int n=maxn-1;
int ma[maxn<<2],t,d,m,len;
void build(int l,int r,int rt)
{
    ma[rt]=-2147283647;
    if (l==r)return;
    int mid=(l+r)>>1;
    build(lson);build(rson);
}
void update(int l,int r,int rt,int i,int j)
{
    if (l==r){ma[rt]=j;return;}
    int mid=(l+r)>>1;
    if (i<=mid)update(lson,i,j);
    else update(rson,i,j);
    ma[rt]=max(ma[rt<<1],ma[rt<<1|1]);
}
int query(int l,int r,int rt,int i,int j)
{

    if (i<=l && r<=j)return ma[rt];
    int mid=(l+r)>>1,o=-2147483647;
    if (i<=mid)o=query(lson,i,j);
    if (j>mid)o=max(o,query(rson,i,j));
    return o;
}
int main ()
{
    scanf ("%d%d",&m,&d);
    build(1,n,1);
    for (int b=1;b<=m;++b)
    {
        char c;int i;
        cin >>c;scanf ("%d",&i);
        if (c=='A'){len++;update(1,n,1,len,(i+t)%d);}
        else {t=query(1,n,1,len-i+1,len);printf ("%d\n",t);}
    }
    return 0;
}