【题解】[JSOI2008]最大数

【题解】[P1198 JSOI2008]最大数

正难则反，意想不到。

这道题是动态让你维护一个数列，已经在数列里面的数据不做改变，每次在最后加上一个数，强制在线。

既然正着做很难，考虑如果时间倒流，不会改变之前的维护的任何数据结构。于是我们反着维护一个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]最大数

【题解】[P1198 JSOI2008]最大数

正难则反，意想不到。

最新文章

热门文章