[HDU 4787]GRE Words Revenge

操作有兩種：
1. 學一個單字
2. 讀一篇文章，問你有幾個子字串是背過的單字 (只要位置或長度不同就是不同的子字串)

如果先學完所有單字，然後給要你讀幾篇文章問你答案，可以怎麼做呢？

首先對所有單字建立$AC$自動機，然後讓每篇文章在$AC$自動機裡面轉移
每走到一個點，就把答案加上「沿著失配邊可以走到的單字結尾數量」
可以對「將所有失配邊反向形成的樹」建立樹壓平序列

把樹壓平就是對樹做一次$dfs$，把每個點的進入和離開時間記錄下來即可
這樣任何一棵子樹都可以用一個區間表示了

用線段樹來維護這個樹壓平序列
每個單字結尾相當於把整個子樹都$+1$ (實作上將樹壓平序列對應的區間$+1$)，可以使用線段樹的區間修改
「沿著失配邊可以走到的單字結尾數量」相當於樹壓平序列上對應點的值，可以使用線段樹的單點查詢
這樣讓大小$N$的$AC$自動機讀入長度$L$的文章，時間複雜度為$O(L\log N)$

現在，需要動態新增字串 (單字)
可是$AC$自動機的失配邊只能離線建立
怎麼辦呢？

解決方案：
$BIT$ ($Binary\ Indexed\ Tree$) 套$AC$自動機

當新增第$N$個字串時，$BIT$的第$N$個元素就是第$N-lowbit(N)+1$個到第$N$個字串組成的$AC$自動機
讀文章時，$BIT$查詢$\log N$個自動機把答案加起來即可

加字串到$BIT$前需要先判斷這個單字有無背過，否則會重複計算

時間複雜度：$O(10^{5}\log 10^{5}+(5*10^{6})\log^{2}10^{5})$

code:

[HDU 2243]考研路茫茫——单词情结

要計算有多少字包含任一個字根，我們可以先算出有多少字不包含任一個字根，然後再用全部的情況去扣掉

可以考慮把這些字根做成一個$AC$自動機
這樣一來，長度$n$不包含任何一個字根的單字數量就是在這個$AC$自動機裡面走$n$步沒有碰到結束集合的方法數了

可以發現，這個$AC$自動機的大小不會超過$5*5+1=26$ (根也要算進去)，因此可以直接利用矩陣快速冪計算走$n$步到達各個位置的方法數
設這個$AC$自動機的轉移矩陣是$A$

因此長度$\leq L$且不包含任一個字根的單字數量就是走$0$步、走$1$步、走$2$步、走$3$步、...、走$L$步的情況全部加起來
對應到的矩陣就是$A^{0}+A^{1}+A^{2}+A^{3}+...+A^{L}=\sum_{i=0}^{L}A^{i}$

直接算會超時

說明：
$Sum(n)=\sum_{i=0}^{n}A^{i}$
$M$為$A$的大小

可以發現，如果我們已經算出$Sum(n)$
再把它乘上$A^{0}+A^{n+1}$，就變成$Sum(2n+1)$了！

更精確地說，我們可以得到以下遞迴式：
$if$ $n$是奇數，$Sum(n)=Sum(\frac{n-1}{2})*(A^{0}+A^{\frac{n+1}{2}})$
$if$ $n$是偶數，$Sum(n)=Sum(n-1)*A^{n}$

算出$A^{n}$利用快速冪可以做到$O(M^{3}\log n)$
矩陣加法$O(M^{2})$
遞迴不會超過$O(\log n)$層
因此算出$Sum(n)$的時間複雜度就是$O((M^{3}\log n+M^{2})\log n)$了

注意答案不是$Sum(L)$，是所有情況減掉$Sum(L)$
所有情況的數量 ($\sum_{i=0}^{L}26^{i}$) 一樣可以依照以上方法計算出來
另外，題目要求$\mod 2^{64}$，因此只要在$unsigned\ long\ long$之下進行這些運算並自由讓它$over\ flow$即可

