P2201 数列编辑器(对顶栈)

ruoye123456 / 2024-09-13 / 原文

#include<bits/stdc++.h>
using namespace std;
#define x first
#define y second
typedef pair<int,int> PII;
typedef long long ll;
typedef unsigned long long ull;
typedef unsigned int uint;
typedef vector<string> VS;
typedef vector<int> VI;
typedef vector<vector<int>> VVI;
vector<int> vx;
inline int mp(int x) {return upper_bound(vx.begin(),vx.end(),x)-vx.begin();}
inline int log_2(int x) {return 31-__builtin_clz(x);}
inline int popcount(int x) {return __builtin_popcount(x);}
inline int lowbit(int x) {return x&-x;}
const int N = 1e6+10,suf = -2139062144;
int A[N],B[N],s[N],f[N];
int tA = 0, tB = 0;
void solve()
{
	//用A存储从开始到光标的栈,B存储光标后到结尾的序列
	//s[i]为前缀和,f[i]为前缀和最大值
	f[0] = suf;
	int n;
	cin>>n;
	for(int i=1;i<=n;++i)
	{
		char op;
		cin>>op;
		if(op == 'I') 
		{
			int x;
			cin>>x;
			A[++tA] = x;
			s[tA] = s[tA-1] + x;
			f[tA] = max(f[tA-1],s[tA]);
		}
		else if(op == 'D') --tA;
		else if(op == 'L')
		{
			B[++tB] = A[tA--];
		}
		else if(op == 'R')
		{
			int x = B[tB--];
			A[++tA] = x;
			s[tA] = s[tA-1] + x;
			f[tA] = max(f[tA-1],s[tA]);
		}
		else 
		{
			int x;
			cin>>x;
			cout<<f[x]<<'\n';
		}
	}
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	int T = 1;
	//cin>>T;
	while(T--)
	{
		solve();
	}
}