【bzoj1012】[JSOI2008]最大数maxnumber

2015.02.20 12:05 Fri | 8次阅读 | 旧日oi | 固定链接 | 源码

Description

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

Input

第一行两个整数,M和D,其中M表示操作的个数(M <= 200,000),D如上文中所述,满足(0

Output

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

Sample Input

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

Sample Output

96
93
96

题解

裸的线段树,平衡树当然也能做……
当然呢我是个有追求的人,所以写了zkw线段树……

我的程序

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
int m,d,x,ans;
char s[2]; 
struct ZKW_tree
{
    static const int t=1<<18;
    int mx[1<<19|1],size;
    void insert(int x)
    {
        size++;mx[size+t]=x;
        for(int i=(size+t)>>1;i;i>>=1)
        mx[i]=max(mx[i<<1],mx[i<<1|1]);
    }
    int query(int l,int r)
    {
        int ret=0;
        for(l+=t-1,r+=t+1;l^r^1;l>>=1,r>>=1)
        {
            if(~l&1) ret=max(ret,mx[l^1]);
            if(r&1) ret=max(ret,mx[r^1]);
        }
        return ret;
    }
}tree;
int main()
{
    scanf("%d%d",&m,&d);
    while(m--)
    {
        scanf("%s%d",s,&x);
        if(s[0]=='A') tree.insert((x+ans)%d);
        else printf("%d\n",ans=tree.query(tree.size-x+1,tree.size));
    }
    return 0;
}```