原题
数据大小是1e6，实现单调修改和区间最大值，和树状数组模板类似，不过有地方需要注意。
求最后l个值得最大值，只需要反着装值，到x求后l，那么求x+l之前的最值就可以了（x到n的值已求）。
#include<iostream> #include<cstdio> #include<cstring> #include<cmath> #include<algorithm> #include<iomanip> #define in(x) scanf("%lld",&x); using namespace std; long long m,d,c[2000005]; void updata(long long pos,long long v) { for(int i=pos;i<=m;i+=i&(-i)) c[i]=max(c[i],v); } long long quary(long long pos) { long long anse=-9999999; for(int i=pos;i;i-=i&(-i)) anse=max(anse,c[i]); return anse; } int main() { in(m);in(d);long long cnt=m,k=0; for(int i=1;i<=m;++i) { char s;long long x; cin>>s;in(x); if(s=='A') { x=(x+k)%d; updata(cnt,x); cnt--; } else { k=quary(x+cnt); printf("%lld\n",k); } } return 0; }