時間複雜度：$O(M^{3}\log^{2}L)$

code:

[HDU 5412]CRB and Queries

經典題型：區間第$k$小帶修改

這種題目經典做法有兩種：
1. $BIT$ ($Binary\ Indexed\ Tree$) 套持久化線段樹 (幾乎每次都MLE的作法)
時間複雜度：$O(\log^{2}N)$修改，$O(\log^{2}N)$查詢
空間複雜度：$O(N\log N+Q\log^{2}N)$
2. 線段樹套名次樹 (請參考這篇)
時間複雜度：$O(\log^{2}N)$修改，$O(\log^{3}N)$查詢
空間複雜度：$O(N)$

這次，我來向大家介紹一種只用到$vector$和$BIT$的作法，神奇吧

說明：
$q_{i}$代表第$i$次修改或詢問
$q_{i}.l$和$q_{i}.r$代表詢問$q_{i}$的左右邊界
$q_{i}.k$代表詢問$q_{i}$的名次

首先，不考慮TLE問題的話

我們把原序列的所有數字，以及修改操作的數字，都賦予一個「生命週期」
也就是，這個數字在第幾次到第幾次詢問內有效
於是我們把序列和以後修改後的樣貌取代成了$O(N+Q)$個物件，有值、位置、生命週期這幾個屬性
再提醒一次，序列已經不存在，我們只剩一堆具有生命週期的物件

對每個詢問$q_{i}$，我們可以二分搜值域 (值域大小經離散化後為$O(N+Q)$)
假設我們現在搜到值域$[l,r]$，算出$mid=\frac{l+r}{2}$
然後檢查看看有幾個數字，生命週期涵蓋$q_{i}$、$\leq mid$且位在$[q_{i}.l,q_{i}.r]$內
如果這種數字數量$<q_{i}.k$，代表$q_{i}$的答案$>mid$
否則，代表$q_{i}$的答案$\leq mid$

直接做的話時間複雜度是$O(Q(N+Q)\log(N+Q))$

信不信，我們可以把那個$Q(N+Q)$合併成$N+Q\log N$！

方法是全部的$q_{i}$一起二分搜
假設我們現在搜到值域$[l,r]$，算出$mid=\frac{l+r}{2}$
現在，只把值$\leq mid$的數字拿出來
然後隨著時間推進，在這些$\leq mid$的數字中，有些數字會出現，有些數字會消失
我們可以用線段樹來維護目前數字的分布狀況，或者像我簡單一點，用$BIT$
當時間到達$q_{i}$的位置的時候，我們可以立即從線段樹中$O(\log N)$得出$[q_{i}.l,q_{i}.r]$內有幾個數字$\leq mid$
如果數字數量$<q_{i}.k$，代表$q_{i}$的答案$>mid$
否則，代表$q_{i}$的答案$\leq mid$

把所有答案$>mid$的$q_{i}$，$q_{i}.k$減掉剛剛找出的數字數量後 (想一想，為甚麼XD)，丟到區間$[mid+1,r]$遞迴繼續二分搜
把所有答案$\leq mid$的$q_{i}$丟到區間$[l,mid]$遞迴繼續二分搜

這就是整體二分的概念

時間複雜度：$O((N+Q\log N)\log(N+Q))$

code:

[HDU 5140]Hun Gui Wei Company

簡單來說，這題就是先給你一堆點 $(x,y)=(level,age)$ 和各自的權重 ($salary$)，然後開始問你一個矩形內所有點的權重總和

可能很多人直覺是二維線段樹
但其實這題不用那麼複雜 (如果你熟悉持久化結構的話)

哈我已經把答案講出來了 (持久化線段樹)

由於這題$x$和$y$的範圍很大，我們可以先把一開始給的點離散化
然後對於每個$x$，維護所有$\leq x$的點的資訊，也就是它們的區間權重總和
這會需要用到持久化線段樹，從左到右慢慢加點，才不會TLE或MLE

