BZOJ 1012: [JSOI2008]最大数maxnumber

Description

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

Input

第一行两个整数，M和D，其中M表示操作的个数(M <= 200,000)，D如上文中所述，满足D在longint内。接下来
M行，查询操作或者插入操作。

Output

对于每一个询问操作，输出一行。该行只有一个数，即序列中最后L个数的最大数。

---

题解：
建一个空树，然后记录插入的个数，依次插入值顺便记录最大值即可…

---

AC代码：

#pragma GCC optimize(2)
#include<bits/stdc++.h>
#include<ext/rope>
using namespace std;
using namespace __gnu_cxx;
#define pii pair<int,int>
#define mp(a,b) make_pair(a,b)
const int MAXN = 2e5+10;
const int MOD = 100003;
const int INF = 0x3f3f3f3f;
struct node{ int l,r,val; }t[MAXN<<2];
char op[MAXN]; int last,n,m,tot;
inline void pushup(int rt){
    t[rt].val=max(t[rt<<1].val,t[rt<<1|1].val);
}
void build(int rt,int l,int r){
    t[rt].l=l,t[rt].r=r;
    if(l==r){ t[rt].val=0; return; }
    int mid=(l+r)>>1;
    build(rt<<1,l,mid); build(rt<<1|1,mid+1,r);
    pushup(rt);
}
void update(int rt,int pos,int val){
    if(t[rt].l==t[rt].r){ t[rt].val+=val;return; }
    int mid=(t[rt].l+t[rt].r)>>1;
    if(pos<=mid) update(rt<<1,pos,val);
    else update(rt<<1|1,pos,val);
    pushup(rt);
}
int query(int rt,int l,int r){
    if(l<=t[rt].l && t[rt].r<=r) return t[rt].val;
    int mid=(t[rt].l+t[rt].r)>>1,res=0;
    if(l<=mid) res=max(res,query(rt<<1,l,r));
    if(r>mid) res=max(res,query(rt<<1|1,l,r));
    return res;
}
signed main(){
#ifndef ONLINE_JUDGE
    freopen("C:\\Users\\Administrator\\Desktop\\in.txt","r",stdin);
#endif // ONLINE_JUDGE
    int n,D,x; cin>>n>>D;
    build(1,1,n);
    for(int i=1;i<=n;i++){
        scanf("%s%d",op,&x);
        if(op[0]=='A'){
            ++tot; update(1,tot,(x+last)%D);
        }else if(op[0]=='Q'){
            last = query(1,tot-x+1,tot)%D;
            printf("%d\n",last);
        }
    }
    return 0;
}