维护两个栈,分别存光标前和光标后的数
再维护前缀和的栈 和 前缀和最大值的栈
注意一下左移,右移,删除到顶了就不操作了
5个操作
I x : 光标处插入x -----> s1.push(x)
D : 光标前删除 -----> s1.pop()
L : 光标左移 -----> s2.push(s1.top()) s1.pop()
R : 光标右移 -----> s1.push(s2.top()) s2.pop()
Q k : 输出前k个数前缀和最大值
/********************* Template ************************/ #include <set> #include <map> #include <list> #include <cmath> #include <ctime> #include <deque> #include <queue> #include <stack> #include <bitset> #include <cstdio> #include <string> #include <vector> #include <cassert> #include <cstdlib> #include <cstring> #include <sstream> #include <fstream> #include <numeric> #include <iomanip> #include <iostream> #include <algorithm> #include <functional> using namespace std; #define EPS 1e-8 #define MAXN 1000050 #define MOD (int)1e9+7 #define PI acos(-1.0) #define DINF (1e10) #define LINF ((1LL)<<50) #define INF (0x3f3f3f3f) #define max(a,b) ((a) > (b) ? (a) : (b)) #define min(a,b) ((a) < (b) ? (a) : (b)) #define max3(a,b,c) (max(max(a,b),c)) #define min3(a,b,c) (min(min(a,b),c)) #define BUG cout<<"BUG! "<<endl #define line cout<<"--------------"<<endl #define L(t) (t << 1) #define R(t) (t << 1 | 1) #define Mid(a,b) ((a + b) >> 1) #define lowbit(a) (a & -a) #define FIN freopen("in.txt","r",stdin) #define FOUT freopen("out.txt","w",stdout) #pragma comment (linker,"/STACK:102400000,102400000") // typedef long long LL; // typedef unsigned long long ULL; // typedef __int64 LL; // typedef unisigned __int64 ULL; // LL gcd(LL a,LL b){ return b?gcd(b,a%b):a; } // LL lcm(LL a,LL b){ return a*b/gcd(a,b); } /********************* F ************************/ int pstack[MAXN],sstack[MAXN]; int pre[MAXN]; int pmax[MAXN]; int main() { //FIN; //FOUT; int n ; while(~scanf("%d",&n)){ int now1 = 0,now2 = 0; while(n--){ char ch; int a; getchar(); scanf("%c",&ch); if(ch == 'I'){ scanf("%d",&a); pstack[now1] = a; pre[now1] = (now1 == 0) ? a : (pre[now1-1]+a); pmax[now1] = (now1 == 0) ? a : max(pmax[now1-1],pre[now1]); now1++; }else if(ch == 'D'){ if(now1 == 0) continue; now1--; }else if(ch == 'L'){ if(now1 == 0) continue; sstack[now2] = pstack[now1-1]; now1--; now2++; }else if(ch == 'R'){ if(now2 == 0) continue; pstack[now1] = sstack[now2-1]; pre[now1] = (now1 == 0) ? sstack[now2-1] : (pre[now1-1]+sstack[now2-1]); pmax[now1] = (now1 == 0) ? sstack[now2-1] : max(pmax[now1-1],pre[now1]); now2--; now1++; }else if(ch == 'Q'){ scanf("%d",&a); printf("%d ",pmax[a-1]); } } } return 0; }