染后最长同色段
P5943. 染后最长同色段
场次:2026年10月21日-非AI方向 · 来源:CodeFun2000 P5943
题目描述
现有一条带子,长度记作 。开始的时候,带子上每个格子的颜色都不一样。
随后要按给定顺序做 次覆写。每一次指定一个闭区间 ,把其中每个格子都改成颜色 。
如果从第 格到第 格这一段里,格子的颜色完全一致,就把 叫做一条同色段。
每当一次覆写做完,都要汇报此刻整条带子上同色段的最大长度。
开始时,第 格的颜色等于它自己的编号 , 从 取到 。
每次覆写给出三个整数 、、,含义是把闭区间 里的颜色统一写成 。
输入格式
第一行给出两个整数 和 。 是带子的长度, 是覆写的次数。
后面还有 行。每一行三个整数 ,按先后对应一次覆写。
输出格式
共写出 行。第 行一个整数,表示第 次覆写完成之后,同色段的最大长度。
数据范围
示例
示例 1
输入:
7 4
3 5 2
6 7 2
1 1 2
4 4 8输出:
4
6
7
3说明:
开始时颜色依次是 。
第一次把 改成 ,得到 。第 格到第 格都是 ,长度 。
第二次把 改成 ,得到 。从第 格一直到末尾都是 ,长度 。
第三次把第 格改成 ,七格全是 ,长度 。
第四次把第 格改成 ,得到 。左右两段 都是长度 ,答案是 。
示例 2
输入:
4 2
2 3 6
1 4 6输出:
2
4说明:
开始时颜色是 。
第一次把 改成 ,得到 ,最长为 。
第二次把 改成 ,四格全是 ,最长为 。
解题思路
要回答的是什么:一个数字,但它由整条带子决定
状态是长度为 的颜色数组,初始 全部互不相同,所以答案一开始是 。每次操作是区间赋值,输出是全局最长同色段的长度——只输出长度,不需要指出是哪一段。
判定标准写清楚了,剩下的问题只有一个:怎么在每次赋值之后,用远小于 的代价更新这个长度。
数据范围把「逐格涂色」这条路堵死了
。最直白的写法是照着题面做:每次把 逐格写成 ,再从头扫一遍统计最长段。单次代价 ,总共 ,Python 和 C++ 都过不去。
于是每一次操作的代价必须压到 左右。要做到这一点,关键是承认一件事:一次赋值只改变与 有关的那一小部分信息,带子上离它很远的地方一点没动。下面两条路都是围绕这句话做文章。
- 方案一:把带子切成固定的树结点,每个结点只记录与自己区间有关的几个数,赋值时只更新被覆盖的 个结点。
- 方案二:把带子看成「一串同色段」,赋值时只动与 相交的那几段,并把答案放进一个堆里。
方案一:线段树,每个结点记「前缀多长、后缀多长、最长多长」
把 铺到一棵线段树上,每个结点维护自己那段区间的六个量:
| 量 | 含义 |
|---|---|
lc / rc | 区间最左格、最右格的颜色 |
pre | 从区间左端开始、颜色全相同的那一截有多长 |
suf | 以区间右端结束、颜色全相同的那一截有多长 |
best | 区间内部最长同色段的长度 |
cnt | 区间里的格子数 |
一个结点只有这六个量,但它足以算出上一层:把左右儿子 、 拼起来时,唯一可能新增的同色段就是「 的后缀 + 的前缀」,前提是这两截颜色相同。于是
best = max(L.best, R.best, L.suf + R.pre 当 L.rc == R.lc)前缀和后缀要单独照顾。 的前缀能不能延伸到 里去,条件不只是「两边颜色一样」,还得要求 整段都是同一个颜色(即 L.pre == L.cnt)——否则 的前缀到区间右端就断了,接不上 :
def pull(p):
a, b = p << 1, p << 1 | 1
cnt[p] = cnt[a] + cnt[b]
lc[p], rc[p] = lc[a], rc[b]
pre[p] = pre[a] + (pre[b] if pre[a] == cnt[a] and lc[a] == lc[b] else 0)
suf[p] = suf[b] + (suf[a] if suf[b] == cnt[b] and rc[b] == rc[a] else 0)
best[p] = max(best[a], best[b],
suf[a] + pre[b] if rc[a] == lc[b] else 0)下面「完整代码实现」里的 pull 多一个 cnt[b] == 0 的分支: 不一定是 的幂,最右边会补几个不存在的填充格,那半边整段继承左儿子即可。
赋值是标准的懒标记:整段被 盖住时,这六个量一次性写死成「全是 」,并把标记挂在结点上;下次要往儿子走之前,把标记推下去。
def apply(p, w): # 整段变成颜色 w
lc[p] = rc[p] = w
pre[p] = suf[p] = best[p] = cnt[p] # 前缀=后缀=最长=整段长度
tag[p] = w
def assign(p, l, r, ql, qr, w):
if ql <= l and r <= qr: # 完全被覆盖,打标记就走
apply(p, w)
return
push(p) # 有标记先下推
mid = (l + r) >> 1
if ql <= mid:
assign(p << 1, l, mid, ql, qr, w)
if qr > mid:
assign(p << 1 | 1, mid + 1, r, ql, qr, w)
pull(p) # 回来重新合并两个儿子答案就是根结点的 best[1]——根覆盖整条带子,它的 best 就是全局最长。
方案二:颜色段均摊,把带子看成一串「段」
换个视角:相邻且同色的格子合成一段,整条带子就是一串极大同色段。初始时每格一段,共 段。
一次赋值 做过之后,只有三种段会变:被 完整覆盖的段(全部消失)、 左边被截断的那一段、 右边被截断的那一段。而一次操作最多新增两个段的起点( 与 ),被删掉的起点则是永久消失的。把「一次操作要遍历的段数」记成「这一轮删掉的段数 + 1」,所有轮加起来不超过「历史新增的段数」。
这就是颜色段均摊(Chtholly 树)的均摊分析:总代价 级别的段访问,每次操作摊到常数个段。剩下的问题只有两个实现细节。
细节一:怎么知道第 格落在哪一段上。 需要「在段起点集合里找 的最后一个位置」,也就是有序集合的前驱查询。C++ 里这是 std::set 的 lower_bound,Python 没有现成的有序集合,用 Fenwick 树顶上:把「某个位置是不是段起点」记成 ,前驱查询变成「第 个 在哪」,其中 是 的前缀和。
def cut(x):
"""保证 x 成为某段的起点(1 <= x <= A)。"""
s = fen_kth(fen_sum(x)) # 覆盖 x 的那一段从 s 开始
if s != x: # 从 x 处锯成两段
link(x, col[s], s, nxt[s])
push_len(s) # 左截变短、右截独立,各自补一条有效记录
push_len(x)
return x细节二:怎么在 内拿到全局最长。 段的长短在变,用一个惰性堆存 (-长度, 起点):查询时不断弹出堆顶,只要「这个起点还活着,并且它当前的长度确实等于记录的长度」就停。失效的记录会在弹出的过程中被清掉,每条记录最多被弹一次,所以堆的总代价也是 。
把这两块拼起来,一次赋值的核心就是「切两端、删中间、染色、与左右同色邻居合并」:
cut(l) # P 处锯开
if nxt[fen_kth(fen_sum(r))] - 1 > r: # r 不是它所在段的末尾
cut(r + 1) # Q+1 处锯开,保住右残段
cur = nxt[l] # 删掉被完整覆盖的段起点
while cur <= r:
nxt[l] = nxt[cur]
unlink(cur)
cur = nxt[l]
col[l] = w # [P, Q] 统一成 W
s = l
if prv[s] >= 1 and col[prv[s]] == w: # 与左邻同色,并进去
unlink(s)
s = prv[s]
if col[nxt[s]] == w: # 与右邻同色,吞掉它
unlink(nxt[s])
push_len(s) # 新长度入堆两条路怎么选
两者渐进复杂度一样,都是 ,差别在常数:
- 线段树的结点是固定的,赋值只看 个结点,代码结构规整、不需要有序集合;
- 颜色段均摊只碰真正被改动的段,一段很长的区间被整段覆盖时几乎不花时间。实测 的随机数据上,第二版比第一版快一倍以上。
两版都写在下面的「完整代码实现」里:第一版是思路主线,第二版是提交时更稳的写法。
完整代码实现
版本一:线段树 + 懒标记
import sys
def solve():
data = sys.stdin.buffer.read().split()
if not data:
return
n, q = int(data[0]), int(data[1])
# 把 1..n 铺到完全二叉树的叶子上,size 是补齐后的宽度
size = 1
while size < n:
size <<= 1
lc = [0] * (size << 1) # 区间最左格的颜色
rc = [0] * (size << 1) # 区间最右格的颜色
pre = [0] * (size << 1) # 前缀同色长度
suf = [0] * (size << 1) # 后缀同色长度
best = [0] * (size << 1) # 区间内最长同色段
cnt = [0] * (size << 1) # 区间里的真实格子数
tag = [0] * (size << 1) # 0 表示没有待下推的赋值
for i in range(1, n + 1):
p = size + i - 1
lc[p] = rc[p] = i # 初始第 i 格颜色为 i
pre[p] = suf[p] = best[p] = cnt[p] = 1
def pull(p):
a, b = p << 1, p << 1 | 1
if cnt[b] == 0: # 右半边是填充格,原样继承左儿子
cnt[p], lc[p], rc[p] = cnt[a], lc[a], rc[a]
pre[p], suf[p], best[p] = pre[a], suf[a], best[a]
return
cnt[p] = cnt[a] + cnt[b]
lc[p], rc[p] = lc[a], rc[b]
pre[p] = pre[a] + (pre[b] if pre[a] == cnt[a] and lc[a] == lc[b] else 0)
suf[p] = suf[b] + (suf[a] if suf[b] == cnt[b] and rc[b] == rc[a] else 0)
best[p] = max(best[a], best[b],
suf[a] + pre[b] if rc[a] == lc[b] else 0)
for p in range(size - 1, 0, -1):
pull(p)
def apply(p, w):
lc[p] = rc[p] = w
pre[p] = suf[p] = best[p] = cnt[p]
tag[p] = w
def push(p):
w = tag[p]
if w:
apply(p << 1, w)
apply(p << 1 | 1, w)
tag[p] = 0
def assign(p, l, r, ql, qr, w):
if ql <= l and r <= qr:
apply(p, w)
return
push(p)
mid = (l + r) >> 1
if ql <= mid:
assign(p << 1, l, mid, ql, qr, w)
if qr > mid:
assign(p << 1 | 1, mid + 1, r, ql, qr, w)
pull(p)
out = []
pos = 2
for _ in range(q):
p0 = int(data[pos])
q0 = int(data[pos + 1])
w = int(data[pos + 2])
pos += 3
assign(1, 1, size, p0, q0, w)
out.append(str(best[1])) # 根结点就是整条带子
sys.stdout.write("\n".join(out) + "\n")
if __name__ == "__main__":
solve()版本二:颜色段均摊 + Fenwick 找起点 + 惰性堆
import heapq
import sys
def solve():
data = sys.stdin.buffer.read().split()
if not data:
return
n, q = int(data[0]), int(data[1])
# ---- Fenwick:维护「哪些位置是段起点」,支持前驱查询 ----
size = 1
while size < n + 1:
size <<= 1
fen = [0] * (size + 1)
def fen_add(i, delta):
while i <= size:
fen[i] += delta
i += i & -i
def fen_sum(i):
s = 0
while i > 0:
s += fen[i]
i -= i & -i
return s
def fen_kth(k):
"""最小的位置 p,使 1..p 里的段起点数达到 k。"""
p, step = 0, size
while step:
nxt_p = p + step
if nxt_p <= size and fen[nxt_p] < k:
p = nxt_p
k -= fen[nxt_p]
step >>= 1
return p + 1
# ---- 颜色段:col[s] 是起点 s 那段的颜色,nxt/prv 把段串起来 ----
col = [0] * (n + 2)
nxt = [0] * (n + 2)
prv = [0] * (n + 2)
alive = bytearray(n + 2)
for i in range(1, n + 1):
col[i] = i # 初始每格自成一段,颜色就是编号
nxt[i] = i + 1
prv[i] = i - 1
alive[i] = 1
fen_add(i, 1)
nxt[n + 1] = n + 1
def unlink(s):
alive[s] = 0
fen_add(s, -1)
a, b = prv[s], nxt[s]
nxt[a] = b
prv[b] = a
def link(s, c, a, b):
"""在 a 与 b 之间插入起点 s。"""
col[s] = c
alive[s] = 1
prv[s], nxt[s] = a, b
nxt[a] = s
prv[b] = s
fen_add(s, 1)
heap = [(-1, i) for i in range(1, n + 1)] # (-长度, 起点)
heapq.heapify(heap)
def push_len(s):
heapq.heappush(heap, (s - nxt[s], s))
def cut(x):
"""保证 x 是某段的起点(1 <= x <= n)。"""
s = fen_kth(fen_sum(x))
if s != x:
link(x, col[s], s, nxt[s])
push_len(s) # 左截变短、右截独立,各自补记录
push_len(x)
return x
out = []
pos = 2
for _ in range(q):
l = int(data[pos])
r = int(data[pos + 1])
w = int(data[pos + 2])
pos += 3
cut(l)
if nxt[fen_kth(fen_sum(r))] - 1 > r: # r 不在它那段的末尾
cut(r + 1) # 保住 [r+1, ...] 这段
cur = nxt[l] # 删掉被完整覆盖的段起点
while cur <= r:
nxt[l] = nxt[cur]
unlink(cur)
cur = nxt[l]
col[l] = w # [l, r] 统一成 w
s = l
if prv[s] >= 1 and col[prv[s]] == w: # 与左邻同色,并进去
unlink(s)
s = prv[s]
b = nxt[s]
if b <= n and col[b] == w: # 与右邻同色,吞掉它
unlink(b)
push_len(s)
while True: # 惰性清理失效的堆顶
neg, st = heap[0]
if alive[st] and nxt[st] - st == -neg:
break
heapq.heappop(heap)
out.append(str(-heap[0][0]))
sys.stdout.write("\n".join(out) + "\n")
if __name__ == "__main__":
solve()示例推演
示例 1:七格、四次覆写
初始 ,颜色 ,七个段各自长度为 ,答案为 。下面用「段列表」的形式记录状态,每段写成 [起点, 终点]: 颜色。
第 1 次:
cut(3): 本来就是段起点,不用锯。- 落在段 上,这段的右端正好是 ,不需要
cut(6)。 - 删掉起点 、,段 就覆盖了 ,颜色改成 。
- 左邻是段 ,颜色也是 ,合并;右邻是段 (颜色 ),不合并。
状态变成 [1,1]:1、[2,5]:2、[6,6]:6、[7,7]:7,最长 。
第 2 次:
cut(6)不用锯; 落在段 上,右端就是 。- 删掉起点 ,段 覆盖 ,颜色改 ;左邻段 颜色也是 ,合并成
[2,7]:2。
状态:[1,1]:1、[2,7]:2,最长 。
第 3 次:
段 改色为 ,右邻段 同色,合并成 [1,7]:2,最长 。
第 4 次:
cut(4): 落在[1,7]中间,从 处锯成[1,3]:2与[4,7]:2两段。- 落在
[4,7]上,右端 ,再cut(5),锯出[4,4]:2与[5,7]:2。 - 要删的段起点一个也没有:
(4,4]$里没有起点,被覆盖的 已经由cut(5)单独隔出来了,直接改它的颜色。 - 左邻
[1,3]是 、右邻[5,7]是 ,都不是 ,谁也不合并。
状态:[1,3]:2、[4,4]:8、[5,7]:2,最长 ,与官方输出一致。
线段树版本在同一时刻维护的是每个结点的 (lc, rc, pre, suf, best)。第 1 次覆写把带子涂成 (第 格是补齐用的填充格),根结点的两个儿子分别是:
| 结点 | 覆盖格子 | lc | rc | pre | suf | best | cnt |
|---|---|---|---|---|---|---|---|
| ( 是填充) |
合并时 rc[1,4]=2 与 lc[5,8]=2 相等,跨中线的候选是 ,比两个儿子各自的 best 都大,所以根结点的 best 取 ——一次合并就把「第 格到第 格连成一段」算了出来。
复杂度分析
| 解法 | 时间复杂度 | 空间复杂度 | 说明 |
|---|---|---|---|
| 逐格涂色 + 每次重扫全带 | 量级,必定超时 | ||
| 线段树 + 懒标记 | 每次赋值只走 个结点,代码规整 | ||
| 颜色段均摊(最优) | 只碰真正被改动的段;有序集合与惰性堆各带一个 ,实测常数更小 |
后两行的渐进复杂度相同,差别在常数:线段树的每次操作固定访问 个结点,与数据无关;均摊版的每次操作访问「本轮删掉的段数 个段」,单个操作最坏可以是 ,但所有操作加起来只有 个段,摊到每次就是常数个。 时两者的对数因子都是 左右。
易错点总结
1. 合并前缀时漏掉「左儿子整段同色」这个条件
pre[p] = pre[a] + (pre[b] if lc[a] == lc[b] else 0) 这种写法只看颜色不看长度。左儿子不整段同色时,它的前缀到区间右端就断了,接不上右儿子,可颜色比较会通过。取 ,依次做 、、,带子成为 :结点 的格子是 ,真实前缀只有 (第 格的 后面紧跟 ),错误写法按 lc[5,6]=2 == lc[7,8]=2 拼成 ;再与左儿子 的后缀 拼出 ,最终输出 ,而正确答案是前三个 组成的长度 。判据必须写成 pre[a] == cnt[a] and lc[a] == lc[b]。两组官方样例每次都只在「整段同色」的情形下拼接,所以测不出来。
2. 打标记时把长度写成了父结点的长度
apply 里若写成 pre[p] = suf[p] = best[p] = cnt[父结点](或者干脆写成一个常量),被下推的子结点就会以错误的长度参与合并。示例 1 的第 3 次覆写把整条带子涂成 ,标记挂在根结点上(cnt=7);第 4 次覆写需要把标记往下推,只覆盖 格的子结点也会拿到 这个长度——带子里根本不存在长度 的同色段,输出变成 而不是 。写成 cnt[p] 才对:apply 拿到的 p 就是被覆盖的那个结点本身,长度只能用它自己的 cnt。
3. 切右残段时用「 所在段的右端」作判断
判断要不要 cut(r + 1),必须看包含 的那一段的右端:if nxt[fen_kth(fen_sum(r))] - 1 > r: cut(r + 1)。若图省事写成 if nxt[l] - 1 > r,看的就成了「 所在段的下一个起点」,而这两个段根本不是一回事。
拿 走一套数据:先把 涂成 ,此时段是 [1,1]:1、[2,7]:2;再做 。正确的切法是 落在 [2,7] 上、右端 ,于是 cut(6) 锯出 [6,7]:2,最终状态 [1,5]:3、[6,7]:2,答案是 。用错判据时 nxt[1]-1=1 不满足 ,cut(6) 被跳过,整段 [2,7] 跟着涂成 ,输出变成 ——比正确答案大,而且两格之外的 [6,7] 明明没被 碰到。