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; }
When I initially commented I clicked the “Notify me when new comments are added”
checkbox and now each time a comment is added I get four e-mails with the same comment.
Is there any way you can remove people from that service?
Thank you!
You illustrate some compelling arguments.