题目：http://www.lydsy.com/JudgeOnline/problem.php?id=1500
第一次遇到这么恶心的数据结构，最开始的时候建树没有平衡建树，结果各种TLE，最大的点跑到了10s，左右，用了堆式建树速度一下子就剩下1s以内了。（建树方法：每次取出序列中中间的数建立节点，然后序列左边部分作为其左子树，右边作为其右子树，然后递归建树）（BZOJ的内存卡的挺紧的，所以要用个队列之类的回收数组节点，然后再次利用（目测在BZOJ开了O2的情况下，直接用指针的delete(),new()速度也相差无几））
操作的实现方法（splay(r,t)表示将子树t中的第r个数旋转到t所在位置，第r个数即select(r,t),s(t)表示子树大小）：
splay节点维护的信息：LS(从左起的最大连续和)，RS(从右起的最大连续和),S(区间和)，MS（最大连续和），SR（翻转标记），SC（修改标记），V（节点权值）,s（子树大小）
其中LS,RS,MS,S,V都是维护操作六必须的。
维护MS,LS,RS的递推式：
LS(t)=max(max(LS(L(t)),S(L(t))+V(t)),S(L(t))+V(t)+LS(R(t)))
RS(t)=max(max(RS(R(t)),S(R(t))+V(t)),S(R(t))+V(t)+RS(L(t)))
MS(t)=max(max(MS(L(t)),MS(R(t))),max(max(RS(L(t))+V(t),LS(R(t))+V(t)),max(V(t),RS(L(t))+LS(R(t))+V(t))))
INSERT：splay(pos,roof) splay(0,R(roof)) 然后平衡建树，把该树的根连到roof右子树的左子树上
DELETE:splay(pos-1,roof) splay(tot,R(roof)) 然后对子树L(R(roof))回收节点，再置空
MAKE-SAME：splay(pos-1,roof) splay(tot,R(roof)) 然后对子树L(R(roof))打标记
REVERSE：方法与MAKE-SAME一样
GET-SUM：splay(pos-1,roof) splay(tot,R(roof)) 然后输出子树L(R(roof))维护的序列和信息
MAX-SUM：splay(0,roof) splay(s(roof)-2,R(roof)) 然后输出子树L(R(roof))维护的最大连续和信息
代码（效率依旧平平）：
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <string>
#include <queue>
using namespace std;
#define inf (1<<19)
#define MAXN 500010
#define L(t) Left[t]
#define R(t) Right[t]
#define s(t) Size[t]
#define V(t) Value[t]
#define SR(t) Sign_Reverse[t]
#define SC(t) Sign_Change[t]
#define S(t) Sum[t]
#define LS(t) Left_Sum[t]
#define RS(t) Right_Sum[t]
#define MS(t) Max_Sum[t]
#define C(r,t) (r<s(L(t)))
queue<int>Q;
int Left[MAXN],Right[MAXN],Size[MAXN],Value[MAXN],Sum[MAXN];
bool Sign_Reverse[MAXN];
int Sign_Change[MAXN],Left_Sum[MAXN],Right_Sum[MAXN],Max_Sum[MAXN];
int n,m,a[MAXN],M=0,roof,Troof=0;
void getstring(string &c) {
c="";
int ch;
for (ch=getchar();ch==' '||ch=='\n';ch=getchar()) ;
c+=char(ch);
for (ch=getchar();ch!=' '&&ch!='\n';ch=getchar()) c+=char(ch);
}
void getint(int &t) {
int ch;
bool flag=false;
for (ch=getchar();!(ch>=int('0')&&ch<=int('9'));ch=getchar()) if (ch==int('-')) flag=true;
t=ch-int('0');
for (ch=getchar();ch>=int('0')&&ch<=int('9');ch=getchar()) t*=10,t+=ch-int('0');
t=flag?(-t):t;
}
void putint(int t) {
if (!t) { putchar(int('0')); putchar(int('\n')); return ; }
int ch[20];
ch[0]=0;
if (t<0) putchar(int('-')),t=-t;
while (t) {
ch[++ch[0]]=t%10;
t/=10;
}
for (int i=ch[0];i;i--) putchar(int('0')+ch[i]);
putchar(int('\n'));
}
void Init(int t) {
L(t)=R(t)=V(t)=S(t)=s(t)=0;
LS(t)=RS(t)=MS(t)=-inf;
SR(t)=false,SC(t)=-inf;
}
void pushdown(int t) {
if (t) {
if (SR(t)) {
swap(LS(t),RS(t)),swap(L(t),R(t));
SR(L(t))^=true,SR(R(t))^=true,SR(t)^=true;
}
if (SC(t)!=-inf) {
V(t)=SC(t);
S(t)=s(t)*SC(t);
LS(t)=RS(t)=MS(t)=max(S(t),V(t));
SC(L(t))=SC(R(t))=SC(t);
SC(t)=-inf;
}
}
}
void update(int t) {
pushdown(t);
pushdown(L(t)),pushdown(R(t));
S(t)=S(L(t))+S(R(t))+V(t),s(t)=s(L(t))+s(R(t))+1;
LS(t)=max(max(LS(L(t)),S(L(t))+V(t)),S(L(t))+V(t)+LS(R(t)));
RS(t)=max(max(RS(R(t)),S(R(t))+V(t)),S(R(t))+V(t)+RS(L(t)));
MS(t)=max(max(MS(L(t)),MS(R(t))),max(max(RS(L(t))+V(t),LS(R(t))+V(t)),max(V(t),RS(L(t))+LS(R(t))+V(t))));
}
void zag(int &t) {
pushdown(t);
pushdown(R(t));
int k=R(t);
R(t)=L(k);update(t);
L(k)=t;t=k;update(t);
}
void zig(int &t) {
pushdown(t);
pushdown(L(t));
int k=L(t);
L(t)=R(k);update(t);
R(k)=t;t=k;update(t);
}
bool splay(int r,int &t,bool flag) {
pushdown(t);
if (s(L(t))==r) {
return false;
}
bool w=splay(C(r,t)?r:r-s(L(t))-1,C(r,t)?L(t):R(t),true);
if (w) {
if (C(r,t)) {
if (C(r,L(t))) zig(t); else zag(L(t));
zig(t);
} else {
if (!C(r-s(L(t))-1,R(t))) zag(t) ; else zig(R(t));
zag(t);
}
} else if (!flag) if C(r,t) zig(t) ; else zag(t);
return w^true;
}
int New() {
if (Q.empty()) return ++M
; else {
int k=Q.front();
Q.pop();
return k;
}
}
void Delete(int t) {
if (!t) return ;
Q.push(t);
Delete(L(t)),Delete(R(t));
}
void build(int l,int r,int &t) {
if (l>r) { t=0; return ; }
int mid=(l+r)>>1;
t=New();
V(t)=a[mid],s(t)=r-l+1;
SR(t)=false,SC(t)=-inf;
build(l,mid-1,L(t)),build(mid+1,r,R(t));
update(t);
}
int main() {
while (!Q.empty()) Q.pop();
memset(Sign_Reverse,0,sizeof(Sign_Reverse));
Init(0);
getint(n),getint(m);
a[0]=a[n+1]=0;
for (int i=0;i++<n;)getint(a[i]);
build(0,n+1,roof);
while (m--) {
string c;
getstring(c);
if (c[0]=='I') {
int x,y,Rs=0;
getint(x),getint(y);
for (int i=0;i++<y;)getint(a[i]);
build(1,y,Rs);
splay(x,roof,false);
splay(0,R(roof),false);
L(R(roof))=Rs;
update(R(roof));
update(roof);
} else {
if (c[0]=='D') {
int x,y;
getint(x),getint(y);
splay(x-1,roof,false);
splay(y,R(roof),false);
Delete(L(R(roof)));
L(R(roof))=0;
update(R(roof));
update(roof);
} else {
if (c[0]=='M') {
if (c[2]=='K') {
int x,y,z;
getint(x),getint(y),getint(z);
splay(x-1,roof,false);
splay(y,R(roof),false);
SC(L(R(roof)))=z;
update(R(roof));
update(roof);
} else {
splay(0,roof,false);
splay(s(roof)-2,R(roof),false);
putint(MS(L(R(roof))));
}
} else if (c[0]=='R') {
int x,y;
getint(x),getint(y);
splay(x-1,roof,false);
splay(y,R(roof),false);
SR(L(R(roof)))^=true;
update(R(roof));
update(roof);
} else {
int x,y;
getint(x),getint(y);
splay(x-1,roof,false);
splay(y,R(roof),false);
putint(S(L(R(roof))));
}
}
}
}
return 0;
}
网友评论