时间限制：1000MS 内存限制：262144KB数据结构-栈 无
现在你需要实现一个数列编辑器，一开始，数列为空，光标在开头位置，编辑器要支持对这个数列进行如下六种操作：
I ：x在光标的后面插入一个整数 x，并将光标移到这个新加入的 x 后。
D：删除光标前的最后一个数字（保证存在），光标位置不变。
L：光标左移一位，如果已经在开头则不做任何事。
R：光标右移一位，如果已经在结尾则不做任何事。
Q l r：求当前序列中第 l到第 r个数（包含边界，保证存在）的和。
C p x：将当前序列第 p 个数（保证存在）修改成整数 x，光标不移动。
第一行，一个整数 n，表示操作的总次数。
后 n 行，每行是上列六种操作中的一种。
对每个询问输出一行一个整数，表示答案。
9
I 2
I -1
I 1
Q 1 2
L
D
Q 1 2
I -3
Q 1 2
1
3
-1
Easy：第 1−2 个测试点，1≤n≤5000。
Normal：第 3−4个测试点，不存在 L,R,C 操作。
Hard：第 5−7个测试点，不存在 L,R操作。
Extra：对于 100%的数据，存在全部操作，且 1≤n≤5×10^5，记当前数列长度为 L，则操作中 −10^9≤x≤10^9，1≤l≤r≤L，且 1≤p≤L。
+20分：链表
+50分：前缀树状数组
正解：建一个前缀树状数组，建一个后缀树状数组，中间夹着光标，如果你不懒再开两个栈，存两个数状数组中的数
移动光标就是，把一个栈的数弹到另一个里面，把一个树状数组的数弹到另一个里面。。。剩下操作就直接求就好了。。。
代码（我懒没有栈）
#include<cstdio> #include<iostream> #define ll long long #define R register ll using namespace std; const int N=500010; inline int g() { R ret=0,fix=1; register char ch; while(!isdigit(ch=getchar())) fix=ch==‘-‘?-1:fix; do ret=ret*10+(ch^48); while(isdigit(ch=getchar())); return ret*fix; } int n,cntl,cntr; ll c[2][N]; inline int lbt(int x) {return x&-x;} inline void add(int d,int pos,int x) {for(;pos<=n;pos+=lbt(pos)) c[d][pos]+=x;} inline ll query(int d,int pos) { R ret=0; for(;pos;pos-=lbt(pos)) ret+=c[d][pos]; return ret; } signed main() { n=g(); for(R i=1;i<=n;++i) { register char ch; R x,l,r; while(!isalpha(ch=getchar())) cerr<<ch; cerr<<ch<<endl; cerr<<"qwq"; cerr<<"fasdgfads"<<cntl<<" "<<cntr<<endl; if(ch==‘I‘) x=g(),add(0,++cntl,x); else if(ch==‘D‘) x=query(0,cntl)-query(0,cntl-1),add(0,cntl,-x),--cntl; else if(ch==‘L‘) {if(cntl>0) x=query(0,cntl)-query(0,cntl-1),add(0,cntl,-x),--cntl,add(1,++cntr,x);} else if(ch==‘R‘) {if(cntr>0) x=query(1,cntr)-query(1,cntr-1),add(1,cntr,-x),--cntr,add(0,++cntl,x);} else if(ch==‘Q‘) { R ret=0; l=g(),r=g(); if(r<=cntl) printf("%lld\n",query(0,r)-query(0,l-1)); else if(l>cntl) printf("%lld\n",query(1,cntl+cntr-l+1)-query(1,cntl+cntr-r)); else printf("%lld\n",query(0,cntl)-query(0,l-1)+query(1,cntr)-query(1,cntl+cntr-r)); } else if(ch==‘C‘) { l=g(),x=g(); if(l<=cntl) r=query(0,l)-query(0,l-1),add(0,l,x-r); else r=query(1,cntl+cntr-l+1)-query(1,cntl+cntr-l),add(1,cntl+cntr-l+1,x-r); } } }
2019.05.06
原文：https://www.cnblogs.com/Jackpei/p/10819753.html