「题解」「NOI2005」维护数列

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}\)。

下面考虑操作。

  1. 插入
    1. 把 \(\text{pos}\) 代表的点转到根,再把 \(\text{pos}+1\) 代表的点转到根节点的右儿子上;
    2. 把新数列的建立的 \(\texttt{Splay}\) 连接到 \(\text{pos}+1\) 代表的点,设为它的左儿子
  2. 删除
    1. 把 \(\text{pos}\) 代表的点转到根,再把 \(\text{pos}+\text{tot}+1\) 代表的点转到根节点的右儿子上;
    2. 把左儿子删掉
  3. 修改
    1. 把 \(\text{pos}\) 代表的点转到根,再把 \(\text{pos}+\text{tot}+1\) 代表的点转到根节点的右儿子上;
    2. 给左儿子打上修改的 \(\text{tag}\)
  4. 翻转
    1. 把 \(\text{pos}\) 代表的点转到根,再把 \(\text{pos}+\text{tot}+1\) 代表的点转到根节点的右儿子上;
    2. 给左儿子打上翻转的 \(\text{tag}\)
  5. 求和
    1. 把 \(\text{pos}\) 代表的点转到根,再把 \(\text{pos}+\text{tot}+1\) 代表的点转到根节点的右儿子上;
    2. 输出左儿子的权值和
  6. 求最大子列和
    这个跟线段树上合并差不多,输出根节点答案即可。记得有翻转标记时候要对调左右的最大子序列和

时间复杂度为 \(\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;
}

相关题目