题目传送门
【题目大意】
【思路分析】
参考这道题“对顶堆”的做法，我们可以用一个类似的“对顶栈”做法。栈$a$记录从序列开头到光标位置的子序列，栈$b$记录从光标后到序列结尾的子序列，两个栈都以光标所在的一端为栈顶。因为第五种操作查询的位置$k$不超过光标位置，所以我们用一个数组$sum$记录栈$a$的前缀和，$f$记录前缀和最大，对于每种操作如下处理：
1.“$I\ x$”操作：把$x$插入栈$a$，更新$sum$数组和$f$数组
2.“$D$”操作：把$a$的栈顶弹出
3.“$L$”操作：弹出$a$的栈顶，插入栈$b$
4.“$R$”操作：弹出$b$的栈顶，插入栈$a$，更新$sum$数组和$f$数组
5.“$Q\ k$”操作：直接返回$f[k]$
弹出栈顶时要注意栈顶元素是否存在。
【代码实现】
1 #include<cstdio> 2 #include<iostream> 3 #include<cstring> 4 #include<algorithm> 5 #include<cmath> 6 #define g() getchar() 7 #define rg register 8 #define go(i,a,b) for(rg int i=a;i<=b;i++) 9 #define back(i,a,b) for(rg int i=a;i>=b;i--) 10 #define db double 11 #define ll long long 12 #define il inline 13 #define pf printf 14 using namespace std; 15 int fr(){ 16 int w=0,q=1; 17 char ch=g(); 18 while(ch<'0'||ch>'9'){ 19 if(ch=='-') q=-1; 20 ch=g(); 21 } 22 while(ch>='0'&&ch<='9') w=(w<<1)+(w<<3)+ch-'0',ch=g(); 23 return w*q; 24 } 25 const int N=1e6+2; 26 int a[N],b[N],sum[N],f[N],q,ha,hb; 27 int main(){ 28 q=fr(); 29 go(i,0,q) f[i]=-N; 30 go(i,1,q){ 31 char type;int x; 32 cin>>type; 33 if(type=='I'){ 34 x=fr();a[++ha]=x; 35 sum[ha]=sum[ha-1]+x; 36 f[ha]=max(f[ha-1],sum[ha]); 37 } 38 if(type=='D'&&ha>0) ha--; 39 if(type=='L'&&ha>0){ 40 b[++hb]=a[ha]; 41 ha--; 42 } 43 if(type=='R'&&hb>0){ 44 a[++ha]=b[hb]; 45 hb--; 46 sum[ha]=sum[ha-1]+a[ha]; 47 f[ha]=max(f[ha-1],sum[ha]); 48 } 49 if(type=='Q'){ 50 x=fr(); 51 pf("%d\n",f[x]); 52 } 53 } 54 return 0; 55 } 代码戳这里转载于:https://www.cnblogs.com/THWZF/p/11347287.html
