NOI2005 Day 1 T2，一道 \(\texttt{Splay}\) 的题目。
题目链接：Luogu P2042/BZOJ 1500/NOI2005 D1T2。
题目
题目描述
请写一个程序，要求维护一个数列，支持以下 \(6\) 种操作：
| 编号 | 名称 | 格式 | 说明 |
|---|---|---|---|
| \(1\) | 插入 | \(\operatorname{INSERT}\ \text{pos} _ i \ \text{tot}\ c _ 1\ c_2\cdots c _ \text{tot}\) | 在当前数列的第 \(\text{pos} _ i\) 个数字后插入 \(\text{tot}\) 个数字：\(c _ 1,c _ 2\cdots c _ \text{tot}\)。 |
| \(2\) | 删除 | \(\operatorname{DELETE}\ \text{pos} _ i\ \text{tot}\) | 从当前数列的第 \(\text{pos} _ i\) 个数字开始连续删除 \(\text{tot}\) 个数字。 |
| \(3\) | 修改 | \(\operatorname{MAKE-SAME}\ \text{pos} _ i\ \text{tot}\ c\) | 从当前数列的第 \(\text{pos} _ i\) 个数字开始的连续 \(\text{tot}\) 个数字统一修改为 \(c\)。 |
| \(4\) | 翻转 | \(\operatorname{REVERSE}\ \text{pos} _ i\ \text{tot}\) | 取出从当前数列的第 \(\text{pos} _ i\) 个数字开始的 \(\text{tot}\) 个数字，翻转后放入原来的位置。 |
| \(5\) | 求和 | \(\operatorname{GET-SUM}\ \text{pos} _ i\ \text{tot}\) | 计算从当前数列的第 \(\text{pos} _ i\) 个数字开始的 \(\text{tot}\) 个数字的和并输出。 |
| \(6\) | 求最大子列和 | \(\operatorname{MAX-SUM}\) | 求出当前数列中和最大的一段子列，并输出最大和。 |
数据范围
- 你可以认为在任何时刻，数列中至少有 \(1\) 个数。
- 输入数据一定是正确的，即指定位置的数在数列中一定存在。
- 对于 \(50\%\) 的数据，任何时刻数列中最多含有 \(3 \times 10^4\) 个数。
- 对于 \(100\%\) 的数据，任何时刻数列中最多含有 \(5 \times 10^5\) 个数，任何时刻数列中任何一个数字均在 \([-10^3, 10^3]\) 内，\(1\leq M\leq 2\times 10^4\)，插入的数字总数不超过 \(4\times 10^6\)。
时空限制
| 题目编号 | 时间限制 | 空间限制 |
| Luogu P2042 | \(1\text{s}\) | \(128\text{MiB}\) |
| BZOJ 1500 | \(1\text{s}\) | \(128\text{MiB}\) |
| NOI2005 D1T2 | \(1\text{s}\) | \(128\text{MiB}\) |
题解
思路
考虑用 \(\texttt{Splay}\) 解决这个问题。以在数列中的序号为键值建一棵 \(\texttt{Splay}\)。
下面考虑操作。
- 插入
- 把 \(\text{pos}\) 代表的点转到根，再把 \(\text{pos}+1\) 代表的点转到根节点的右儿子上；
- 把新数列的建立的 \(\texttt{Splay}\) 连接到 \(\text{pos}+1\) 代表的点，设为它的左儿子。
- 删除
- 把 \(\text{pos}\) 代表的点转到根，再把 \(\text{pos}+\text{tot}+1\) 代表的点转到根节点的右儿子上；
- 把左儿子删掉。
- 修改
- 把 \(\text{pos}\) 代表的点转到根，再把 \(\text{pos}+\text{tot}+1\) 代表的点转到根节点的右儿子上；
- 给左儿子打上修改的 \(\text{tag}\)。
- 翻转
- 把 \(\text{pos}\) 代表的点转到根，再把 \(\text{pos}+\text{tot}+1\) 代表的点转到根节点的右儿子上；
- 给左儿子打上翻转的 \(\text{tag}\)。
- 求和
- 把 \(\text{pos}\) 代表的点转到根，再把 \(\text{pos}+\text{tot}+1\) 代表的点转到根节点的右儿子上；
- 输出左儿子的权值和。
- 求最大子列和
这个跟线段树上合并差不多，输出根节点答案即可。记得有翻转标记时候要对调左右的最大子序列和。
时间复杂度为 \(\Theta(n\log _ 2n)\)。
代码
#include<bits/stdc++.h>
using namespace std;
#define reg register
#define INF 0X3F3F3F3F
#define TAGNONE INF
inline int read(void){
reg bool f=false;
reg char ch=getchar();
reg int res=0;
while(ch<'0'||'9'<ch)f|=(ch=='-'),ch=getchar();
while('0'<=ch&&ch<='9')res=10*res+ch-'0',ch=getchar();
return f?-res:res;
}
const int MAXN=1000000+5;
int n,m;
namespace Splay{
struct Node{
int fa,ch[2];
int size;
int val,sum;
int tag,rev;
int lMax,rMax,Max;
inline void clear(void){
fa=ch[0]=ch[1]=rev=0;
tag=TAGNONE;
return;
}
#define fa(x) unit[(x)].fa
#define ch(x) unit[(x)].ch
#define lson(x) unit[(x)].ch[0]
#define rson(x) unit[(x)].ch[1]
#define size(x) unit[(x)].size
#define val(x) unit[(x)].val
#define sum(x) unit[(x)].sum
#define tag(x) unit[(x)].tag
#define rev(x) unit[(x)].rev
#define lMax(x) unit[(x)].lMax
#define rMax(x) unit[(x)].rMax
#define Max(x) unit[(x)].Max
};
int a[MAXN],id[MAXN];
int tot;
int root;
int top,S[MAXN];
Node unit[MAXN];
inline int New(void){
if(top)
return S[top--];
else
return ++tot;
}
inline void Set(reg int u,int Val){
if(!u)
return;
tag(u)=val(u)=Val;
sum(u)=Val*size(u);
lMax(u)=rMax(u)=max(sum(u),0);
Max(u)=max(sum(u),Val);
return;
}
inline void reverse(reg int u){
swap(lson(u),rson(u));
swap(lMax(u),rMax(u));
rev(u)^=1;
return;
}
inline void pushup(reg int u){
sum(u)=sum(lson(u))+sum(rson(u))+val(u);
size(u)=size(lson(u))+size(rson(u))+1;
Max(u)=max(max(Max(lson(u)),Max(rson(u))),rMax(lson(u))+lMax(rson(u))+val(u));
lMax(u)=max(lMax(lson(u)),sum(lson(u))+lMax(rson(u))+val(u));
rMax(u)=max(rMax(rson(u)),sum(rson(u))+rMax(lson(u))+val(u));
return;
}
inline void pushdown(reg int u){
if(tag(u)!=TAGNONE){
Set(lson(u),tag(u));
Set(rson(u),tag(u));
tag(u)=TAGNONE;
}
if(rev(u)){
reverse(lson(u));
reverse(rson(u));
rev(u)=false;
}
return;
}
inline bool get(reg int u){
return rson(fa(u))==u;
}
inline void rotate(reg int x){
int y=fa(x),z=fa(y),dir=get(x);
ch(z)[get(y)]=x;
fa(x)=z;
ch(y)[dir]=ch(x)[dir^1];
fa(ch(x)[dir^1])=y;
ch(x)[dir^1]=y,fa(y)=x;
pushup(y),pushup(x);
return;
}
inline void splay(reg int x,reg int goal){
for(reg int f;f=fa(x),f!=goal;rotate(x))
if(fa(f)!=goal)
rotate(get(x)!=get(f)?x:f);
if(!goal)
root=x;
return;
}
inline void New(reg int u,int Val){
Max(u)=sum(u)=Val;
tag(u)=TAGNONE;
rev(u)=0;
lMax(u)=rMax(u)=max(Val,0);
size(u)=1;
return;
}
inline void Build(reg int l,reg int r,reg int father){
if(r<l)
return;
reg int mid=(l+r)>>1;
int u=id[mid],pre=id[father];
if(l==r)
New(u,a[l]);
Build(l,mid-1,mid);
Build(mid+1,r,mid);
val(u)=a[mid],fa(u)=pre,
tag(u)=TAGNONE;
pushup(u);
ch(pre)[mid>=father]=u;
return;
}
inline int kth(reg int k){
reg int u=root;
while(true){
pushdown(u);
if(k<=size(lson(u)))
u=lson(u);
else if(k==size(lson(u))+1)
return u;
else{
k-=size(lson(u))+1;
u=rson(u);
}
}
}
inline void remove(reg int u){
if(lson(u))
remove(lson(u));
if(rson(u))
remove(rson(u));
S[++top]=u;
unit[u].clear();
return;
}
inline int split(reg int pos,reg int len){
reg int l=kth(pos),r=kth(pos+len+1);
splay(l,0),splay(r,l);
return lson(r);
}
inline void query(reg int pos,reg int len){
reg int u=split(pos,len);
printf("%d\n",sum(u));
return;
}
inline void update(reg int pos,reg int len,reg int Val){
reg int u=split(pos,len),f=fa(u);
Set(u,Val);
pushup(f),pushup(fa(f));
return;
}
inline void reverse(reg int pos,reg int len){
reg int u=split(pos,len),f=fa(u);
if(tag(u)!=TAGNONE)
return;
reverse(u);
pushup(f),pushup(fa(f));
return;
}
inline void erase(reg int pos,reg int len){
reg int u=split(pos,len),f=fa(u);
remove(u);
lson(f)=0;
pushup(f),pushup(fa(f));
return;
}
inline void insert(reg int pos,reg int len){
for(reg int i=1;i<=len;++i)
a[i]=read();
for(reg int i=1;i<=len;++i)
id[i]=New();
Build(1,len,0);
reg int z=id[(1+len)>>1];
int x=kth(pos+1),y=kth(pos+2);
splay(x,0),splay(y,x);
fa(z)=y;
lson(y)=z;
pushup(y),pushup(x);
return;
}
}
using namespace Splay;
int main(void){
n=read(),m=read();
unit[0].Max=a[1]=a[n+2]=-INF;
for(reg int i=1;i<=n;++i)
a[i+1]=read();
for(reg int i=1;i<=n+2;++i)
id[i]=i;
Build(1,n+2,0);
root=(n+3)>>1;
tot=n+2;
for(reg int i=1;i<=m;++i){
static string str;
static int pos,tot,c;
cin>>str;
if(str=="MAX-SUM")
printf("%d\n",unit[root].Max);
else{
pos=read(),tot=read();
if(str=="INSERT")
insert(pos,tot);
else if(str=="DELETE")
erase(pos,tot);
else if(str=="REVERSE")
reverse(pos,tot);
else if(str=="GET-SUM")
query(pos,tot);
else if(str=="MAKE-SAME"){
c=read();
update(pos,tot,c);
}
}
}
return 0;
}
近期评论