编辑代码

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

// 宏定义，用于方便编程
#define int long long



// 定义常量 N=5e5+50
const int N = 5e5 + 50;

vector<int> segment_tree, arr, left_idx, right_idx;

// 建树，cur为当前节点，l为左端点，r为右端点
void build_tree(int cur, int l, int r)
{
	// 如果左右端点相同，说明只有一个元素，将这个元素赋给f数组，并返回
	if (l == r)
	{
		segment_tree[cur] = arr[l];
		return;
	}
	// 否则，递归建树,并更新f数组
	int mid = (l + r) / 2;
	build_tree(cur + cur, l, mid);
	build_tree(cur + cur + 1, mid + 1, r);
	segment_tree[cur] = min(segment_tree[cur + cur], segment_tree[cur + cur + 1]);
}

// 查询最小值，cur为当前节点，l为查询区间左端点，r为查询区间右端点
pair<long long, long long> query(int cur, int l, int r)
{
	// 如果左右端点相同，说明只有一个元素，返回该元素所在位置，以及对应的f值
	if (l == r)
	{
		return { segment_tree[cur],l };
	}
	int mid = (l + r) / 2;
	pair<long long, long long> ans = { 0,0 };
	// 如果左子节点的值小于等于右子节点的值，则递归查询左子树
	if (segment_tree[cur + cur] <= segment_tree[cur + cur + 1])ans = query(cur + cur, l, mid);
	// 否则，递归查询右子树
	else ans = query(cur + cur + 1, mid + 1, r);
	return ans;
}

// 修改指定位置的元素，cur为当前节点，l为区间左端点，r为区间右端点，x为所要修改元素的下标，val为修改量
void revise(int cur, int l, int r, int x, int val)
{
	// 如果左右端点相同，说明已经找到目标元素，将其加上val，返回
	if (l == r)
	{
		segment_tree[cur] += val;
		return;
	}
	int mid = (l + r) / 2;
	// 如果目标元素在左子树中，则递归处理左子树
	if (x <= mid) {
		revise(cur + cur, l, mid, x, val);
	}else// 否则递归处理右子树
	{
		revise(cur + cur + 1, mid + 1, r, x, val);
	}
	// 更新左右子树的 segment_tree 值
	segment_tree[cur] = min(segment_tree[cur + cur], segment_tree[cur + cur + 1]);
}

// 查找 arr 数组中某个元素的祖先
int find_left_node(int x)
{
	// 通过递归查找父节点来确定根节点
	if (left_idx[x] != x)left_idx[x] = find_left_node(left_idx[x]);
	return left_idx[x];
}

// 查找 b 数组中某个元素的祖先
int find_right_node(int x)
{
	// 通过递归查找父节点来确定根节点
	if (right_idx[x] != x)right_idx[x] = find_right_node(right_idx[x]);
	return right_idx[x];
}

// 主函数，用于解题
void solve()
{
	int n, k;
	// 输入 n 和 k
	cin >> n >> k;
    segment_tree = vector<int> (4 * ( n + 10), 0);
    arr = vector<int> (n + 10, 0);
    left_idx = vector<int> (n + 10, 0);
    right_idx  = vector<int> (n + 10, 0);
	for (int i = 1; i <= n; i++)
	{
		cin >> arr[i];
	}
	// 建树
	build_tree(1, 1, n);
	// 初始化 left_idx 和 right_idx 数组
	for (int i = 1; i <= n; i++)
	{
		left_idx[i] = i;
		right_idx[i] = i;
	}

	while (k--)
	{
		//查找的结果以pair的形式返回，first是最小值，second是它在数组的下标
		pair<long long, long long> ans = query(1, 1, n);

		//找当前元素挨着的左边元素 l，和右边元素 r
		int l = find_left_node(ans.second - 1), r = find_right_node(ans.second + 1);
		//改变指向，将 ans.second 的祖先设为 l，将 ans.second 的祖先设为 r
		left_idx[ans.second] = l;
		right_idx[ans.second] = r;

		//修改原最小值，让它不要影响我们之后的操作
		revise(1, 1, n, ans.second, 1e18);
		//在线段树中修改原最小值两边的元素
		revise(1, 1, n, l, ans.first);
		revise(1, 1, n, r, ans.first);
		//在数组中也要修改
		arr[l] += ans.first;
		arr[r] += ans.first;

	}
	//输出
	for (int i = 1; i <= n; i++)
	{
		//如果fa的指向没变，说明这个元素没被删
		if (left_idx[i] == i)cout << arr[i] << " ";
	}
}
// 主函数
signed main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	int t = 1;
	//cin>>t;
	while (t--)
	{
		solve();
	}

	return 0;
}