典型数据结构题，可用线段树、ST表、栈、树状数组。
线段树就不说了，裸的一比，也不难打，就是跑得有点慢。
#include<cstdio> #include<cctype> #include<algorithm> #define mid (l+r>>1) #define lc (o<<1) #define rc (o<<1)+1 using namespace std; int read(){ char c; while(!isdigit(c=getchar())); int x=c-'0'; while(isdigit(c=getchar())) x=x*10+c-'0'; return x; } int cnt,t,maxv[1<<19]; void change(int o,int l,int r,int w,int v){ if(l>w || r<w) return; if(l==r){maxv[o]=v; return;} change(lc,l,mid,w,v); change(rc,mid+1,r,w,v); maxv[o]=max(maxv[lc],maxv[rc]); } int search(int o,int l,int r,int L,int R){ if(l>R || r<L) return 0; if(l>=L && r<=R) return maxv[o]; return max(search(lc,l,mid,L,R),search(rc,mid+1,r,L,R)); } int main(){ int m=read(),d=read(); for(int i=1;i<=m;i+=1){ char c; while(c=getchar(),c!='A' && c!='Q'); if(c=='A') change(1,1,m,++cnt,((long long)read()+t)%d); else printf("%d\n",t=search(1,1,m,cnt-read()+1,cnt)); } return 0; }
ST表在网上貌似不多，这个数据结构是天生支持从末尾插入的。
代码很短，就是内存需要得比较大，跑得还是挺快的。
#include<cstdio> #include<cctype> #include<cmath> #include<algorithm> using namespace std; int read(){ char c; while(!isdigit(c=getchar())); int x=c-'0'; while(isdigit(c=getchar())) x=x*10+c-'0'; return x; } int f[200001][19]; int main(){ int n=0,m=read(),d=read(),t=0; while(m--){ char opt; while(opt=getchar(),opt!='A' && opt!='Q'); if(opt=='A'){ f[++n][0]=((long long)read()+t)%d; for(int i=1;(1<<i)<=n;i+=1) f[n][i]=max(f[n-(1<<i-1)][i-1],f[n][i-1]); }else{ int l=read(),x=log2(l); t=max(f[n-l+(1<<x)][x],f[n][x]); printf("%d\n",t); } } return 0; }
由于询问一定是询问的最后几个中的最大值，所以我们可以维护单调性，保证栈顶到栈底单调递增。
输出时二分一下可以取的在栈中位置最底下的那个元素。
这是我写的这四个方法中跑得最快的一个，代码也很短。
#include<cstdio> #include<cctype> int read(){ char c; while(!isdigit(c=getchar())); int x=c-'0'; while(isdigit(c=getchar())) x=x*10+c-'0'; return x; } int cnt,top,t,s[200001][2]; int main(){ int m=read(),d=read(); while(m--){ char c; while(c=getchar(),c!='A' && c!='Q'); if(c=='A'){ int x=((long long)read()+t)%d; while(top && s[top][0]<=x) top--; s[++top][0]=x; s[top][1]=++cnt; }else{ int l=1,r=top,v=read(); while(l<=r){ int mid=l+r>>1; if(s[mid][1]>cnt-v) t=s[mid][0],r=mid-1; else l=mid+1; } printf("%d\n",t); } } return 0; }
树状数组的做法貌似也不多。
先统计有多少次增加元素。
然后编号倒一下，第一个变成最后一个，以此类推。
然后直接树状数组维护即可。
#include<cstdio> #include<cctype> #include<algorithm> using namespace std; int read(){ char c; while(!isdigit(c=getchar())); int x=c-'0'; while(isdigit(c=getchar())) x=x*10+c-'0'; return x; } int tot,t,opt[200001],v[200001],tree[200001]; int main(){ int m=read(),d=read(); for(int i=1;i<=m;i+=1){ char c; while(c=getchar(),c!='A' && c!='Q'); if(c=='A') opt[i]=1,tot++; else opt[i]=2; v[i]=read(); } int now=tot+1; for(int i=1;i<=m;i+=1) if(opt[i]==1){ int add=((long long)v[i]+t)%d; for(int j=--now;j<=tot;j+=j&-j) tree[j]=max(tree[j],add); }else{ t=0; for(int j=now+v[i]-1;j>=now;j-=j&-j) t=max(tree[j],t); printf("%d\n",t); } return 0; }