看到题的第一眼，我问LLJ大佬，这是不是主席树模板题呀，然后被大佬无情地嘲笑了。
又思考了一下，感觉树套树可做，我大概是傻了吧。
LLJ说，题解是单调队列啊。
我觉得他说的十分有道理。
裸的单调队列。
#include<cstdio>#include<cstring>#include<iostream>#include<algorithm>#include<cmath>#include<queue>#include<vector>typedef long long LL;using namespace std;const int maxn=200000+299;int m,mod,t,x,que[maxn],val[maxn],tot,now;char op[5];int ef(int l,int r,int x) { ???int res=0; ???while(l<=r) { ???????int mid=(l+r)>>1; ???????if(que[mid]>=now-x+1) ?{ ???????????res=val[que[mid]]; ???????????r=mid-1;} ???????else l=mid+1; ???} ???return res;}int main(){ ???//freopen(".in","r",stdin); ???//freopen(".out","w",stdout); ???scanf("%d%d",&m,&mod); ???while(m--) { ???????scanf("%s%d",&op,&x); ???????if(op[0]==‘A‘) { ???????????x=(x+t)%mod; ?now++; ???????????while(tot&&val[que[tot]]<=x) { ???????????????tot--; ????????????} ????????????que[++tot]=now; ???????????val[now]=x; ???????} ???????else { ??????????t=ef(1,tot,x); ??????????printf("%d\n",t); ???????} ???} ????return 0;}BZOJ 1012 [JSOI2008]最大数maxnumber
原文地址：http://www.cnblogs.com/Achenchen/p/7531897.html