CF1329C Drazil Likes Heap 与左偏树

发表于 更新于 分类于 ， 阅读次数：

CF1329C Drazil Likes Heap 与左偏树

左偏树是一种可并堆，在保持堆的性质的基础上能实现快速合并两个堆。

本来是写了个左偏树板子，想找题测一下，发现都不太会。

CF1329C Drazil Likes Heap

简要失真题意

一个有$2^h-1$个元素的二叉最大堆，要求大小缩小到$2^g-1$，所以你要删除$2^h-2^g$个元素，同时使剩下的元素之和最小。输出这个最小值，以及你每次删除的元素的下标。

注意：当一个元素缺失时，会由他较大的儿子来填补。所以元素的下标是一直在变的，而且这个堆也因此没有完全二叉树性质。

思路

很明显删除元素尽量大是最优的，那么我们得确定最终删除哪些元素。因为一开始从叶子开始向根节点删的话不会影响祖先的下标，之后在输出时直接从后向前输出即可。

在这里插入图片描述

因为这个特殊的堆并不特意维护完全二叉树的性质，如上图，此时是不能$pop$掉根节点的，只能选择删除掉$2$。

在这里插入图片描述

对于最终保留的高度为$g$的一个堆，很明显对于$g$堆的每一个叶子，都是原来高度为$h$的堆在以这个节点的子树上的最小值。所以此时我们可以确定$g$堆的所有叶子节点，那我们对$g-1$层同样进行贪心，取左右子树上剩余的最小值，同时要保证大顶堆的性质，将所有小于左右儿子的值删除（因为越往上值越大这些值后面也用不到了）。

因为叶子节点数$2^{h-1}>2^{h}-1-2^{h-1}$，所以深度$\le g$的节点的权值必定是用不到的。

所以我们可以在原树上进行$dfs$，对于每一个叶子节点都视为一个小根堆，并且在回溯的时候为左右儿子进行堆合并，当回溯时深度$\le g$时，我们贪心地选择最小的值分配给当前节点，并且$pop$掉比左右节点更小的值来维护堆的性质。

