题目大意：
维护一个数列，有两种操作：1、 查询当前数列中末尾L个数中的最大的数，并输出这个数的值。限制：L不超过当前数列的长度。2、插入操作：将n加上t，其中t是最近一次查询操作的答案（如果还未执行过查询操作，则t=0)，并将所得结果对一个固定的常数D取模，再将所得答插入到数列的末尾。初始时数列是空的，没有一个数。
思路：
讲道理这道题用线段树肯定不是最好的（比如用栈更快），但是我现在在学线段树，就拿来练练手。线段树裸题，有单点加入、区间查询操作。
代码：
1 #include<cstdio> 2 #include<cstring> 3 #include<iostream> 4 using namespace std; 5 6 int da[800001]; 7 8 void add(int l,int r,int x,int y,int cur) 9 { 10 da[cur]=max(da[cur],y); 11 if (l==r) return; 12 int mid=l+r>>1; 13 if (x>mid) add(mid+1,r,x,y,cur<<1|1); 14 else add(l,mid,x,y,cur<<1); 15 } 16 17 int ask(int L,int R,int l,int r,int cur) 18 { 19 if (L>=l && R<=r) return da[cur]; 20 int mid=L+R>>1,ans=0; 21 if (l<=mid) ans=max(ans,ask(L,mid,l,r,cur<<1)); 22 if (r>mid) ans=max(ans,ask(mid+1,R,l,r,cur<<1|1)); 23 return ans; 24 } 25 26 int main() 27 { 28 int m,mod,ans=0,n=0; 29 scanf("%d%d",&m,&mod); 30 for (int i=1;i<=m;i++) 31 { 32 int l; 33 char ch=getchar(); 34 while (ch<'A' || ch>'Z') ch=getchar(); 35 scanf("%d",&l); 36 if (ch=='A') 37 { 38 n++; 39 int x=(l+ans)%mod; 40 add(1,m,n,x,1); 41 } 42 else printf("%d\n",ans=ask(1,m,n-l+1,n,1)); 43 } 44 return 0; 45 }
转载于:https://www.cnblogs.com/HHshy/p/5733668.html
相关资源：JAVA上百实例源码以及开源项目