链接：http://acm.hdu.edu.cn/showproblem.php?pid=4699

题意就是模拟打字，要求支持以下操作：

• I x：在当前光标后面插入x
• D：删除光标前面一个字符
• L：光标向左移动一步
• R：光标向右移动一步
• Q k：插入前k个数字中子段和最大是多少。

这题可以用splay维护，比较简单的办法是用双向链表，维护一个ans数组，记录前i个ss数字中子段和最大是多少。对于L，R，D，I操作的时候记得更新ans数组就行了。

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <stack>
#include <list>
using namespace std;

const int maxn = 1001010;
const int inf = 0x3f3f3f3f;

struct ListNode {
	ListNode *next;
	ListNode *pre;
	int key, sum;
};

ListNode nodes[maxn*2];
ListNode *p;
int C, id, ans[maxn];
int n, x;
char op[100];

void add(int key) {
	ListNode *q = &nodes[C++];
	q->sum = p->sum + key;
	q->key = key;
	q->pre = p;
	q->next = p->next;
	if (q->next != 0)
		q->next->pre = q;
	p->next = q;
	p = p->next;
	id++;
	ans[id] = max(p->sum, ans[id-1]);
}

void del() {
	if (p->pre == 0)
		return ;
	id--;
	ListNode *q = &nodes[C++];
	q = p->next;
	p = p->pre;
	if (q != 0)
		q->pre = p;
	p->next = q;
}

void left() {
	if (p->pre == 0)
		return ;
	id--;
	p = p->pre;
}

void right() {
	if (p->next == 0)
		return ;
	int tmp = p->sum;
	id++;
	p = p->next;
	p->sum = tmp + p->key;
	ans[id] = max(p->sum, ans[id-1]);
}

void init() {
	for (int i = 0; i < maxn; i++)
		ans[i] = -inf;
	C = 1; id = 0;
	p = &nodes[0];
	p->pre = 0;
	p->next = 0;
	p->sum = 0;
	p->key = 0;
}

void work() {
	for (int i = 0; i < n; i++) {
		scanf("%s", op);
		if (op[0] == 'I') {
			scanf("%d", &x);
			add(x);
		} else if (op[0] == 'D') {
			del();
		} else if (op[0] == 'L') {
			left();
		} else if (op[0] == 'R') {
			right();
		} else {
			scanf("%d", &x);
			printf("%d\n", ans[x]);
		}
	}
}

int main() {
	while (scanf("%d", &n) != EOF) {
		init();
		work();
	}
	return 0;
}