因此，我們已經有能力求出所有形如$(x_{left},x_{right},y_{down},y_{up})=(-INF,x,y_{1},y_{2})$的矩形，裡面點的權重總和了
方法是對$x座標\leq x$ ($x座標$最大) 的那棵線段樹查詢$[y_{1},y_{2}]$離散化後的等價區間

那對於形如$(x_{left},x_{right},y_{down},y_{up})=(x_{1},x_{2},y_{1},y_{2})$的矩形要怎麼辦呢？
可以發現，答案就是$Sum((-INF,x_{2},y_{1},y_{2}))-Sum((-INF,x_{1}-1,y_{1},y_{2}))$
($Sum(矩形)$代表查詢對應矩形得到的答案)

我的code考慮了詢問時的$int$溢位
沒考慮會怎樣？我沒試過XD

時間複雜度：$O(N\log N+M\log N)$

code:

[HDU 4605]Magic Ball Game

我們先假設$N\leq 1000$且$Q\leq 1000$
這樣就可以直接從根出發，每到一個節點$u$就將機率依和$w_{u}$的大小關係乘上對應的分數
如果在走到$v$前走到$w_{u}=x$的，代表沒有答案

現在$N\leq 100000$且$Q\leq 100000$
會TLE的情況就是高度很高、接近一條鏈的樹
那我們能不能每個節點只要走一次就好呢？

可以的！

可以發現，每通過一個節點$u$
走到左子樹相當於為所有$x<w_{u}$的的詢問貢獻$\frac{1}{2}$，$x>w_{u}$的貢獻$\frac{1}{8}$
走到右子樹相當於為所有$x<w_{u}$的的詢問貢獻$\frac{1}{2}$，$x>w_{u}$的貢獻$\frac{7}{8}$
這是個離線操作的方式

乍看之下很像區間修改
沒錯，我們可以用線段樹或$treap$來實現區間修改！
可是線段樹不離散化就得$copy-on-write$
因此我這裡採用了$treap$

這裡的區間包含各種長度只有$1$的$[w_{u},w_{u}]$和剩餘右界是$w_{u}-1$，左界是右界往左走第一個碰到的$w_{v}+1$的區間 (左界有可能是$-INF$)，加上最右邊右界是$INF$的區間

直接將每個區間的右界選作代表存成一個節點，因此查詢$x$時只要找到最接近$x$且$\geq x$的節點就好了
在一條$\log N$的查詢路徑上，$\geq x$的節點中最接近$x$的就是所求，可以透過更新答案的方式

那遇到無解的情況要怎麼判斷？
我們可以為每個節點新增一個屬性：exist
在前往子節點前先將代表$w_{u}$的節點的exist設為$false$
這樣只要判斷查到的節點exist是不是$true$就好，不是的話代表無解

注意遞迴到子節點算完返回時要抵銷對$treap$的修改，才能再遞迴到另一個子節點繼續算

時間複雜度：$O((M+Q)\log N)$ (其實$M=\frac{N-1}{2}$永遠成立)

p.s.如果你想用持久化結構寫出這題的在線作法，你會得到MLE (你想要記憶體回收？沒用的www)

code:

[HDU 3415]Max Sum of Max-K-sub-sequence

假設序列不是環狀的，那要怎麼做呢？
如果我們把序列處理成前綴和 (表示為$SUM_{i}$)，那麼問題就變成，找出兩個點$a$和$b$ ($a\leq b$)，使得$b-a+1\leq K$且$SUM_{b}-SUM_{a-1}$盡量大

因此，我們可以從小到大枚舉$b$，利用單調隊列維護$\min_{k=b-K}^{b-1}SUM_{k}$ (注意$k$的大小寫)，然後慢慢更新答案就好了

現在序列是環狀的
我們可以把整個序列再複製一次，接到尾巴
這下就可以把序列當成鏈狀的看待了

時間複雜度：$O(N)$

code: