BZOJ 1012 [JSOI2008]最大数maxnumber

题目大意

求一种数据结构（队列形式），支持每次加入一个数（强制在线）或者询问从队尾开始的N个数里面最大的数。

操作数量$\le 200000$

这道题线段树傻题QwQ

线段树是一种静态的数据结构，虽然可以动态加点（问的Dalao）但是比较难= =，所以这种题我比较慌= =

但是其实这个数据范围根本不需要动态= =（动态开点线段树是没啥办法的时候用的）我们直接开一棵很大的线段树存储一下就可以了，因为求的是最大值我们不需要Build直接放在那里就已经初始化完了。

之后我们就模拟请求一个一个往里塞，一次一次查询就可以了。

#include <bits/stdc++.h>
using namespace std;
int a[800010],m,n=200000,d,in,len,tmp;
char mode[10];
void updata(int pos,int l,int r,int tx,int val)
{
    if(l==r){if(l==tx) a[pos]=val;return;}
    int mid=(l+r)>>1;
    if(tx>mid) updata((pos<<1)+1,mid+1,r,tx,val);
    else updata(pos<<1,l,mid,tx,val);
    a[pos]=max(a[pos<<1],a[(pos<<1)+1]);
    return;
}
int query(int pos,int l,int r,int x,int y)
{
    if(x<=l&&r<=y) return a[pos];
    int mid=(l+r)>>1;
    if(x>mid) return query((pos<<1)+1,mid+1,r,x,y);
    if(y<=mid) return query(pos<<1,l,mid,x,y);
    return max(query(pos<<1,l,mid,x,y),query((pos<<1)+1,mid+1,r,x,y));
}
int main()
{
    scanf("%d%d",&m,&d);
    while(m--)
    {
        scanf("%s%d",mode,&in);
        //printf("%d\n",m);
        if(mode[0]=='A') {updata(1,1,n,++len,(in+tmp)%d);}
        if(mode[0]=='Q') {printf("%d\n",tmp=query(1,1,n,len-in+1,len));}
    }
    return 0;
}