题目

分析

比赛上，没有注意到询问只询问光标前面，于是只打了个暴力。

因为询问只询问光标前面，首先，当光标向后每移动到一个位置，顺便将这个位置的前缀和，和最大前缀和求出来。

总之，模拟

#include <cmath>

#include <iostream>

#include <cstring>

#include <cstdio>

#include <cstdlib>

using namespace std;

const int maxlongint=2147483647;

const int N=1000005;

const int mo=1000000007;

int next[N],last[N],a[N],n,tot,num,sum[N],tt,mx[N],pos[N];

int main()

{

	scanf("%d",&n);

	for(int i=0;i<N;i++) mx[i]=-maxlongint;

	next[0]=n+1;

	last[n+1]=0;

	for(int i=1;i<=n;i++)

	{

		char c=getchar();

		while(c!='I' && c!='D' && c!='L' && c!='R' && c!='Q') c=getchar();

		int x;

		if(c=='I')

		{

			scanf("%d",&x);

			num++;

			tt++;

			last[next[tot]]=tt;

			next[tt]=next[tot];

			last[tt]=tot;

			next[tot]=tt;

			a[tt]=x;

			sum[tt]=sum[tot]+a[tt];

			pos[tt]=pos[tot]+1;

			mx[pos[tt]]=max(sum[tt],mx[pos[tot]]);

			tot=tt;

		}

		else

		if(c=='D')

		{

			num--;

			next[last[tot]]=next[tot];

			last[next[tot]]=last[tot];

			a[tot]=sum[tot]=0;

			tot=last[tot];

		}

		else

		if(c=='L')

		{

			tot=last[tot];

		}

		else

		if(c=='R')

		{

			if(pos[tot]<num) tot=next[tot];

			else continue;

			sum[tot]=sum[last[tot]]+a[tot];

			pos[tot]=pos[last[tot]]+1;

			mx[pos[tot]]=max(sum[tot],mx[pos[last[tot]]]);

		}

		else

		if(c=='Q')

		{

			scanf("%d",&x);

			printf("%d\n",mx[x]);

		}

	}

}

巴特西

【NOIP2016提高A组模拟9.14】数列编辑器

题目

分析

最新文章

热门文章