题目链接
解题思路
看了题解区，竟然没有人写可爱的左偏树。
我们需要支持四种操作：
- 删除集合中的元素。
- 取集合中的最小值。
- 合并两个集合。
- 修改集合中的元素。
那么我们可以用常数极小的左偏树（可并堆） 来解决这道模板题。
对于左偏树的基础操作，详见左偏树-OI Wiki或洛谷 P3377【模板】左偏树/可并堆。
在支持删除元素的情况下，我们在进行 push_up 操作时需要查找节点 \(x\) 的父节点，因此无法使用路径压缩来查找左偏树的根节点。如果直接向上查找根节点，会导致 TLE。
为了解决这个问题，我们可以引入一个 root 数组，其中 \(root_x\) 存储集合 \(S_x\) 的根节点下标。在每次执行 merge、erase 和 push_up 操作时，对 root 数组进行相应的更新。
在删除操作中，可以直接将元素 \(x\) 从左偏树中删除，然后重新初始化元素 \(x\)，将其作为一个独立的左偏树，再将其合并回原来的左偏树，保证了堆的性质。
此外，对于修改操作，还有另一种更高效的处理方式。由于题目保证 \(z<a_y\)，我们可以在修改 \(x\) 的权值后与其父节点进行比较。如果 \(x\) 的父节点的权值大于 \(x\) 的权值，则交换 \(x\) 和其父节点的位置。这样常数极小但是我写挂了。
整体时间复杂度为 \(O(m\log{n})\)，跑得飞快。
以下是使用朴素修改操作的左偏树 AC 代码的提交记录，仅仅跑了 \(325\) ms，比最优解手写巨大数据结构的大佬慢了 \(19\) ms。
参考代码
#include<bits/stdc++.h>
using namespace std;
namespace IO
{
char buf[1<<20],*p1,*p2;
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<20,stdin),p1==p2)?EOF:*p1++)
template<typename T>inline T read(T& x)
{
char ch=getchar();bool f=true;x=0;
while(ch<'0'||ch>'9') f&=(bool)(ch^'-'),ch=getchar();
while(ch>='0'&&ch<='9') x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
return x=f?x:-x;
}
char pbuf[1<<20],*pp=pbuf;
inline void push(const char x){if(pp-pbuf==1<<20) fwrite(pbuf,1,1<<20,stdout),pp=pbuf;*pp++=x;}
inline void flush(){fwrite(pbuf,1,pp-pbuf,stdout);pp=pbuf;}
#define putchar(x) push(x)
template<typename T>void print(const T x)
{
if(x<0){putchar('-');print(-x);return ;}
if(x>9) print(x/10);putchar(x%10^48);
}
template<typename T,typename... Args>inline void read(T& x,Args&... args){read(x);read(args...);}
template<typename T>inline void print(const T x,const char ch){print(x);putchar(ch);}
#undef getchar
#undef putchar
#define getchar() (IO::p1==IO::p2&&(IO::p2=(IO::p1=IO::buf)+fread(IO::buf,1,1<<20,stdin),IO::p1==IO::p2)?EOF:*IO::p1++)
#define putchar(x) IO::push(x)
#define flush() IO::flush()
}using IO::read,IO::print;
typedef long long ll;
const int N=1e6+1;
int n,m;
int root[N];
struct ZPS{int ls,rs,dis,fa;ll val;}tree[N];
#define ls(x) tree[x].ls
#define rs(x) tree[x].rs
int merge(int x,int y)
{
if(!x||!y) return x|y;
if(tree[x].val>tree[y].val||(tree[x].val==tree[y].val&&x>y)) swap(x,y);
rs(x)=merge(rs(x),y);
if(tree[ls(x)].dis<tree[rs(x)].dis) swap(ls(x),rs(x));
tree[x].dis=tree[rs(x)].dis+1;
return tree[ls(x)].fa=tree[rs(x)].fa=tree[x].fa=x;
}
void push_up(const int x)
{
if(!x) return ;
if(tree[ls(x)].dis<tree[rs(x)].dis) swap(ls(x),rs(x));
if(tree[x].dis^(tree[ls(x)].dis+1))
tree[x].dis=tree[ls(x)].dis+1,push_up(tree[x].fa);
}
inline int erase(const int x,const int pos)
{
int y=merge(ls(x),rs(x));
if(tree[x].fa^x)
{
tree[y].fa=tree[x].fa;
if(ls(tree[y].fa)==x) ls(tree[y].fa)=y;
if(rs(tree[y].fa)==x) rs(tree[y].fa)=y;
push_up(tree[y].fa);
}else root[pos]=tree[y].fa=y;
tree[x].fa=y;ls(x)=rs(x)=0;
return pos;
}
inline ll top(const int pos){return tree[root[pos]].val;}
inline void modify(const int x,const int k,const int pos){erase(x,pos);tree[x]={0,0,1,x,k};root[pos]=merge(root[pos],x);}
int main()
{
#ifndef ONLINE_JUDGE
freopen("awa.in","r",stdin);
freopen("awa.out","w",stdout);
#endif
read(n,m);
for(int i=1;i<=n;++i) read(tree[i].val),tree[i].dis=1,tree[i].fa=root[i]=i;
int opt;ll x,y,z;
while(m--)
switch(read(opt))
{
case 0:read(x,y),erase(y,x);break;
case 1:read(x),print(top(x),'\n');break;
case 2:read(x,y),root[x]=merge(root[x],root[y]);break;
case 3:read(x,y,z),modify(y,z,x);break;
}
flush();
return 0;
}