zhangxyhp

摘要： 考慮如果沒有修改，用 ST 表就非常舒服。 考慮暴力修改，需要修改所有覆蓋了這個位置的區間，時間復雜度是 \(O(n)\) 的。 而如果只修改 \(\frac{\log n}{2}\) 層，時間復雜度就是 \(O(\sqrt{n})\) 的。查詢時從上往下查，最多查到第 \(\frac{\log n 閱讀全文

摘要： A. Tree Master 考慮根號分治，暴力處理。對于一層，設點數為 \(cnt\)。 若 \(cnt>\sqrt{n}\)，這樣的層最多有 \(\sqrt{n}\) 層，每一層最多計算 \(q\) 次，時間復雜度為 \(O(q\sqrt{n})\)。 否則 \(cnt\le\sqrt{n}\) 閱讀全文

摘要： 一.前言 早就學了掃描線了，但是有一道題當時沒做，現在才做，于是就來寫寫學習筆記。 哎我學習筆記前面咋老是這么多廢話啊 二.定義 掃描線其實是一種思想，就是遍歷某個值并將其加入數據結構，同時動態地解決一些問題。 聽起來很抽象，那就看例題吧。 三.例題 [poj1151]亞特蘭蒂斯 求矩形面積并。想象 閱讀全文

摘要： 考慮如果暴力 DP，設 \(f_{i,j}\) 為當前的串長為 \(i\)，在 AC 自動機的 \(j\) 節點的概率。轉移時枚舉在后面加的字符 \(k\)，如果加上 \(k\) 后匹配上了一個禁忌串就直接回到根節點，同時給答案貢獻，否則就繼續匹配。\(len\) 在 \(10^9\)，時間復雜度會 閱讀全文

摘要： 設 \(dp_{i,j,S}\) 表示填了 \(i\) 位，在 AC 自動機上的 \(j\) 號節點，當前覆蓋的字符串集位 \(S\) 的方案數。于是有轉移： \[\large{dp_{i,j,S}\to dp_{i+1,tr_{j,k},S\operatorname{or}sta_{tr_{j,k 閱讀全文

摘要： 容易發現相交的區間是不會產生貢獻的。于是不用考慮這個限制。 用單調棧可以求出以 \(a_i\) 為最小值和最大值的區間個數 \(qmn_i\) 和 \(qmx_i\)。 從小到大枚舉第二個區間的最小值，記 \(p_i\) 表示 \(i\) 的位置，則對于 \(i\) 的答案即為： \[\sum_{j 閱讀全文

摘要： \(k\le 20\)，考慮 \(O(2^k)\) 暴力枚舉加入的邊。但是邊數很大，時間復雜度很高無法承受。 考慮在一開始強制選這 \(k\) 條邊，然后跑最小生成樹，此時加入的邊就是一定會加入的邊。設這個邊集為 \(S\)。 將 \(S\) 連接的連通塊縮成點，點數為 \(O(k)\)。再在原圖上 閱讀全文

摘要： A. [COCI2009-2010#7] SVEMIR 顯然 boruvka。將所有點分別按照 \(x\)，\(y\)，\(z\) 排序，更新最小邊。時間復雜度 \(O(n\log^2 n)\)。 Code #include<cstdio> #include<iostream> #include<u 閱讀全文

摘要： 考慮初始的答案，顯然為卡特蘭數 \(H(n)\)。 考慮加入一對括號 \((l,r)\) 時對答案的貢獻。（\((l,r)\) 表示有一對括號，左括號在 \(l\)，右括號在 \(r\)。） 我們默認一開始有一對括號 \((0,n+1)\)。當出現一對括號 \((l,r)\) 時，首先要加上 \(( 閱讀全文

摘要： 很巧的 trick。 首先離線。從大到小掃 \(l\)，維護數組 \(p_i\) 表示當前出現 \(i\) 的最小的位置。 顯然當確定了左端點，從左到右的 \(\operatorname{mex}\) 是單調不降的。因此我們要求的就是一段區間 \([l',r']\)，滿足 \(\operatorna 閱讀全文