正难则反，意想不到。
这道题是动态让你维护一个数列，已经在数列里面的数据不做改变，每次在最后加上一个数，强制在线。
既然正着做很难，考虑如果时间倒流，不会改变之前的维护的任何数据结构。于是我们反着维护一个St表。
#include<iostream>#include<cstring>#include<algorithm>#include<cstdio>#include<queue>#include<bitset>#include<vector>#include<map>#include<ctime>#include<cstdlib>#include<set>#include<bitset>#include<stack>#include<list>#include<cmath>using namespace std;#define RP(t,a,b) for(register int (t)=(a),edd_=(b);t<=edd_;++t)#define DRP(t,a,b) for(register int (t)=(a),edd_=(b);t>=edd_;--t)#define ERP(t,a) for(int t=head[a];t;t=e[t].to)#define Max(a,b) ((a)<(b)?(b):(a))#define Min(a,b) ((a)<(b)?(a):(b))#define TMP template<class ccf>typedef long long ll;TMP inline ccf qr(ccf k){ ???char c=getchar(); ???ccf x=0; ???int q=1; ???while(c<48||c>57) ???q=c==45?-1:q,c=getchar(); ???while(c>=48&&c<=57) ???x=x*10+c-48,c=getchar(); ???if(q==-1) ???x=-x; ???return x;}const int maxn=2e5+15;int n;int top;ll data[maxn];ll ans[maxn][25];int lg[maxn];ll t1,t2,t3;char c;int cnt;ll mod;ll lastans;inline void init(){ ???n=qr(1); ???mod=qr(1ll); ???memset(ans,0xcc,sizeof ans); ???RP(t,1,n+5){ ???lg[t]=lg[t-1]; ???if((1<<(lg[t]+1))==t) ???????lg[t]++; ???} ???RP(t,1,n){ ???cin>>c; ???if(c==‘A‘){ ???????data[top+1]=(qr(1ll)%mod+lastans%mod)%mod; ???????++top; ???????ans[top][0]=data[top]; ???????RP(k,1,lg[top]) ???????ans[top][k]=Max(ans[top][k-1],ans[top-(1<<(k-1))][k-1]); ???} ???else{ ???????t1=qr(1); ???????lastans=Max(ans[top][lg[t1]],ans[top-t1+(1<<lg[t1])][lg[t1]]); ???????printf("%lld\n",lastans); ???} ???}}int main(){#ifndef ONLINE_JUDGE ???freopen("in.in","r",stdin); ???freopen("out.out","w",stdout);#endif ???init(); ???return 0;}【题解】[JSOI2008]最大数
原文地址：https://www.cnblogs.com/winlere/p/10308137.html