代码

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
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
//#pragma comment(linker, "/STACK:102400000,102400000")
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
//#define int ll
typedef pair<int,int>pii;
#define ff first
#define ss second
#define debug(x) std:: cerr << #x << " = " << x << std::endl;
const int maxn=2e6+10,inf=0x3f3f3f3f,mod=1000000007;
const ll INF=0x3f3f3f3f3f3f3f3f;
const double eps=1e-9;
//#define DEBUG//#define lowbit(x) ((x) & -(x))//<<setiosflags(ios::fixed)<<setprecision(9)
void read(){}
template<typename T,typename... T2>inline void read(T &x,T2 &... oth) {
    x=0; int ch=getchar(),f=0;
    while(ch<'0'||ch>'9'){if (ch=='-') f=1;ch=getchar();}
    while (ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
    if(f)x=-x;
    read(oth...);
}
typedef struct LeftistTree
{
    /*
     * 在保持二叉堆基础性质上可以快速合并的堆
     * 外节点:左右儿子不完整的节点
     * 距离:最近的外节点到该点的距离
     * 性质:
     * 1.节点权值不大于左右儿子权值(堆性质)
     * 2.节点左儿子距离≥右儿子距离(左偏性质)
     * 3.节点距离=右儿子距离+1
     * 支持如下操作:
     * 合并两个堆 merge,log(p+q)
     * 插入 push ,log(n)
     * 删除最值 pop ,log(n)
     * 删除指定节点 ,log(n)
     * 修改指定节点的值:先删除再加入
     * 取最大/最小值 ,O(1)
     * lt.sum[lt.findfa(x)],可以得到x所在堆的元素和
     * lt.cnt[lt.findfa(x)],可以得到x所在堆的大小
     * build可快速建树,暴建树力建树nlogn
    */
    using type=int;
    int siz=0;
    struct node
    {
        type val;
        int lc,rc,dis,fa;
        int id;
        node(){}
        node(type val):
            val(val){lc=rc=dis=fa=0;}
    } ltt[maxn];
    type sum[maxn];//堆中元素之和
    int cnt[maxn];//每一个堆的大小
    #define ls(x) ltt[x].lc
    #define rs(x) ltt[x].rc
    inline void update(int x)
    {
        sum[x]=sum[ls(x)]+sum[rs(x)]+ltt[x].val;//更新堆中元素和
//        printf("node[%d],l=%d,r=%d\n",x,ls(x),rs(x));
        cnt[x]=cnt[ls(x)]+cnt[rs(x)]+1;
        if(ltt[ls(x)].val==-1)
        {
            sum[x]-=sum[ls(x)];
            cnt[x]-=cnt[ls(x)];
        }
//        printf("cnt[%d]=%d+%d+1=%d\n",x,cnt[ls(x)],cnt[rs(x)],cnt[x]);
//        printf("sum[%d]=%d=%d+%d+%d\n\n",x,sum[x],sum[ls(x)],sum[rs(x)],ltt[x].val);
    }
    int merge(int x,int y)
    {//x,y为堆顶点元素的编号
        if(x==y)//相同堆不合并
            return x;
//        printf("%d,%d\n",x,y);
        if(!x||!y)//如果有一个为空
            return x+y;//就返回另一个
        if(ltt[x].val>ltt[y].val||(ltt[x].val==ltt[y].val&&x>y))//大根堆
            std::swap(x,y);
//        printf("%d:ls=%d,rs=%d\n",x,ls(x),rs(x));
        rs(x)=merge(rs(x),y);//往右儿子合并
        ltt[rs(x)].fa=x;
        update(x);//回溯更新新树信息
        if(ltt[ls(x)].dis<ltt[rs(x)].dis)
            std::swap(ls(x),rs(x));
        ltt[x].dis=ltt[rs(x)].dis+1;
        return x;//返回新的根编号
    }
    void Merge(int x,int y)
    {//合并x所在堆与y所在堆
//        if(ltt[x].val==-1||ltt[y].val==-1)//根据需要注释
//            return;
        int fx=findfa(x),fy=findfa(y);
        if(fx==fy)
            return;
        ltt[fx].fa=ltt[fy].fa=merge(fx,fy);//维护联通性
    }
    int push(int val,int x)
    {//新加入的点权val,准备加入的堆根编号x
        ltt[++siz].val=val;
        ltt[siz].fa=siz;
        ls(siz)=rs(siz)=ltt[siz].dis=0;
        cnt[siz]=1;
        sum[siz]=ltt[siz].val;
        return merge(siz,x);//当作一棵新树合并到原树上
    }
    int findfa(int x)
    {//获得第x号所在堆的顶点编号
        if(ltt[x].fa!=x)//路径压缩
            return ltt[x].fa=findfa(ltt[x].fa);
        return x;
    }
    type top(int x)
    {//返回x所在堆的顶点的值
        return ltt[findfa(x)].val;
    }
    int pop(int x)
    {//x为当前堆根编号,并且删除x节点
        if(ltt[x].val==-1)//已经被删除
            return -1;
        ltt[x].val=-1;//将节点x标记为删除
        ltt[ls(x)].fa=ls(x);
        ltt[rs(x)].fa=rs(x);//将左右子树合并,并用并查集维护联通
        return ltt[x].fa=merge(ls(x),rs(x));//返回新的根编号
    }
    void del(int x)//待修改,错的
    {//O(logn)删除任意节点,x为节点编号
        int fx=ltt[x].fa,p=merge(ls(x),rs(x));//将左右子树合并
        int &lls=ls(fx),&rrs=rs(x);
        ltt[p].fa=fx;
        if(lls==x)//新子树连接到x原来的父节点
            lls=p;
        else
            rrs=p;
        while(p!=fx)
        {//检查左偏树性质
            if(ltt[lls].dis<ltt[rrs].dis)
                swap(lls,rrs);
            if(ltt[lls].dis==ltt[rrs].dis+1)
                return;
            ltt[fx].dis=ltt[rrs].dis+1;
            p=fx;//向上
            fx=ltt[fx].fa;
            lls=ls(fx);
            rrs=rs(fx);
        }
    }
    int build(int a[],int n)//未验证
    {//将[1,n]的元素全部合并
        ltt[0].dis=-1;
        queue<int>q;
        for(int i=1;i<=n;i++)
        {//处理节点信息
            ltt[i].val=a[i];
            ltt[i].fa=i;
            ls(i)=rs(i)=0;
            q.push(i);
        }
        siz=n;
        while(!q.empty())
        {//队列优化建树
            if(q.size()==1)
                break;
            else{
                int x=q.front();q.pop();
                int y=q.front();q.pop();
                q.push(merge(x,y));
            }
        }
        return q.front();//返回堆根编号
    }
    void init(int n)
    {
        siz=0;
        ltt[0].dis=-1;
        for(int i=1;i<=n;i++)
        {
            ltt[i].dis=ls(i)=rs(i)=ltt[i].dis=0;
            ltt[i].val=0;
            ltt[i].fa=i;
            cnt[i]=0;
            sum[i]=0;
        }
    }
    #undef ls
    #undef rs
} LT;
LT lt;
int a[maxn],ans[maxn],h,g;
bool vis[maxn];
void dfs2(int x,int dep)
{
    if(dep+1<=h)
    {
        dfs2(x<<1,dep+1);
        dfs2(x<<1|1,dep+1);
        lt.Merge(lt.findfa(x),lt.findfa(x<<1));
        lt.Merge(lt.findfa(x),lt.findfa(x<<1|1));
    }
}
void dfs(int x,int dep)
{
    if(dep==g)
    {
        dfs2(x,dep);
        ans[x]=a[lt.findfa(x)];//最终权值
        vis[lt.findfa(x)]=1;//标记保留
        lt.pop(lt.findfa(x));
        return;
    }
    dfs(x<<1,dep+1);
    dfs(x<<1|1,dep+1);
    lt.Merge(lt.findfa(x),lt.findfa(x<<1));
    lt.Merge(lt.findfa(x),lt.findfa(x<<1|1));
    while(lt.top(x)<max(ans[x<<1],ans[x<<1|1]))
        lt.pop(lt.findfa(x));
    ans[x]=lt.top(x);
    vis[lt.findfa(x)]=1;
    lt.pop(lt.findfa(x));
}
signed main(signed argc, char const *argv[])
{
    std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    #ifdef DEBUG
        freopen("input.in", "r", stdin);
    //	freopen("output.out", "w", stdout);
    #endif
    int t;
    cin>>t;
    while(t--)
    {
        cin>>h>>g;
        int n=(1ll<<h)-1,m=(1ll<<g)-1;
        lt.init(n);
        for(int i=1;i<=n;i++)
        {
            vis[i]=0;
            cin>>a[i];
            lt.push(a[i],i);
//            lt.ltt[i].id=i;
        }
        dfs(1,1);
        ll sum=0;
        for(int i=1;i<=(1<<g)-1;i++)
            sum+=ans[i];
        cout<<sum<<endl;
        for(int i=(1<<h)-1;i>=1;i--)
            if(!vis[i])
                cout<<i<<' ';
        cout<<endl;
    }
    return 0;
}
/*
 * 2021-04-21-08.27.22
 * 一个高度为h的大根堆,要让他的高度减小到g
 * 每一轮调用,都会删除当前堆的根
 * 空出来的位置由左右儿子最大的填补
 * 很明显贪心删最大的,只要能确定位置即可
 * 这TM能拿左偏树做么
 * https://leohh.moe/?p=117
*/