题目：https://www.lydsy.com/JudgeOnline/problem.php?id=1012
单调栈水题。可以用lower_bound。
但输入不要char ch; cin>>ch。会TLE。（为什么？）
#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>using namespace std;const int N=2e5+5;int n,m,mod,stack[N],a[N],top,lst;int main(){ ???scanf("%d%d",&m,&mod); ???char ch[5];int x; ???while(m--) ???{ ???????scanf("%s%d",ch,&x); ???????if(ch[0]==‘A‘) ???????{ ???????????(x+=lst)%=mod;a[++n]=x; ???????????while(top&&x>=a[stack[top]])top--; ???????????stack[++top]=n; ???????} ???????if(ch[0]==‘Q‘) ???????{ ???????????int k=lower_bound(stack+1,stack+top+1,n-x+1)-stack; ???????????lst=a[stack[k]]; ???????????printf("%d\n",lst); ???????} ???} ???return 0;}#include<iostream>#include<cstdio>#include<cstring>using namespace std;const int N=2e5+5;int n,m,mod,stack[N],ps[N],top,lst;int main(){ ???scanf("%d%d",&m,&mod); ???char ch[5];int x; ???while(m--) ???{ ???????scanf("%s%d",ch,&x); ???????if(ch[0]==‘A‘) ???????{ ???????????(x+=lst)%=mod; ???????????while(top&&x>=stack[top])top--; ???????????stack[++top]=x;ps[top]=++n; ???????} ???????if(ch[0]==‘Q‘) ???????{ ???????????int l=1,r=top; ???????????while(l<=r) ???????????{ ???????????????int mid=((l+r)>>1); ???????????????if(ps[mid]>n-x)lst=mid,r=mid-1; ???????????????else l=mid+1; ???????????} ???????????lst=stack[lst]; ???????????printf("%d\n",lst); ???????} ???} ???return 0;}bzoj 1012 [JSOI2008]最大数maxnumber
原文地址：https://www.cnblogs.com/Narh/p/9248678.html