传送门
思路：操作数M<=200000，假设每次都是插入，那么得到的序列长度也不会超过200000，考虑对区间[1,m]建一棵线段树，然后就是板子题了。
AC Code：
#include<cstdio>#include<cstring>#include<algorithm>using namespace std;const int N=200000+100;typedef long long ll;int tot;struct node{ ???int l,r; ???ll maxx;}tr[N<<2];void updata(int u){ ???tr[u].maxx=max(tr[u<<1].maxx,tr[u<<1|1].maxx);}void build(int u,int l,int r){ ???tr[u].l=l,tr[u].r=r; ???if(l==r){ ???????tr[u].maxx=0;return ; ???} ???int mid=(l+r)>>1; ???build(u<<1,l,mid);build(u<<1|1,mid+1,r); ???updata(u);}void modify(int u,int p,ll k){ ???int l=tr[u].l,r=tr[u].r; ???if(l==r){ ???????tr[u].maxx=k;return ; ???} ???int mid=(l+r)>>1; ???if(p<=mid) modify(u<<1,p,k); ???else modify(u<<1|1,p,k); ???updata(u);}ll query(int u,int ql,int qr){ ???ll ans=-(1<<30); ???int l=tr[u].l,r=tr[u].r; ???if(ql<=l&&qr>=r) return tr[u].maxx; ???if(ql>r||qr<l) return -(1<<30); ???int mid=(l+r)>>1; ???if(ql<=mid) ans=max(ans,query(u<<1,ql,qr)); ???if(qr>mid) ans=max(ans,query(u<<1|1,ql,qr)); ???return ans;} ?int main(){ ???int m; ???ll d; ???scanf("%d%lld",&m,&d); ???build(1,1,m); ???char op[3];ll t=0; ???for(int i=1;i<=m;i++){ ???????scanf("%s",op); ???????if(op[0]==‘A‘){ ????????????ll n;scanf("%lld",&n); ????????????n=(n+t)%d; ????????????tot++; ????????????modify(1,tot,n); ???????} ???????else if(op[0]==‘Q‘){ ???????????int l;scanf("%d",&l); ???????????int r=tot;l=tot-l+1; ???????????t=query(1,l,r); ???????????printf("%lld\n",t); ???????} ???} ???return 0;}P1198 [JSOI2008]最大数 - 线段树
原文地址：https://www.cnblogs.com/Loi-Brilliant/p/9460941.html