欲承之冠，以造极之锋芒；
俯首之势，作缄默之冷妄。
堆
堆是一个树型结构，拥有左儿子和右儿子。
满足性质【父结点权值大于子结点】的堆称为大根堆；
满足性质【父结点权值小于子结点】的堆称为小根堆。
常见的，std::priority_queue 的初始就是一个大根堆。（$\text{Stl}$ 大法吼啊）
可并堆/配对堆
见 $\text{OI-Wiki}$ 。
说实话，堆需要学习的，就左偏树就够了。
左偏树
拥有线段树合并的部分功能，且码量极小。
功能
可以维护一个堆（一个集合），支持操作：
- 插入一个数；效率 $\mathcal O(\log n)$ ；
- 求取最小值；效率 $\mathcal O(1)$ ；
- 删除最小值；（或任意值），删除最小值的效率为 $\mathcal O(\log n)$ ；
- 合并堆（两棵树），效率 $\mathcal O(\log n)$ 。
而左偏树的特性就在于第四个操作。
实现
以小根堆为例。
左偏树的每一个结点都会维护一些信息：
| $val$ |
$dist$ |
| 点权值 |
到最近空结点的距离 |
定义叶结点的 $dist$ 为 $1$ ，左偏树的左偏性质在于【左儿子的 $dist$ 大于右儿子的 $dist$】，即左子树比右子树更深。
左偏树操作的复杂度与距离成正比，且 $\mathcal O(\log n)$ 为上界。
有性质：$dist[root]\leq\mathcal O(\log n)$ 。
定义函数 $f(k)$ 表示距离为 $k$ 的点的子树至少包含了 $f(k)$ 个点。
可以知道 $f(1)=1$ ，并容易证明 $f(k)\geq 2^k-1$ 。
假设 $n=k-1$ 时成立，证明 $n=k$ 时成立。
设 $dist[root]=k$
则 $dist[root.rightson]=k-1$
且 $dist[root.leftson]\geq k-1$
则 $f(root)=f(root.leftson)+f(root.rightson)$
则 $f(n)\geq(2^{n-1}-1)+(2^{n-1}-1)+1$
化简得到 $f(n)\geq 2^n-1$ 。
所以有 $dist\leq\mathcal O(\log n)$ 。
合并
定义函数 merge(a,b) 为合并 $a,b$ 两棵子树并返回合并后的根结点。
首先比较 $a_{root}$ 和 $b_{root}$ 的深度，返回较小的值作为根结点，记为 $c$ 。
从 $c$ 开始向下递归，将剩下的子树（假设 $c$ 为 $a$ ，剩余 $b$）$b$ 与 $a$ 的右子树合并。并维护左偏性质，可以将 $c$ 的左右子树进行交换。
期望复杂度 $\mathcal O(dist[a]+dist[b])$ ，实际复杂度 $\mathcal O(\log n)$ 。
插入
建立原根堆，与需要插入的数，共两个堆，并将两个堆合并。
删除
删除根结点，并合并左子树和右子树。
查询极值
直接返回根结点。
例题
我们需要同时维护 $n$ 个左偏树和一套并查集以查询当前的 $(x,y)$ 的所属，并直接合并其并查代表元素。
这里的并查集与左偏树必须对应，而并查集并不支持删除操作，且左偏树在合并之后会形成一个新的左偏树，会与并查的映射偏离。如果每次删除操作重置初始化的话，时间复杂度会高达 $\mathcal O(n)$ ，有悖题意。
不过，容易想到，并查集的映射并不会影响我们左偏树的查询，所以，我们不需要去删除并查集的点，因为不会影响后续答案。
但是，我们必须保证并查集的代表元素是新左偏树的根结点，所以我们需要对并查集进行换根。这个操作只有一步，就是把原来的代表元素指向新的根结点就行了。不理解的读者可以去重修一下并查集。
对于洛谷的这道模板题，会出现一个输出 -1 的情况，所以给出一个 $Del[x]$ 数组表示当前数是否被删除过，即可
AC Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
| #include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<ctime>
#include<iomanip>
#include<queue>
#include<stack>
#include<map>
#include<vector>
#define gh() getchar()
#define re register
typedef long long ll;
template<class T>
inline void read(T &x)
{
x=0;
char ch=gh(),t=0;
while(ch<'0'||ch>'9') t|=ch=='-',ch=gh();
while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=gh();
if(t) x=-x;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1)
{
read(x),read(x1...);
}
template<class T>
inline void write(T x)
{
if(x<0) putchar('-'),x=-x;
if(x>9) write(x/10);
putchar(x%10+'0');
}
template<class T>
inline bool checkMax(T &x,T &y)
{
return x<y?x=y,1:0;
}
template<class T>
inline bool checkMin(T &x,T &y)
{
return x>y?x=y,1:0;
}
const int MAXN=2e5+10;
const int INF=0x3f3f3f3f;
int N,M,Val[MAXN],Dist[MAXN];
int Fa[MAXN],Le[MAXN],Ri[MAXN];
bool Del[MAXN];
inline bool Cmp(int x,int y)
{
if(Val[x]==Val[y]) return x<y;
return Val[x]<Val[y];
}
int getFa(int x)
{
return Fa[x]==x?x:Fa[x]=getFa(Fa[x]);
}
int merge(int x,int y)
{
if(!x||!y) return x+y;
if(Cmp(y,x)) std::swap(x,y);
Ri[x]=merge(Ri[x],y);
if(Dist[Ri[x]]>Dist[Le[x]]) std::swap(Le[x],Ri[x]);
Dist[x]=Dist[Ri[x]]+1;
return x;
}
int main()
{
read(N,M);
Dist[0]=-1;
for(int i=1;i<=N;++i) read(Val[i]),Fa[i]=i;
while(M--)
{
int opt;
read(opt);
if(opt==1)
{
int x,y;read(x,y);
if(Del[x]||Del[y]) continue;
x=getFa(x),y=getFa(y);
if(x!=y)Fa[x]=Fa[y]=merge(x,y);
}
else
{
int x;read(x);
if(Del[x])
{
puts("-1");
continue;
}
x=getFa(x);
Del[x]=1;
write(Val[x]),puts("");
Fa[x]=Fa[Ri[x]]=Fa[Le[x]]=merge(Le[x],Ri[x]);
Dist[x]=Le[x]=Ri[x]=0;
}
}
return 0;
}
|
这道题的思路似乎也出奇的多，什么线段树，贪心等等。
首先，把严格递增的要求转换为非严格就会好求得多，所以设：
$a_i’=a_i+i,b_i’=b_i+i$
根据数学知识的经验，给定一个数列 $a_i$ ，构造一个数 $b$ 使得 $\displaystyle\sum|a_i-b|$ 最小的话，$b$ 必定是 $a$ 的中位数。
那么，这道题现在就有两个情况：
- 对于其一个子区间，其中 $a_{l\sim r}$ 单调递增，则对应 $b_{l\sim r}$ 一一对应；
- 对于其一个子区间，其中 $a_{l\sim r}$ 单调递减，则对应 $b_{l\sim r}$ 取中位数。
所以我们将原序列拆分成若干个单调区间，然后合并。但是，对于区间与区间之间的答案可能会互相影响。
然后有一个非常离谱但是是对的的结论：
合并两个区间并再次取出中位数。
这点几乎所有题解都没有提及，所幸 $\text{yxc}$ 给出了证明（虽然我还是不会证），也可以参考某一篇集训队论文，也给出了证明，这道题也是改编于此。
所以我们从前往后遍历 $a$ 数列，并在线维护中位数，更新答案。
对于维护中位数，可以建立一个只有 $\lceil\frac{size}{2}\rceil$ 的大根堆，此时的堆顶就是中位数。
而区间的合并也不一定会按照顺序，所以选择用栈维护。
AC Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
| #include<bits/stdc++.h>
template<class T>
inline void read(T &x)
{
x=0;
char ch=getchar(),t=0;
while(ch<'0'||ch>'9') t|=ch=='-',ch=getchar();
while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
if(t) x=-x;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1)
{
read(x),read(x1...);
}
template<class T>
inline void write(T x)
{
if(x<0) putchar('-'),x=-x;
if(x>9) write(x/10);
putchar(x%10+'0');
}
typedef long long ll;
const int MAXN=1e6+10;
int N,Val[MAXN],Dist[MAXN],Le[MAXN],Ri[MAXN];
struct Seg
{
int end,rt,siz;
}Stk[MAXN];
int Top,ans[MAXN];
int merge(int x,int y)
{
if(!x||!y) return x+y;
if(Val[x]<Val[y]) std::swap(x,y);
Ri[x]=merge(Ri[x],y);
if(Dist[Ri[x]]>Dist[Le[x]]) std::swap(Le[x],Ri[x]);
Dist[x]=Dist[Ri[x]]+1;
return x;
}
inline int pop(int x)
{
return merge(Le[x],Ri[x]);
}
int main()
{
read(N);
for(int i=1;i<=N;++i)
{
read(Val[i]);
Val[i]-=i;
}
for(int i=1;i<=N;++i)
{
auto cur=(Seg){i,i,1};Dist[i]=1;
while(Top&&Val[cur.rt]<Val[Stk[Top].rt])
{
cur.rt=merge(cur.rt,Stk[Top].rt);
if(cur.siz%2&&Stk[Top].siz%2)
cur.rt=pop(cur.rt);
cur.siz+=Stk[Top].siz;--Top;
}
Stk[++Top]=cur;
}
for(int i=1,j=1;i<=Top;++i)
{
while(j<=Stk[i].end)
ans[j++]=Val[Stk[i].rt];
}
ll res=0;
for(int i=1;i<=N;++i) res+=std::abs(Val[i]-ans[i]);
write(res),puts("");
for(int i=1;i<=N;++i) write(ans[i]+i),putchar(' ');
}
|