题解 P2201 【数列编辑器】
wuzhoupei
2017-11-05 18:46:17
这道题我写的是链表；
至少这样写还好想；
但是有一点需要注意：每次操作完都要去更新当前点；
所以插入就是断开点前点与前一个点的连接，加入新点；
删除就是把当前点的前后两个点连接；
左移右移显然直接移动；
查询最好是用数组记录，这样不会TLE；
所以就直接写个链表模拟就好了；
我是每次都更新，这样不会错，而且保险；
```cpp
#include "iostream"
#include "stdio.h"
#include "algorithm"
#define II int
#define R register
#define U NULL
#define I 1000010
using namespace std;
struct node {
II o,sum,wei;
node *up,*next;
};
node * begin(R II x)
{
node * ret=new node;
ret->up=U;
ret->next=U;
ret->o=x;
ret->sum=0;
return ret;
}
node *root=begin(0),*now,*en;
II ans[I];
void ppp(node *pi)
{
pi->wei=pi->up->wei+1;
pi->sum=pi->up->sum+pi->o;
ans[pi->wei]=max(ans[pi->wei-1],pi->sum);
}
void add()
{
R II x;
scanf("%d",&x);
R node *pi=begin(x);
R node *qian=now->up;
now->up=pi;
pi->next=now;
pi->up=qian;
qian->next=pi;
ppp(pi);
ppp(now);
}
void del()
{
R node *de=now->up;
R node *qian=de->up;
qian->next=now;
now->up=qian;
ppp(now);
}
void just()
{
now=now->up;
ppp(now);
}
void back()
{
now=now->next;
ppp(now);
}
void query()
{
R II k;
scanf("%d",&k);
printf("%d\n",ans[k]);
}
int main()
{
// freopen("1.in","r",stdin);
R II n; R char a;
scanf("%d",&n);
now=begin(0);
now->up=root; now->next=root;
root->up=now;
root->next=now;
ans[0]=-1e9;
while (n--) {
cin>>a;
if(a=='I') add();
if(a=='D') del();
if(a=='L') just();
if(a=='R') back();
if(a=='Q') query();
}
exit(0);
}
```