【题目链接】
http://acm.hdu.edu.cn/showproblem.php?pid=4699
【算法】
维护两个栈，一个栈放光标之前的数，另外一个放光标之后的数
在维护栈的同时求最大前缀和，即可
【代码】
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 1e6 + ;
const int INF = 2e9; class mstack
{
private :
int tot;
int s[MAXN];
public :
inline void clear()
{
tot = ;
}
inline void push(long long x)
{
tot++;
s[tot] = x;
}
inline void pop()
{
tot--;
}
inline long long top()
{
return s[tot];
}
inline bool empty()
{
return tot == ;
}
} s1,s2; int q,pos;
long long x;
long long sum[MAXN],f[MAXN];
char opt[]; int main()
{ while (scanf("%d",&q) != EOF)
{
f[] = -INF;
s1.clear();
s2.clear();
pos = ;
while (q--)
{
scanf("%s",&opt);
if (opt[] == 'I')
{
scanf("%lld",&x);
s1.push(x);
pos++;
sum[pos] = sum[pos-] + x;
f[pos] = max(f[pos-],sum[pos]);
}
if (opt[] == 'D')
{
if (s1.empty()) continue;
s1.pop();
pos--;
}
if (opt[] == 'L')
{
if (s1.empty()) continue;
x = s1.top();
s1.pop();
s2.push(x);
pos--;
}
if (opt[] == 'R')
{
if (s2.empty()) continue;
x = s2.top();
s2.pop();
s1.push(x);
pos++;
sum[pos] = sum[pos-] + x;
f[pos] = max(f[pos-],sum[pos]);
}
if (opt[] == 'Q')
{
scanf("%lld",&x);
printf("%lld\n",f[x]);
}
}
} return ; }