题意：给定一个数列，要求维护：1、求倒数L个数中的最大值  2、在数列末尾插入（最近的1询问的答案+x）%D。其中初始序列为空。

法一：因为询问最多200000个，所以直接建一棵大小为M的线段树维护即可

#include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           using namespace std;struct Node{    int l,r,m;    Node *lchild,*rchild;    Node(){}    Node(int _l,int _r):l(_l),r(_r),m(0),lchild(0),rchild(0){}}*Root;int N,M,D,x,t;char Order[6];void Pushup(Node *&x){ x->m=max(x->lchild->m,x->rchild->m);}void Build(Node *&x,int l,int r){    x=new Node(l,r);    if(l==r) return;    int m=(l+r)>>1;    Build(x->lchild,l,m),Build(x->rchild,m+1,r);}void Update(Node *&x,int p,int v){    if(x->l==x->r){        x->m=v;        return;    }    int m=(x->l+x->r)>>1;    if(p<=m) Update(x->lchild,p,v);    else Update(x->rchild,p,v);    Pushup(x);}int Query(Node *&x,int l,int r){    if(l<=x->l && x->r<=r) return x->m;    int m=(x->l+x->r)>>1,Ans=-1;    if(l<=m) Ans=Query(x->lchild,l,r);    if(m
           
            rchild,l,r)); return Ans;}int main(){ scanf("%d %d",&M,&D); Build(Root,1,M); for(int i=1,p;i<=M;i++){ scanf("%s",Order); if(Order[0]=='Q'){ cin >> p; cout << (t=Query(Root,N-p+1,N)) << endl; } else{ cin >> x; N++,Update(Root,N,(x+t)%D); } } return 0;}
           
          
         
        
       
      

法二：显然对于任意一个位置的数，其之前比它小的数在之后的询问中肯定没有贡献。所以维护一个单调栈，用二分来回答询问。

#include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            using namespace std;#define ll long longconst int MAXN=200000+2;int M,N,s[MAXN],C,D,t,a[MAXN];char Order[6];int main(){ scanf("%d%d",&M,&D); while(M--){ int x; scanf("%s%d",Order,&x); if(Order[0]=='Q'){ int p=lower_bound(s+1,s+N+1,C-x+1)-s; printf("%d\n",t=a[s[p]]); } else{ x=(x+t)%D,a[++C]=x; while(N && a[s[N]]<=x) N--; s[++N]=C; } } return 0;}