Cdq 解決一類最值和雙端點有關的數點問題

真っ白な想いに
夢のかけらを
描いて
動き出す未來
子供の頃に知った
心が躍るような
わくわくする感情を
今も覚えてるよ
迷いや不安はない
期待に溢れてる
何にだってなれ
そうな気がした
はじまりの靜けさと
これからにざわめく鼓動
未知數な物語
そのワンシーンを大切に
めに焼き付けたいから
真っ白な気持ちを
鮮やかに染めていこう
どんな理想も自分
次第で近づくから
不透明な明日に
悩んで躓いたときも
君の聲で
乗り越えられるから
葉えたい
胸の中の
沢山の希望のかけらを
描いて
走り出す世界
手のひらに伝わる
きらめくイメージを
少しずつ紡いでいく時間も
大切で大好きな
かけがえのないものになる
未完成な物語
そのワンシーンを忘れない
輝き感じたいから
真っ白な想いを
何色に染めていこう
どんな昨日も自分に
エールをくれるから
流した涙も
元気が足りないときも
君といれば
笑顏になれるから
屆けたい
胸の中の
溢れ出した夢のかけれを
描いて
動き出す未來
一人一人が持つ
想いを線で繋いだら
星座みたいに広がる景色
真っ白な光を
どこまでも追い続けて
もっと知りたい
好奇心を感動の先へ
真っ白な気持ちを
鮮やかに染めていこう
どんな理想も
自分次第で近づくから
不透明な明日に
悩んで躓いたときも
君の聲で
乗り越えられるから
葉えたい
胸の中の
沢山の希望のかけらを
描いて
走り出す世界

今年最后一篇鮮花。

今年的第一篇鮮花。

被同一個 trick 背刺兩次也是沒救了。

Yet Another Partiton Problem

首先 \(n^2k\) 的轉移是顯:

發現 \(\max\) 同時和 \(i, j\) 有關，不好優化。

很牛的 trick 是套一個 cdq，考慮處理 \(j < mid \le i\) 的貢獻，容易發現其 \(\max_{k\in(j, i]}\{a_k\}\) 可以拆成 \(\max\{\max_{k\in(j, mid]}\{a_k\}, \max_{k\in(mid, i]}\{a_k\}\}\)，而這兩段可以分開做，做兩個斜率優化即可。

于是我們用一個 \(\log\) 做掉了一個同時和 \(i, j\) 有關的 \(\max\)。

Baby's First Suffix Array Problem

首先建 SA

這里我們默認都是在排好序的數組上，如果是原數組第 \(i\) 個寫成 \(sa_i\)

發現因為刪除了一個后綴，其相對大小會改變，考慮統計變化量，即原來在 \(k\) 前被 \(k\) 超過的部分和原來在 \(k\) 后超過 \(k\) 的部分。

簡單分討一下 \(sa_i, sa_k, i, k\) 的大小關系，容易發現只有兩種有貢獻。

分別是：

和

前一種是好做的，發現 \(r - sa_k\) 是定值，\(lcp\) 在 \(i\) 上是連續的一段，所以 $$lcp(sa_i, sa_k) + sa_k > r$$ 相當于是一個限制 \(i > p\)，可以二分求出 \(p\)，然后直接做二維偏序即可。

后一種沒有這么優良的性質，考慮到 \(lcp(sa_i, sa_k) \Leftrightarrow min_{x \in (i, k]}\{ht_x\}\)，于是依然套用 \(cdq\)，將其拆成 \(\min\{\min_{x\in(i, mid]}\{ht_x\}, \min_{x\in(mid, k]}\{ht_x\}\}\)。

但是你發現你現在對 \(\min\) 兩邊大小分討會變成三維偏序，十分不好做，于是我們寫出這個式子 \(\min\{\min_{x\in(i, mid]}\{ht_x\}, \min_{x\in(mid, k]}\{ht_x\}\} + sa_i > r\)，因為其是 \(>\)，我們有個經典拆法，拆成 \(\min_{x\in(i, mid]}\{ht_x\} + sa_i > r \land \min_{x\in(mid, k]}\{ht_x\} + sa_i > r\)，也就是說其現在是這三個式子：

發現 \(\min_{x\in(mid, k]}\{ht_x\} + sa_i > r\) 中 \(\min_{x\in(mid, k]}\{ht_x\}\) 對于每個相同的 \(k\) 是定值，所以第三個式子可以寫成 \(sa_i > r - b(b = \min_{x\in(mid, k]}\{ht_x\})\) 的形式，這樣就和第一個式子合并了，于是依然是二維偏序。

復雜度 \(O(n \log^2 n)\)