维修数列 Splay(这可能是我写过最麻烦的题之一了。。。用平衡树维护dp。。。丧心病狂啊。。。。)
2024-10-12 06:33:53
题目来源BZOJ1500
这题的思路：
1、这题的话，稍微会splay的人，一般前面四个都不是问题。。主要是最后的一个，要你在修改的同时要维护好最大字段和。。。
2、最大字段和其实就是区间合并。具体操作可以看POJ2750，这是这道题的简化版本。
3、然后这题就是三个区间合并嘛。。。慢慢讨论就好了。。。这题写了我一天的时间。。从吃完午饭一直写到了晚上8点才AC。。。
直接贴代码吧。。这题是我为了学LCT，所以想做做Splay的题先熟悉一下Splay。。。结果选了这个BOSS题。。。心理阴影。。。。
我觉得我pushup那段写的挺清楚的23333 思路可以看我的pushup和pushdown函数的代码，应该挺好懂的
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<stack> using namespace std; const int N=,INF=0x3f3f3f3f; struct Splay_Tree
{
struct Node
{
int val,sum,cover,Size,son[],mxl,mxr,mx;
bool rev,cov;
void init(int _val)
{
val=sum=mxl=mxr=mx=_val;
Size=;
rev=cov=cover=son[]=son[]=;
}
} T[N];
stack<int>mem;
int fa[N],root,tot; void pushDown(int x)///下放标记（序列操作）
{
if(x==)return ;
if(T[x].cov)
{
if(T[x].son[])
{
T[T[x].son[]].cov=;
T[T[x].son[]].cover=T[T[x].son[]].val=T[x].cover;
T[T[x].son[]].sum=T[x].cover*T[T[x].son[]].Size;
T[T[x].son[]].rev=;
if(T[x].cover>=)
T[T[x].son[]].mx=T[T[x].son[]].mxl=T[T[x].son[]].mxr=T[x].cover*T[T[x].son[]].Size;
else
T[T[x].son[]].mx=T[T[x].son[]].mxl=T[T[x].son[]].mxr=T[x].cover;
}
if(T[x].son[])
{
T[T[x].son[]].cov=;
T[T[x].son[]].cover=T[T[x].son[]].val=T[x].cover;
T[T[x].son[]].sum=T[x].cover*T[T[x].son[]].Size;
T[T[x].son[]].rev=;
if(T[x].cover>=)
T[T[x].son[]].mx=T[T[x].son[]].mxl=T[T[x].son[]].mxr=T[x].cover*T[T[x].son[]].Size;
else
T[T[x].son[]].mx=T[T[x].son[]].mxl=T[T[x].son[]].mxr=T[x].cover;
}
T[x].cov=T[x].cover=T[x].rev=;
}
if(T[x].rev)
{
if(T[x].son[])
{
T[T[x].son[]].rev^=;
swap(T[T[x].son[]].mxl,T[T[x].son[]].mxr);
}
if(T[x].son[])
{
T[T[x].son[]].rev^=;
swap(T[T[x].son[]].mxl,T[T[x].son[]].mxr);
}
swap(T[x].son[],T[x].son[]);
T[x].rev=;
}
} void pushUp(int x)///更新节点（序列操作）
{
T[x].Size=;
T[x].sum=T[x].val;
if(T[x].son[])
T[x].sum+=T[T[x].son[]].sum,T[x].Size+=T[T[x].son[]].Size;
if(T[x].son[])
T[x].sum+=T[T[x].son[]].sum,T[x].Size+=T[T[x].son[]].Size; if(T[x].son[]&&T[x].son[])
{
T[x].mx=T[x].val;
T[x].mx=max(T[x].mx,T[T[x].son[]].mx);
T[x].mx=max(T[x].mx,T[T[x].son[]].mx);
T[x].mx=max(T[x].mx,T[T[x].son[]].mxr+T[x].val+T[T[x].son[]].mxl);
T[x].mx=max(T[x].mx,T[x].val+T[T[x].son[]].mxr);
T[x].mx=max(T[x].mx,T[x].val+T[T[x].son[]].mxl); T[x].mxl=T[T[x].son[]].mxl;
T[x].mxl=max(T[x].mxl,T[T[x].son[]].sum+T[x].val);
T[x].mxl=max(T[x].mxl,T[T[x].son[]].sum+T[x].val+T[T[x].son[]].mxl); T[x].mxr=T[T[x].son[]].mxr;
T[x].mxr=max(T[x].mxr,T[T[x].son[]].sum+T[x].val);
T[x].mxr=max(T[x].mxr,T[T[x].son[]].sum+T[x].val+T[T[x].son[]].mxr);
}
else if(T[x].son[]&&!T[x].son[])
{
T[x].mx=max(T[T[x].son[]].mxr+T[x].val,T[T[x].son[]].mx); T[x].mx=max(T[x].mx,T[x].val); T[x].mxl=max(T[T[x].son[]].mxl,T[T[x].son[]].sum+T[x].val); T[x].mxr=max(T[x].val,T[x].val+T[T[x].son[]].mxr);
}
else if(!T[x].son[]&&T[x].son[])
{
T[x].mx=max(T[T[x].son[]].mxl+T[x].val,T[T[x].son[]].mx); T[x].mx=max(T[x].mx,T[x].val); T[x].mxl=max(T[x].val,T[x].val+T[T[x].son[]].mxl); T[x].mxr=max(T[T[x].son[]].mxr,T[T[x].son[]].sum+T[x].val);
}
else T[x].mxl=T[x].mxr=T[x].mx=T[x].val; } /*inline void up(int x)///更新节点（普通平衡树操作）
{
T[x].Size=1;
if(T[x].son[0])
T[x].Size+=T[T[x].son[0]].Size;
if(T[x].son[1])
T[x].Size+=T[T[x].son[1]].Size;
}*/ void Rotate(int x,int kind)///旋转，有左旋右旋（反正配合splay用就好了233）
{
int y=fa[x],z=fa[y];
T[y].son[!kind]=T[x].son[kind],fa[T[x].son[kind]]=y;
T[x].son[kind]=y,fa[y]=x;
T[z].son[T[z].son[]==y]=x,fa[x]=z;
pushUp(y);
} void Splay(int x,int goal)///把下标为x的元素旋转到目标的儿子节点
{
if(x==goal)return ;
while(fa[x]!=goal)
{
int y=fa[x],z=fa[y];
pushDown(z),pushDown(y),pushDown(x);
int rx=T[y].son[]==x,ry=T[z].son[]==y;
if(z==goal)Rotate(x,rx);
else
{
if(rx==ry)Rotate(y,ry);
else Rotate(x,rx);
Rotate(x,ry);
}
}
pushUp(x);
if(goal==)root=x;
} int Select(int pos)///查找第k小元素
{
pos--;
int u=root;
pushDown(u);
while(T[T[u].son[]].Size!=pos)
{
if(pos<T[T[u].son[]].Size)u=T[u].son[];
else
{
pos-=T[T[u].son[]].Size+;
u=T[u].son[];
}
pushDown(u);
}
return u;
} void Reverse(int L,int R)///序列操作的区间翻转
{
if(L>R)return ;
int u=Select(L-),v=Select(R+);
Splay(u,);
Splay(v,u);
T[T[v].son[]].rev^=;
swap(T[T[v].son[]].mxl,T[T[v].son[]].mxr);
pushDown(T[v].son[]);
update(T[v].son[]);
} void Cover(int L,int R,int Val)///序列操作的区间翻转
{
if(L>R)return ;
int u=Select(L-),v=Select(R+);
Splay(u,);
Splay(v,u);
T[T[v].son[]].cov=;
T[T[v].son[]].cover=T[T[v].son[]].val=Val;
pushDown(T[v].son[]);
update(T[v].son[]);
} int build(int L,int R,int *a)///区间操作建树
{
if(L>R)return ;
int mid=(L+R)>>,sL,sR;
int loc=mem.top();mem.pop();
T[loc].init(a[mid]);
if(L==R)return loc;
T[loc].son[]=sL=build(L,mid-,a);
T[loc].son[]=sR=build(mid+,R,a);
fa[sL]=fa[sR]=loc;
pushUp(loc);
return loc;
} void init(int n,int *a)///区间操作，输入n个元素建树
{
T[].init(INF);
for(int i=;i>=;i--)
mem.push(i);
root=build(,n,a),fa[root]=;
fa[]=,T[].son[]=root,T[].Size=;
} void Insert(int pos,int n,int *a)
{
if(n==)return ;
int u=Select(pos-),v=Select(pos);
Splay(u,);
Splay(v,u);
fa[T[v].son[]=build(,n,a)]=v;
update(T[v].son[]);
} void Delete(int L,int R)
{
if(L>R)return ;
int u=Select(L-),v=Select(R+);
Splay(u,);
Splay(v,u);
Free(T[v].son[]);
T[v].son[]=;
update(v);
} int Get_sum(int L,int R)
{
if(L>R)return ;
int u=Select(L-),v=Select(R+);
Splay(u,);
Splay(v,u);
if(T[v].son[])
return T[T[v].son[]].sum;
else return ;
} int Get_max(int L,int R)
{
if(L>R)return ;
int u=Select(L-),v=Select(R+);
Splay(u,);
Splay(v,u);
if(T[v].son[])
return T[T[v].son[]].mx;
else return ;
} void Free(int x)
{
if(x==)return ;
Free(T[x].son[]);
mem.push(x);
Free(T[x].son[]);
} /*void Insert(int &t,int val,int par=0)///普通平衡树，往某个地方的下面插入元素，一般是插入根节点
{
if(t==0)
{
t=++tot;
T[t].init(val);
fa[t]=par;
Splay(tot,0);
}
else
{
int cur=t;
if(val<T[t].val)Insert(T[t].son[0],val,cur);
//else if(val==T[t].val)return ;
else Insert(T[t].son[1],val,cur);
up(cur);
}
}*/ /*int find(int t,int v)///普通平衡树查找值为v的元素
{
if(t==0)return 0;
else if(T[t].val==v)
{
Splay(t,0);
return t;
}
else if(v<T[t].val)return find(T[t].son[0],v);
else return find(T[t].son[1],v);
}*/ ///删除根节点元素
/*void Delete()
{
if(!T[root].son[0])
{
fa[T[root].son[1]]=0;
root=T[root].son[1];
}
else
{
int cur=T[root].son[0];
while(T[cur].son[1])cur=T[cur].son[1];
Splay(cur,root);
T[cur].son[1]=T[root].son[1];
root=cur,fa[cur]=0,fa[T[root].son[1]]=root;
up(root);
}
}*/ int size()
{
return T[root].Size;
} ///从t开始找值为v的前驱,返回值
int pred(int t,int v)
{
if(t==)return v;
else
{
if(v<=T[t].val)return pred(T[t].son[],v);
else
{
int ans=pred(T[t].son[],v);
if(ans==v)
ans=T[t].val,Splay(t,);
return ans;
}
}
}
///查找下标t节点的前驱返回下标
int pred(int t)
{
Splay(t,);
int u=T[t].son[];
if(u==)return fa[t];
while(T[u].son[])u=T[u].son[];
return u;
} ///从t开始找值为v的后继,返回值
int succ(int t,int v)
{
if(t==)return v;
else
{
if(v>=T[t].val)return succ(T[t].son[],v);
else
{
int ans=succ(T[t].son[],v);
if(ans==v)
ans=T[t].val,Splay(t,);
return ans;
}
}
} ///查找下标t节点的后继返回下标
int succ(int t)
{
Splay(t,);
int u=T[t].son[];
if(u==)return fa[t];
while(T[u].son[])u=T[u].son[];
return u;
} void Preorder( int t ){///输出成序列顺便检查是否有逻辑错误
if( !t ) return;
pushDown(t);
Preorder( T[t].son[] );
if(T[t].son[]&&fa[T[t].son[]]!=t)
printf("!");
printf("%d " , T[t].val );
Preorder( T[t].son[] );
} /*void init()///普通平衡树初始化
{
T[0].init(-INF);
tot=root=0;
}*/ void update(int x)///更新下标为x的节点。。手动操作后调用
{
while(x!=)
pushUp(x),x=fa[x];
} }; Splay_Tree tree; int a[N]; char str[]; int main()
{
int n,m;
scanf("%d%d",&n,&m);
for(int i=;i<=n+;i++)
scanf("%d",a+i);
tree.init(n+,a);
int sum=n;
while(m--)
{
scanf("%s",str+);
if(str[]=='S')
{
int pos,tot;
scanf("%d%d",&pos,&tot);
pos++;
pos++;
sum+=tot;
for(int i=;i<=tot;i++)
scanf("%d",a+i);
tree.Insert(pos,tot,a);
}
else if(str[]=='L')
{
int pos,tot;
scanf("%d%d",&pos,&tot);
pos++;
tree.Delete(pos,pos+tot-);
sum-=tot;
}
else if(str[]=='K')
{
int pos,tot,cov;
scanf("%d%d%d",&pos,&tot,&cov);
pos++;
tree.Cover(pos,pos+tot-,cov);
}
else if(str[]=='V')
{
int pos,tot;
scanf("%d%d",&pos,&tot);
pos++;
tree.Reverse(pos,pos+tot-);
}
else if(str[]=='T')
{
int pos,tot;
scanf("%d%d",&pos,&tot);
pos++;
printf("%d\n",tree.Get_sum(pos,pos+tot-));
}
if(str[]=='X')
{
printf("%d\n",tree.Get_max(,tree.size()-));
}
}
return ;
}
最新文章
- JAVA中的字符串小结
- HDU 5923 Prediction
- C#，往线程里传参数的方法总结
- 25.usb固件深入
- SQL创建链接服务器
- 一个读取propeties配置文件的工具类，线程安全的
- Bootstrap定制(一)less入门及编译
- Caché Monitor 2.03发布，Caché的SQL开发工具 - 开源中国社区
- 飞鱼相册笔记(1)----外置SD卡文件夹名称不区分大小写
- LeetCode专题-Python实现之第28题： Implement strStr()
- BZOJ 1001 - 狼抓兔子 - [Dinic最大流][对偶图最短路]
- labview之连接MySQL数据库
- [C#] DataTable转成List集合
- MySQL order null 0 - 把null和0(零)排在最后
- pycharm 工具栏Tool中找不到Run manager.py Task
- elementUI表格合并单元格
- 使用pako.js实现gzip的压缩和解压
- Selenium webdriver Java 封装与重用
- 四、golang内置函数、递归、闭包、数组切片和map
- java的几个特性