CEOI 2014 Day2 T2「Cake」题解

题目分析

这个问题模拟了一个有趣的吃蛋糕过程：Leopold 从编号为 $a$ 的蛋糕开始吃，然后每次选择与空位相邻的蛋糕中美味度最小的吃掉。Molly 会进行两种操作：提升某块蛋糕的美味度，或者询问在吃掉某块特定蛋糕前会吃掉多少块蛋糕。

关键思路

1. 吃蛋糕的规律

• 初始时吃掉位置 $a$ 的蛋糕，形成一个空位
• 每次选择与空位相邻的蛋糕中美味度最小的吃掉
• 空位始终保持为一个连续的区间

2. 数据结构设计

使用线段树维护以下信息：

• 每个位置蛋糕的"排名"（将美味度转换为排名，美味度越大排名越小）
• 线段树维护区间最小值，用于快速查询某个区间内的最小排名

3. 核心算法

对于每个查询：

• 如果查询位置 $b$ 在起始位置 $a$ 的右侧，则向左扩展找到边界
• 如果查询位置 $b$ 在起始位置 $a$ 的左侧，则向右扩展找到边界
• 使用线段树进行区间最小值的查询和边界查找

4. 美味度更新处理

• 维护前10大美味度的蛋糕编号
• 当更新某块蛋糕的美味度时，重新调整前10名的排名
• 只更新受影响的前10名蛋糕在线段树中的值

算法复杂度

• 构建线段树：$O(n)$
• 每次查询：$O(\log n)$
• 每次更新：$O(\log n)$（只更新前10名）
• 总复杂度：$O((n+q)\log n)$

代码实现要点

// 主要数据结构
struct T {
    int l, r, mid, mn;  // 线段树节点
} t[N << 2];

int n, ord[N], mstd[12], rt;  // ord:排名, mstd:前10名, rt:起始位置

// 关键函数：
// - build(): 构建线段树
// - qr(): 区间最小值查询  
// - mdf(): 单点更新
// - fdr()/fdl(): 向右/向左查找边界

样例解析

对于样例输入：

5 3
5 1 2 4 3

初始美味度转换为排名：

• 蛋糕1: 排名1 (美味度5最大)
• 蛋糕2: 排名5 (美味度1最小)
• 蛋糕3: 排名4
• 蛋糕4: 排名2
• 蛋糕5: 排名3

吃蛋糕顺序：3(起始)→2→4→5→1

当提升蛋糕2的美味度后，吃蛋糕顺序变为：3→4→5→2→1

总结

这道题通过巧妙的排名转换和线段树的应用，高效地解决了动态更新和查询问题。关键在于理解吃蛋糕的扩展规律，以及如何处理有限次数的美味度更新操作。