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
HINT
Source
[][][]
线段树求区间最值，如果能动态开点就更好了。
1 #include2 #include 3 #include 4 #include 5 #include 6 #include 7 #include 8 #include 9 using namespace std;10 typedef long long LL;11 const LL maxn=200005;12 const LL inf=1e15;13 inline LL read(){14 LL x=0,f=1;char ch=getchar();15 while(ch<'0'||ch>'9'){ if(ch=='-')f=-1;ch=getchar();}16 while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}17 return x*f;18 }19 LL N,M,D;20 LL tot=1;21 LL a[maxn];22 LL NOW;23 char c[10];24 LL P;25 struct node{26 LL num;27 LL MAX;28 LL l,r,lc,rc;29 }seg[maxn*8];30 inline void Build(LL root,LL l,LL r){31 seg[root].num=tot;32 seg[root].l=l; seg[root].r=r;33 if(seg[root].l==seg[root].r){34 seg[root].MAX=a[l];35 return;36 }37 LL mid=(seg[root].l+seg[root].r)>>1;38 seg[root].lc=++tot; Build(tot,l,mid);39 seg[root].rc=++tot; Build(tot,mid+1,r);40 seg[root].MAX=max(seg[seg[root].lc].MAX,seg[seg[root].rc].MAX);41 }42 inline LL query(LL root,LL l,LL r){43 if(l<=seg[root].l&&seg[root].r<=r){44 return seg[root].MAX;45 }46 LL mid=(seg[root].l+seg[root].r)>>1;47 LL ans=-inf;48 if(l<=mid) ans=max(ans,query(seg[root].lc,l,r));49 if(mid+1<=r) ans=max(ans,query(seg[root].rc,l,r));50 seg[root].MAX=max(seg[seg[root].lc].MAX,seg[seg[root].rc].MAX);51 return ans;52 }53 inline void change(LL root,LL l,LL r,LL delta){54 if(l<=seg[root].l&&seg[root].r<=r){55 seg[root].MAX=delta;56 return ;57 }58 LL mid=(seg[root].l+seg[root].r)>>1;59 if(l<=mid) change(seg[root].lc,l,r,delta);60 if(mid+1<=r) change(seg[root].rc,l,r,delta); 61 seg[root].MAX=max(seg[seg[root].lc].MAX,seg[seg[root].rc].MAX);62 }63 int main(){64 scanf("%lld%lld",&M,&D);65 for(int i=1;i<=M;i++) a[i]=-inf;66 Build(1,1,M);67 for(LL i=1;i<=M;i++){68 scanf("%s",c);69 if(c[0]=='A'){70 scanf("%lld",&P);71 P=(P+NOW)%D;72 N++;73 change(1,N,N,P); 74 }75 else{76 scanf("%lld",&P);77 NOW=query(1,N-P+1,N);78 printf("%lld\n",NOW);79 }80 }81 return 0;82 }