BZOJ链接：http://www.lydsy.com/JudgeOnline/problem.php?id=1012
luogu链接：https://www.luogu.org/problemnew/show/P1198（luogu自称已加强数据）
虽然有很多人给出了非线段树做法，但是秉承着练线段树的原则，我还是把它当成了线段树裸题。
主要是有个坑点，那就是查询一个长度为0的区间。。。
因为一开始数列中没有数字，所以线段树甚至不需要建树，整个题只需要查询和修改两个操作即可完美解决
每个点只修改一次，而且是单点修改，标记什么的也不需要。但是查询的时候要先把a,b赋一个非常小的值，来应对负数的情况。
区间长度的话，假设所有的操作都是修改，这样区间长度就是操作数。
#include<cstdio>const long long inf=-(1<<62);int m,cnt;char op[2];long long data[800005],x,t,p;long long max(long long a,long long b){ ???return a>b?a:b;}void add(int s,int k,int o,int l,int r){ ???if(l==r) ???{ ???????data[o]=k; ???????return; ???} ???int mid=(l+r)>>1; ???if(mid>=s) add(s,k,o<<1,l,mid); ???if(mid<s) add(s,k,o<<1|1,mid+1,r); ???data[o]=max(data[o<<1],data[o<<1|1])%p;}long long ask(int ll,int rr,int o,int l,int r){ ???if(ll<=l&&rr>=r) return data[o]; ???int mid=(l+r)>>1; ???long long a=inf,b=inf; ???if(mid>=ll) a=ask(ll,rr,o<<1,l,mid); ???if(mid<rr) b=ask(ll,rr,o<<1|1,mid+1,r); ???return max(a,b);}int main(){ ???scanf("%d %lld",&m,&p); ???for(int i=0;i<m;i++) ???{ ???????scanf("%s %lld",op,&x); ???????if(op[0]==‘A‘) ???????{ ???????????add(cnt+1,(x+t)%p,1,1,m); ???????????cnt++; ???????} ???????if(op[0]==‘Q‘) ???????{ ???????????if(x==0) t=0; ???????????else t=ask(cnt-x+1,cnt,1,1,m)%p; ???????????printf("%lld\n",t); ???????} ???} ???return 0;}[JSOI2008]最大数
原文地址：https://www.cnblogs.com/zeroform/p/8320264.html