昨天A掉的这题，然后伸展树还有最后一题没敲。很BT的一题，但是感觉学习伸展树不做这道题不算真正学过吧。 这道题多了一个操作，求子序列和的最大值。这个东西怎么维护？其实和学习线段树的时候很经典的那个Hotel基本一样，维护一个最左端的和的最大值，维护一个最右端和的最大值，维护一个最大值，维护一个区间和。然后区间合并的操作就好写了，不过写的时候细节的地方要特别注意一下，例如，没有左节点的情况。（当然每次pushup,pushdown操作的时候都可以加上特判）。这里还有一点要特别注意一下，就是每次翻转的时候：除了左右子节点要翻转之外，还需要将每个节点的lmax_sum,rmax_sum进行交换（这个特别注意一下）。然后其他操作也没有什么难实现的东西。
交了20+发，终于过了，一开始超时居然是因为没有进行内存回收，（话说这样为什么返回的是超时啊，不应该是RE嘛），改掉以后就是一直PushDown操作写跪。
下面附上AC代码：
/**************************************************************
Problem: 1500
User: hqwhqwhq
Language: C++
Result: Accepted
Time:6136 ms
Memory:29772 kb
****************************************************************/
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <map>
#define INF (1<<30)
#define LL long long
#define FOR(i,x,y) for(int i = x;i < y;i ++)
#define IFOR(i,x,y) for(int i = x;i > y;i --)
#define Key_Tree ch[ch[root][1]][0]
#define MAXN 550000
using namespace std;
int n,m;
int num[MAXN];
struct SplayTree{
int ch[MAXN][2],sz[MAXN],pre[MAXN],key[MAXN],root,tot1,tot2,sum[MAXN],maxx[MAXN],lmaxx[MAXN],rmaxx[MAXN];
int s[MAXN];
bool lazy[MAXN];
int cvr[MAXN];
int flip[MAXN];
//固定部分，不需要修改
void Rotate(int x,int kind){
int y = pre[x];
Push_Down(y);
Push_Down(x);
ch[y][!kind] = ch[x][kind];
pre[ch[x][kind]] = y;
if(pre[y]){
ch[pre[y]][ch[pre[y]][1] == y] = x;
}
pre[x] = pre[y];
ch[x][kind] = y;
pre[y] = x;
Push_Up(y);
}
void Splay(int x,int goal){
Push_Down(x);
while(pre[x] != goal){
Push_Down(pre[pre[x]]); Push_Down(pre[x]); Push_Down(x);
if(pre[pre[x]] == goal){
Rotate(x,ch[pre[x]][0] == x);
}
else{
int y = pre[x];
int kind = (ch[pre[y]][0] == y);
if(ch[y][kind] == x){
Rotate(x,!kind);
Rotate(x,kind);
}
else{
Rotate(y,kind);
Rotate(x,kind);
}
}
}
Push_Up(x);
if(!goal) root = x;
}
void RotateTo(int k,int goal){
int x = root;
Push_Down(x);
while(sz[ch[x][0]] != k){
if(k < sz[ch[x][0]]){
x = ch[x][0];
}
else{
k -= (sz[ch[x][0]]+1);
x = ch[x][1];
}
Push_Down(x);
}
Splay(x,goal);
}
//以上为固定部分，不需要修改！！！
//debug部分copy from hh
void Treaval(int x) {
//Push_Down(x);
if(x) {
Treaval(ch[x][0]);
printf("结点%2d:左儿子 %2d 右儿子 %2d 父结点 %2d size = %2d ,key = %2d,sum = %2d
",x,ch[x][0],ch[x][1],pre[x],sz[x],key[x],sum[x]);
Treaval(ch[x][1]);
}
}
void debug() {printf("%d
",root);Treaval(root);}
//以上debug
void NewNode(int& x,int father,int k){
if(tot2) x = s[tot2--];
else x = ++tot1;
pre[x] = father;
sum[x] = maxx[x] = lmaxx[x] = rmaxx[x] = key[x] = k;
if(x == 1 || x == 2) maxx[x] = lmaxx[x] = rmaxx[x] = -INF;
ch[x][0] = ch[x][1] = 0;
sz[x] = 1;
lazy[x] = false;
cvr[x] = 0;
flip[x] = 0;
}
void Update_Flip(int x){
if(!x) return;
swap(lmaxx[x],rmaxx[x]);
swap(ch[x][0],ch[x][1]);
flip[x] ^= 1;
}
void Update_Same(int x,int v){
if(!x) return;
key[x] = v;
sum[x] = v * sz[x];
lmaxx[x] = rmaxx[x] = maxx[x] = max(v,sum[x]);
cvr[x] = v;
lazy[x] = true;
}
void Push_Up(int x){
sz[x] = sz[ch[x][0]] + sz[ch[x][1]] + 1;
sum[x] = sum[ch[x][0]] + sum[ch[x][1]] + key[x];
if(ch[x][0] == 0) lmaxx[x] = key[x] + max(0,lmaxx[ch[x][1]]);
else lmaxx[x] = max(lmaxx[ch[x][0]],max(sum[ch[x][0]] + key[x],sum[ch[x][0]] + key[x] + lmaxx[ch[x][1]]));
if(ch[x][1] == 0) rmaxx[x] = key[x] + max(0,rmaxx[ch[x][0]]);
else rmaxx[x] = max(rmaxx[ch[x][1]],max(sum[ch[x][1]] + key[x],sum[ch[x][1]] + key[x] + rmaxx[ch[x][0]]));
int t = max(maxx[ch[x][0]],maxx[ch[x][1]]);
maxx[x] = key[x] + max(0,rmaxx[ch[x][0]]) + max(0,lmaxx[ch[x][1]]);
maxx[x] = max(maxx[x],t);
}
void Push_Down(int x){
if(flip[x]){
Update_Flip(ch[x][0]);
Update_Flip(ch[x][1]);
flip[x] = 0;
}
if(lazy[x]){
Update_Same(ch[x][0],cvr[x]);
Update_Same(ch[x][1],cvr[x]);
lazy[x] = false;
}
}
void Build(int& x,int l,int r,int father){
if(l > r) return;
int mid = (l+r) >> 1;
NewNode(x,father,num[mid]);
Build(ch[x][0],l,mid-1,x);
Build(ch[x][1],mid+1,r,x);
Push_Up(x);
}
void Init(){
lmaxx[0] = rmaxx[0] = maxx[0] = -INF;
sum[0] = 0;
sz[0] = 0;
root = tot1 = tot2 = 0;
sz[0] = 0;
NewNode(root,0,0);
NewNode(ch[root][1],root,0);
sz[root] = 2;
Build(Key_Tree,0,n-1,ch[root][1]);
Push_Up(ch[root][1]);
Push_Up(root);
}
void Erase(int x){
if(!x) return;
s[++tot2] = x;
Erase(ch[x][0]);
Erase(ch[x][1]);
}
void Insert(int l,int len){
RotateTo(l,0);
RotateTo(l+1,root);
Build(Key_Tree,0,len-1,ch[root][1]);
Push_Up(ch[root][1]);
Push_Up(root);
}
void Delete(int l,int r){
RotateTo(l-1,0);
RotateTo(r+1,root);
Erase(Key_Tree);
Key_Tree = 0;
Push_Up(ch[root][1]);
Push_Up(root);
}
void Modify(int l,int r,int v){
RotateTo(l-1,0);
RotateTo(r+1,root);
lazy[Key_Tree] = true;
Update_Same(Key_Tree,v);
Push_Up(ch[root][1]);
Push_Up(root);
}
void Reverse(int l,int r){
RotateTo(l-1,0);
RotateTo(r+1,root);
Update_Flip(Key_Tree);
Push_Up(ch[root][1]);
Push_Up(root);
}
int Get_Sum(int l,int r){
RotateTo(l-1,0);
RotateTo(r+1,root);
return sum[Key_Tree];
}
int Max_Sum(){
Splay(1,0);
Splay(2,root);
return maxx[Key_Tree];
}
int Get_Pre(int x){
Push_Down(x);
x = ch[x][0];
while(x){
Push_Down(x);
while(ch[x][1]){
x = ch[x][1];
Push_Down(x);
}
return x;
}
return -1;
}
int Get_Next(int x){
Push_Down(x);
x = ch[x][1];
while(x){
Push_Down(x);
while(ch[x][0]){
x = ch[x][0];
Push_Down(x);
}
return x;
}
return -1;
}
}spt;
int main()
{
//freopen("test.in","r",stdin);
while(~scanf("%d%d",&n,&m)){
FOR(i,0,n) scanf("%d",&num[i]);
spt.Init();
char str[20];
FOR(i,0,m){
scanf("%s",str);
if(strcmp(str,"INSERT") == 0){
int pos,cnt;
scanf("%d%d",&pos,&cnt);
FOR(i,0,cnt) scanf("%d",&num[i]);
spt.Insert(pos,cnt);
}
else if(strcmp(str,"DELETE") == 0){
int pos,cnt;
scanf("%d%d",&pos,&cnt);
spt.Delete(pos,pos+cnt-1);
}
else if(strcmp(str,"MAKE-SAME") == 0){
int pos,cnt,v;
scanf("%d%d%d",&pos,&cnt,&v);
spt.Modify(pos,pos+cnt-1,v);
}
else if(strcmp(str,"REVERSE") == 0){
int pos,cnt;
scanf("%d%d",&pos,&cnt);
spt.Reverse(pos,pos+cnt-1);
}
else if(strcmp(str,"GET-SUM") == 0){
int pos,cnt;
scanf("%d%d",&pos,&cnt);
printf("%d
",spt.Get_Sum(pos,pos+cnt-1));
}
else{
printf("%d
",spt.Max_Sum());
}
}
}
return 0;
}版权声明：本文为博主原创文章，未经博主允许不得转载。