#include <stdio.h>
#include <algorithm>
using namespace std;
const int MAX_NODE_NUN = 2001000;
struct range_node {
int start, end; // 区间开始和结束位置
int root_id; // 左偏树上的根id
} ranges[MAX_NODE_NUN];
int range_idx = 0;
int ll[MAX_NODE_NUN]; // 左指针
int rr[MAX_NODE_NUN]; // 右指针
long long val[MAX_NODE_NUN]; // 实际问题里面节点数值不一定就是int类型,实际使用的时候根据具体情况做修改, 和模板参数T对应即可,需要T类型实现小于运算符
int dis[MAX_NODE_NUN]; // 节点的距离
int pp[MAX_NODE_NUN]; // 并查集数组
int __buffer[MAX_NODE_NUN]; // 缓存,并查集操作时候使用
int __pool_pos = 1; // 当前对象池的末尾
long long arr[MAX_NODE_NUN];
template<typename T>
class LeftistHeapForest {
// 合并根是id1和根是id2的两个堆, 返回新堆的堆顶节点的id号
int __merge(int id1, int id2) {
if (id1 == 0 || id2 == 0) {
return id1 + id2;
}
T val1 = val[id1], val2 = val[id2];
if (val2 > val1 || (val1 == val2 && id2 < id1)) {
id1 = id1 ^ id2, id2 = id1 ^ id2, id1 = id1 ^ id2;
}
int new_root_id = __merge(rr[id1], id2);
rr[id1] = new_root_id;
dis[id1] = dis[new_root_id] + 1;
int l_id = ll[id1], r_id = rr[id1];
if (dis[r_id] > dis[l_id]) {
ll[id1] = r_id, rr[id1] = l_id;
}
return id1;
}
public:
LeftistHeapForest() {
__pool_pos = 1;
}
// 用数值v创建新堆, 返回新创建的节点的id
int make_new_heap(T v) {
int id = __pool_pos++;
ll[id] = rr[id] = dis[id] = 0;
val[id] = v;
return id;
}
// 合并堆顶是root1和堆顶是root2的堆, 返回新的堆的堆顶元素的id
int merge(int root1, int root2) {
return __merge(root1, root2);
}
// 获取堆顶是id的节点所在堆的堆顶的元素(堆顶id, 堆顶val)
T get_top_val(int root) {
return val[root];
}
// 将堆顶是root号节点的堆的堆顶元素从堆上删除, 返回(新堆顶id, 弹出去的堆顶val)
pair<int, T> pop_top_val(int root) {
int new_root_id = __merge(ll[root], rr[root]);
return pair<int, T>{new_root_id, val[root]};
}
};
int main() {
//freopen("/Users/grh/Programming/CLionProjects/SimpleTest/input.txt", "r", stdin);
int n;
long long node_val, prev_val;
scanf("%d", &n);
LeftistHeapForest<long long> algo;
scanf("%lld", &node_val);
arr[0] = node_val;
ranges[range_idx++] = {0, 0, algo.make_new_heap(node_val)};
for (int i = 1; i < n; i++) {
scanf("%lld", &node_val);
arr[i] = node_val;
node_val -= i; // a'[i] = a[i] - i 做映射
ranges[range_idx++] = {i, i, algo.make_new_heap(node_val)};
while (range_idx >= 2) {
node_val = val[ranges[range_idx-1].root_id];
prev_val = val[ranges[range_idx-2].root_id];
if (node_val >= prev_val) {
break;
}
int new_root = algo.merge(ranges[range_idx-1].root_id, ranges[range_idx-2].root_id);
if (((ranges[range_idx-1].end - ranges[range_idx-1].start + 1) & 1) && ((ranges[range_idx-2].end - ranges[range_idx-2].start + 1) & 1)) {
// 两个左偏树大小都是奇数,维护中位数,合并后新的堆会多一个节点,
new_root = algo.pop_top_val(new_root).first;
}
ranges[range_idx-2] = {ranges[range_idx-2].start, ranges[range_idx-1].end, new_root};
range_idx -= 1;
}
}
long long ans = 0;
for (int i = 0; i < range_idx; i++) {
long long top_val = val[ranges[i].root_id];
for (int j = ranges[i].start; j <= ranges[i].end; j++) {
ans += abs((top_val + j) - arr[j]);
}
}
printf("%lld\n", ans);
for (int i = 0; i < range_idx; i++) {
long long top_val = val[ranges[i].root_id]; // 堆顶是区段的中位数,也就是这一整个区间的b'[i]的解
for (int j = ranges[i].start; j <= ranges[i].end; j++) {
printf("%lld ", top_val+j); // b[i] = b'[i] + i, 映射回原始a序列对应的解b序列
}
}
printf("\n");
}
删掉了一个点之后 cur.size 为什么不用-1