6.25

P6780 [Ynoi2009] pmrllcsrms

首先按 \(C\) 分塊，塊內答案是容易維護的，這時我們要處理的就是塊間的答案，我們的答案肯定是前一塊的某一個后綴 \(A_i\) 加上后一塊的某一個前綴 \(B_j\)，把我們要處理的信息放到二維平面上，發現是一個等腰直角三角形內，我們可以找到等腰三角形斜邊上的中點，橫豎分別切一刀，把這個三角形分成一個矩形和兩個等腰直角三角形，這樣我們就有了一個方便的分治結構，對于矩形的答案，我們可以通過其相鄰的兩個等腰直角三角形維護出來，具體而言，對于每一個節點，我們記下底邊對應的 \(\max A_i\)，以及左底邊對應的 \(\max B_i\)，這樣矩形答案直接加就行了，直接建出這個分治結構做就行，復雜度 \(\mathcal{(n+q)\log n}\)

P4128 [SHOI2006] 有色圖

Burnside 引理

有 \(|X/G|=\frac{1}{|G|}\sum\limits_{g\in G} X^{g}\)，一般來說，我們可以通過枚舉置換來暴力求不動點數量，也就是邊的等價類個數，而對于每個置換環，其貢獻是可以分開考慮的，因為一個置換可以拆成若干個置換環的乘積，他們同時作用在集合 \(X\) 上就是這個置換作用在 \(X\) 上，而置換是否不同只和環長有關，也就是說，我們實際上只需要枚舉出這個置換的所有環長，這里就是枚舉分拆數

如果求出了所有的環長，為 \(c_1\sim c_l\)，我們如何計算其不動點數量？首先在同一個等價類中的邊，其端點的并不可能在三個置換環中，因為我們只需要讓其中一個置換環走一步就不合法了，所以現在只需要考慮邊的端點在同一個置換環中，和在兩個不同的置換環中的答案

對于同一個置換環，我們走 \(\left\lfloor \frac{c_i}{2}\right\rfloor\) 步之后就會回到原點，于是其貢獻為 \(\left\lfloor \frac{c_i}{2}\right\rfloor\)，對于兩個不同的置換環，對于任意的兩個起點，我們走 \(\text{lcm}(c_i,c_j)\) 步之后會回到原點，那會劃分到 \(\frac{c_i\times c_j}{\text{lcm}(c_i,c_j)}\) 個等價類中，于是這一部分的貢獻就是 \(\gcd(c_i,c_j)\)

我們還要計算出來有多少的置換是能被拆成這 \(l\) 個置換環，這一步是簡單的

于是這樣就做完了，最后復雜度是 \(\mathcal{O}(\sum\limits_{k=1}^{n}k^2\times p_{n,k})\)，其中 \(p_{n,k}\) 是把 \(n\) 拆成 \(k\) 個可以相同的數的分拆個數

P5386 [Cnoi2019] 數字游戲

和 D2T2 那題一樣，序列分塊，對于每個詢問的塊，分治求其值域在 \([l,r]\) 的答案，復雜度 \(\mathcal{O}((n+q)\sqrt n)\)

AT_agc057_d [AGC057D] Sum Avoidance

容易說明集合 \(A\) 的大小就是 \(\left\lfloor \frac{n-1}{2} \right\rfloor\)，因為如果選了一個 \(i>\left\lfloor \frac{n}{2} \right\rfloor\)，那么必定不能選 \(S-i\)，這樣可以說明集合 \(A\) 的上界是 \(\left\lfloor \frac{n-1}{2} \right\rfloor\)，同時，我們可以構造出一個 \(A=[\left\lfloor\frac{n}{2}\right\rfloor +1,S-1] \cap \mathbb{Z}\)，這樣可以說明 \(A\) 可以取到這個上界

又發現，\(i\) 和 \(S-i\)，我們只能選擇其中一個，所以最優的策略肯定是能選的都選上，而 \(\left\lfloor\frac{n}{2}\right\rfloor\) 右半會出現沖突肯定是和左半出現沖突，也就是說，\(\left\lfloor\frac{n}{2}\right\rfloor\) 左半邊的選取并不需要考慮右半

設我們最后選出來的左半集合為 \(C\)，容易說明 \(\forall x\in C,y\in C\)，滿足 \(x+y\in C\)，這樣肯定是不劣的，而題目要求字典序最小，考慮貪心選取，則最小的數肯定是第一個不與 \(S\) 互質的數，設其為 \(d\)，對于 \(S\le 10^{18}\)，有 \(d\le 43\)

這時候，\(C\) 中 \(d,2d,3d,...\) 都被選取，那我們可以在膜 \(d\) 意義下考慮下一個數填啥，如果當前數沒被填過且填上他不會沖突，那么直接選中它肯定是最優的，而這種數最多只有 \(d-1\) 個，因為膜 \(d\) 相同的數最多只會被考慮一次，于是可以記 \(f_i\) 為膜 \(d\) 下與 \(i\) 同余的最小的在 \(C\) 中出現的數，如果要填 \(x\equiv r\pmod d\)，那么首先必須滿足 \(x<f_r\)，若填上了 \(x\)，他會更新到 \(\forall i\in [1,d),f_{(r+ir)\bmod d}\leftarrow f_{r}+ir\)，那 \(f_r\) 可以填的下界就是 \(\max\limits_{i=1}^{d-1}\left\lfloor\frac{(r+ir)\bmod d}{i} \right\rfloor+1\)，每次找到所有的 \(r\) 中最小的那個下界再更新 \(f\) 就行了

得到了 \(f\)，我們可以二分出來一個數的排名，這樣總復雜度就是 \(\mathcal{O}(Td^3)\)

P10107 [GDKOI2023 提高組] 樹

直接維護出來 \(f_{i,j}\) 表示 \(i\) 向下 \(2^j\) 的答案，長剖合并

6.26

P8861 線段

好題

考慮 \(l\le 10^5\le r\) 的部分分，這時候所有的區間都是相交的，而且左端點和右端點的貢獻實際上是獨立的，而操作相當于對于所有的左端點，對 \(L\) 取 \(\max\)，所有的右端點，對 \(R\) 取 \(\min\)，于是我們可以對左右兩個端點分別開一個堆，每次取出堆頂并暴力直接修改，如果有重合，可以用并查集并起來，這樣如果每次只修改 \(\mathcal{O}(1)\) 個區間，復雜度顯然正確，而修改多個區間至少會使一個區間被并起來，復雜度也是對的，對于查詢，可以用兩個樹狀數組維護

而左右不獨立的時候，我們可以考慮每次分治做，維護一個權值線段樹，在這顆線段樹上面操作，如果修改滿足 \(l\le ql\le mid\le qr\le r\)，那可以按照剛才的做法直接做，另一種情況只能是 \(mid<ql\) 或者 \(qr<mid\)，考慮第一種情況，這時候如果被修改了，那他就要被放到右兒子中，那與當前修改有交當且僅當 \(r\ge ql\)，找到 \(r\) 對應的堆，每次把被修改的區間的拉出來，然后把這些區間放到右兒子中，這樣每個區間只會被移動 \(\log n\) 次，復雜度也是對的

這樣總復雜度就是 \(\mathcal{O}(q\log ^2q)\)

6.30

模擬賽

T1

如果我們知道每個點選擇了 \(A\) 還是 \(B\)，那么可以把排序之后的 \(A\)，\(B\) 序列分別從大到小錯位計算即可，把 \((a_i,b_i)\) 放到二維平面上，發現如果某個點選擇了 \(a\)，那么在他左上方不可能存在點選擇了 \(b\)，容易交換證明，這樣可以用一條折線把整個平面分成兩部分，左上的為 \(a\)，右下的為 \(b\)，這樣容易做到 \(\mathcal{O}(n^2)\) 的 dp

考慮優化，從大往小掃 \(a\)，用線段樹維護 \(b\) 軸上每個區間的 \(b\) 的貢獻之和、到區間左端點的 dp 值，這樣如果要詢問 \(x\) 處的 dp 值，可以直接找到線段樹上的這些區間，從小往大掃一遍即可維護，\(a\) 的貢獻可以直接打前綴加標記，復雜度 \(\mathcal{O}(n\log n)\)

T2

拉反

記 \(T(x,y)=\sum\limits_{n}\sum\limits_{k} t_{n,k}x^ny^k\) 表示 \(n\) 個點，\(k\) 個紅點的樹的方案數，記 \(R(x,y)\) 表示根為紅色的方案數，記 \(B(x,y)\) 表示根為藍色的方案數，則有

\(T=R+B+1\)

\(R=xyT^{d-1}\times (1+B\)

\(B=xT^{d-1}\times (1+R)\)

可以得到

\(T=\frac{1+xT^{d-1}+y(xT^{d-1})^2+xyT^{d-1}}{1-y(xT^{d-1})^2}\)

記 \(f(x)=xT^{d-1},g(x)=\left(\frac{1+x+xy+x^2y}{1-x^2y}\right)^{d-1},h(x)=\frac{1+x+xy+x^2y}{1-x^2y}\)，則有 \(\frac{f}{g(f)}=x,T=h(f)\)，直接拉反可得

\([x^n]T=[x^n]h(f)=\frac{1}{n}[x^{n-1}]h'\left(\frac{x}{\frac{x}{g}}\right)^n=\frac{1}{n}[x^{n-1}]h'g^n\)

帶入后整理可得

\([x^n]T=\frac{1}{(d-1)n+1}[x^n]\left((1+x)(1+xy)\left(\frac{1}{1-x^2y}\right)\right)^{(d-1)n+1}\)

二項式展開，可以得到

\(ans=\sum\limits_{i=0}^{n}\binom{(d-1)n+1}{n-k-i}\binom{(d-1)n+1}{k-i}\binom{(d-1)n+i}{i}\)

可以 \(\mathcal{O}(n)\) 計算

T3

考慮組合意義，“每段的權值和的平方的乘積的和”可以轉化成：第 \(i\) 個位置有 \(w_{i}\) 個球，從每一段中間選兩個球（有序，可重）的方案數，設狀態 \(f_{i,0/1/2}\) 表示已經考慮了前 \(i\) 個位置，當前段選擇了 \(0/1/2\) 個小球的方案數，則有轉移：

• \(f_{i+1,0}\leftarrow f_{i,0}+f_{i,2}\)
• \(f_{i+1,1}\leftarrow (f_{i,0}+f_{i,2})\times w_{i+1}+f_{i,1}\)
• \(f_{i+1,2}\leftarrow (f_{i,0}+f_{i,2})\times w_{i+1}^2+2\times f_{i,1}\times w_{i+1}+f_{i,2}\)

再倒著做一遍記為 \(g\)，答案就是 \(\sum\limits_{i}f_{i,0}\times g_{i,0}\) 這樣可以做到 \(\mathcal{O}(nq)\)

這樣我們直接維護一個 \(3\times 3\) 的矩陣 \(A\)，其中 \(A_{j,k}=f_{i,j}\times g_{i,k}\)，這樣就能樹剖線段樹維護了

7.1

模擬賽

T1

發現 \(\zeta(F(l,r))\) 是一個 \(sum(l,r)\bmod (B-1)\) 的東西，那只需要知道所有區間的權值和以及其中出現的數，就可以知道這個區間是否能修改一個字符滿足條件

具體地，從右往左掃描左端點，維護每個 \(a_i \bmod (B-1)\) 第一次出現的位置，用一個集合維護 \((sum-a_i)\bmod (B-1),i\in [l,r]\)，存在 \(f_{sum,*}\) 里，最后我們只需要查詢形如 \(\sum\limits_{S\cap T=\emptyset,sum\ne x}f_{sum,S}\) 的東西，做高維前綴和即可，對于 \(x=0\) 和 \(x=B-1\) 的情況需要特判

T3

考慮每一個位置對答案的貢獻，如果記 \(l_i\) 為 \(i\) 左邊第一個嚴格大于 \(a_i\) 的位置，\(r_i\) 為 \(i\) 右邊第一個嚴格大于 \(a_i\) 的位置，那么 \(i\) 對所有的 \(j\ne i,j\in [l_i+1,r_i-1]\) 都有 \(C\) 的貢獻，而如果存在相同元素且其 \((l_i,r_i)\) 完全相同，我們只能在其中一個這樣的 \(i\) 算貢獻，可以保留最右邊的這樣的位置，我們把這樣具有相同貢獻的點叫做 “等勢點”

考慮詢問，\(h_x=h_{x+1}\) 不用處理，不妨令 \(h_x<h_{x+1}\)，\(h_x>h_{x+1}\) 的情況可以按照 \(h_x<h_{x+1}\) 的情況把貢獻都乘上負號，考慮其他權值 \(v\) 的影響

• \(v\ge h_{x+1}\) 或 \(v< h_x\)，沒有影響
• \(v=h_{x}\)，如果 \(x\) 左邊有一個等勢點，對 \(x\) 的位置單點減去 \(C\)，否則 \([l_x+1,x]\) 減去 \(C\)；若 \(x+1\) 右邊存在 \(h_x\) 的等勢點，那么 \(x+1\) 單點加 \(C\)，否則 \([x+1,r_{x}+1]\) 區間加 \(C\)
• \(v\in [h_x+1,h_{x+1}-1]\)，這些點貢獻到的區間只可能是左右端點移動了 \(1\)，左側這樣的值，就是 \(x\) 左邊 \(v\in [h_x+1,h_{x+1}-1]\) 的區間中大于 \(h_x\) 的單調棧的元素個數，容易使用單側遞歸線段樹實現

總復雜度 \(\mathcal{O}(n\log^2n)\)

7.3

模擬賽

T1

把值域上相鄰的沒出現過的數縮成一段 \([l,r]\)，發現這一段的長度不能超過 \(\left\lfloor \frac{n-k-\sum\limits_i[a_i<l]}{2} \right\rfloor\)，記這個東西 \(+1\) 為 \(lim\)，段長為 \(len\)，那么答案就是 \(\binom{n-k+m-1}{m-1}-\sum\limits_{i=0}\sum\limits_{j=lim_i}^{n-k}\binom{j+len_i-1}{len_i-1}\binom{n-k-j+m-len_i-1}{m-len_i-1}\)
考慮組合意義快速求后面的東西，有 \(n-k+m-2\) 個位置，\(m-2\) 個球，在 \(j\) 和 \(j+1\) 之間塞一個板，要求 \(j\ge lim_i\) 的方案數

直接枚舉前 \(\lim_i+1\) 的位置放了多少球

\(\sum\limits_{i=0}^{len_i-1}\binom{lim_i+len_i-1}{i}\binom{n-k+m-lim_i-len_i}{m-i-1}\)

復雜度 \(\mathcal{O}(n)\)

T2

直接放在直徑上討論，兩個人至少有一個會往直徑上走，對于兩個人中至少有一個走到直徑端點的情況都是容易處理的，只需要處理兩個人都向內走的情況

這時候就是一個區間查詢，預處理出來線段樹上 \([l,r]\) 中 每一個 \(x\in [l,r)\) 的\((a,b)\)，其中 \(a=\max\limits_{u\in sub(x)}\text{dist}(l,u),b=\max\limits_{v\in sub (x+1)}\text{dist}(r,v)\)，要求形如 \(ax+by\) 的值， 可以直接維護出來所有斜率為 \(a\)，截距為 \(b\) 的直線組成的下凸殼，這樣直接在凸包上遍歷一遍可以查詢出來 \(a\frac{x}{y}+b\) 的最值，可以二分，或者把詢問離線下來按照 \(\frac{x}{y}\) 排序，理論復雜度可以做到 \(\mathcal{O}((n+q)\log n)\)

T3

首先在開頭加入 11，在結尾加入 00，這樣對答案沒有影響

考慮相鄰的兩個位置，把 11 記為 L，00 記為 R，10/01 記為 .

考慮每一次操作相當于什么

1. R.... \(\rightarrow\) ....R
2. ....L \(\rightarrow\) L....
3. R...L \(\rightarrow\) .....
4. ..... \(\rightarrow\) L...R

在最開始的時候把相鄰下標差為 \(4\) 的倍數的 R 和 L 進行第三種操作刪掉，之后我們可以把能每個 L 和 R 的連續段盡量縮地比較短，直到每個相同字符之間的距離變成 \(0\) 或者 \(2\)

對于每個端之間的 .，我們可以進行第四種操作之后再進行第三種操作抵消，發現其實與直接使用第一種和第二種操作等價，所以不用再考慮三四兩種操作了

那么現在剩下的操作只有：將一段 L 往左移，將一段 R 往右移，直接計算一段 . 的貢獻

又發現一段 . 的貢獻是一個凸函數，于是左 R 右 L 的段只有一個會移動，這樣就能直接線性 dp 了

7.4

模擬賽

傻逼模擬賽糙擬嗎

T1

傻逼

T2

傻逼

T3

傻逼

7.5

P10790 [NOI2024] 樹形圖

純神

縮點，一二類點只可能出現在入度為 \(0\) 的那個強連通分量里，而且縮點后的圖必須是一棵以那個入度為 \(0\) 的強連通分量為根的樹，否則不會存在一類或二類點，下面只考慮入度為 \(0\) 的那個強連通分量

我們可以給出一種一類點的判定方式，如果以這個點為根跑出來一個 dfs 樹，那么非樹邊只能存在返祖邊，不難發現這就是判定一類點的充要條件，考慮部分分，如果圖上不存在一類點，那么所有的點都是二類點，而如果我們已經知道了一個一類點，那么可以以這個點為根跑出一個 dfs 生成樹，考慮在這個樹上找一類點和二類點

對于一類點，手玩一下鏈的情況，可以發現，對于一條返祖邊 \((u,v)\)，其中 \(u\) 在 \(v\) 的下面，我們把其包含的所有的點（不包括 \(v\)），都標記一下，最后根之外的所有點都至少會被標記一次，而被標記兩次的點不可能成為一個一類點，那一類點充要條件就是只被標記一次嗎？發現并不是，因為如果包含他的邊 \((u,v)\) 指向了一個二類點，那么這個點就不能是一類點，于是我們可以說明，一類點的充要條件就是：只被一條邊包含，且這條邊指向一個一類點，必要性我們已經說明，充分性的證明，可以考慮直接構造一顆 dfs 樹，當前點子樹中的點原地不動，當往下走到 \(u\) 時，把 \(v\) 從上面接過來，接著以其為起點開始遍歷所有不在 \(u\) 子樹中的點，這樣 \((u,v)\) 鏈上的點是滿足條件的，相當于我們把一個環轉了一下，而不在 \((u,v)\) 中的，由于 \(v\) 是一個一類點，則其余點肯定只有返祖邊，這樣就給出了一個合法的構造，從上往下做一遍就能找到所有的一類點

考慮找二類點，這時候我們需要原先的一類點仍然是一類點，那么為了保證連通性，那些覆蓋到一類點的 \((u,v)\) 絕對不能被刪除，如果我們想判定某個點 \(u\) 是否為二類點，那么需要知道是否存在一種方案，刪掉若干條標記了他的邊，使得他變成一類點

• 如果有至少兩條不能刪除，那么其肯定不能成為二類點
• 如果只有一條邊不能刪除，記為 \((u,v)\)，那么其是否能成為二類點，取決于 \(v\) 是否為一類點或二類點
• 所有邊都能刪除，必須滿足存在一條邊 \((u,v)\)，滿足 \(v\) 為一類點或二類點

這樣找一類點和二類點的工作就完成了，接下來是找到任意一個一類點

發現一類點對應的 dfs 樹，其葉子均滿足入度為 \(1\)，于是可以每次刪去入度為 \(1\) 的點，保留重邊但是刪去自環，使用啟發式合并，可以做到 \(\mathcal{O}((n+m)\log n)\)

7.6

P10789 [NOI2024] 登山

太難了

把 \(l_i,r_i\) 都變成其對應的深度（\(r_i>l_i\)），記 \(lim_i=dep_i-h_i-1\)

容易提出 \(\mathcal{O}(n^2)\) 做法，考慮到每沖刺到一個點 \(u\)，其之前的限制在以后肯定沒有 \(u\) 處的限制嚴，那么直接記 \(f_u\) 為從 \(1\) 走到 \(u\) 的方案數，接著枚舉他向下滑到了哪個點，能貢獻到他的祖先是一段區間，可以簡單維護

接著考慮 \(l_i=r_i\)，仍然去考慮兩個被沖刺點中間的點，那每一個點能貢獻到也是形如一段祖先鏈，那么找到這個祖先鏈求和就行了，考慮樹上倍增，記 \(t_{u,*}\) 為 \(u\) 祖先鏈上一段的 \(lim\) 的最小值，這樣可以 \(\mathcal{O}(\log n)\) 復雜度找到可以貢獻到的區間，記當前點可以沖刺到的那個點為 \(x\)，那么只需要在 \(x\) 處做一個鏈加就行了，復雜度 \(\mathcal{O}(n\log n)\)

接著考慮 \(l_i\ne r_i\)，這個點的貢獻應該是一段祖先鏈上的 \(f\) 的和，則記 \(s_i\) 為 \(i\) 到根鏈的 \(f\) 之和，那么這個點的貢獻形如一個 \(s_{*}-s_{l-1}\)，\(s_{l-1}\) 的貢獻可以和 \(l_i=r_i\) 的部分一樣處理，這時候考慮右端點限制的變化，如果其到某個祖先鏈上的點 \(v\) 的權值都大于等于當前限制，那么貢獻這些點的轉移是可以一起處理的，于是考慮再建出來一棵樹，令每個點的新父親為其原樹祖先鏈上 \(lim\) 第一個嚴格小于他的的點 \(p_i\)，考慮在每個點的 \(p_i\) 的祖先鏈上計算剩余貢獻，可以維護一個 \(w_v\)，表示 \(v\) 對應的 \(i\) 的個數，接著做一個鏈加就行了

求 \(w_v\)，發現每個 \(i\) 能貢獻到的 \(w_v\) 在第二棵樹上仍然是一條祖先鏈，接著倍增出來就行了

這樣總復雜度是 \(\mathcal{O}(n\log n)\)

7.7

UNR D1

7.8

UNR D2

7.9

P10787 [NOI2024] 樹的定向

考慮特殊性質A，發現此時，對于任意一條邊，無論怎樣選擇方向都是合法的，因為可以構造如下定向方案：將每個點黑白染色，強制讓白點連向黑點，此時任意一條長度大于等于二邊都至少跨過了三個相鄰的點，則至少會有兩種方向的邊，而我們任意調換方向顯然也是合法的

那現在我們有結論：若對于任意一個限制，其至少包含兩條未被定向的邊，則這時可以對其他邊任意定向

對著這個做，我們要維護的是兩個事情：刪掉一條邊，將所有只包含了兩=一條邊的限制找出來；判斷一個限制是否已經被滿足

發現這是一個類似拓撲排序的過程，考慮一個倍增優化建圖，具體而言，對于每個點 \(u\)，建出來 \(\log\) 個虛點，記作 \(id_{u,2^k}\)，令 \(id_{u,2^{k-1}}\) 和 \(id_{fa_{u,2^{k-1}},2^{k-1}}\) 向 \(id_{u,2^k}\) 連邊，對于拓撲排序，維護一個隊列，每一個節點，若其度數只為 \(1\) 或者其度數為 \(0\) 時，將其入隊，這樣每個點最多只會被入隊兩次，而每次入隊只會更新其所有的出邊，邊數為 \(\mathcal{O}(n\log n)\) 級別，這樣就可以找到所有只包含了一條邊的限制

查詢限制是否被滿足，這里用一個樹上帶權并查集維護，每個點的權值為其到聯通塊中祖先的邊權和，均攤 \(\mathcal{O}(n)\)

總復雜度 \(\mathcal{O}(n\log n)\)，常數比較大

7.10

P9479 [NOI2023] 桂花樹

純 Ad-hoc

考慮 \(k=0\)，直接從小到大塞點，答案為 \(\prod\limits_{i=n}^{n+m-1}(2i-1)\)。

擴展到 \(k>0\)，每次塞一個點，他與別的點的 lca 的編號在區間 \([i+1,i+k]\) 中，那么我們將 \(i\) 塞入一條邊或者一個點下面的時候，同時塞入其與別的點的 lca，也就是把其 lca 放在那個位置，而這個點掛在這個 lca 的下面，那可以把這個要塞的 lca 放到后面轉移，于是把他記在狀態里，記 \(f(i,S)\) 表示當前塞的點的編號為 \(i\)，現在空白的點的集合為 \(S\)，則有三種轉移

• 將當前點塞入一個空白點，轉移系數為 \(1\)
• 將當前點和一個空白點塞到一個條內，轉移系數 \(i+popcount(S)-1\)
• 將當前點直接塞進去，轉移系數 \(2(i+popcount(S))-1\)

總復雜度 \(\mathcal{O}(Tmk2^k)\)

AT_abc277_h [ABC277Ex] Constrained Sums

我擦

考慮 2-sat，每個點用 \(m+2\) 個 \(01\) 變量 \(x_{i,j}=[v_{i}\ge j]\)

若 \(x_{i,j}=1\)，則有

• \(x_{i,j-1}=1\)
• 若存在限制 \((i,k,l,r)\) 或者 \((k,i,l,r)\)，則 \(x_{k,\min(r-j+1,m)}=0\)

若 \(x_{i,j}=0\)，則有

• \(x_{i,j+1}=0\)
• 若存在限制 \((i,k,l,r)\) 或者 \((k,i,l,r)\)，則 \(x_{k,\max(l-j+1,0)}=1\)

同時需要滿足 \(x_{i,0}=1,x_{i,m+1}=0\)

7.13

CF1117G Recursive Queries

為了方便，令 \(p_0=p_{n+1}=\infty\)，考慮拆貢獻，記 \(lf_i\) 為 \(i\) 左邊第一個大于他的數的位置，記 \(rt_i\) 為 \(i\) 右邊第一個大于他的數的位置，于是答案就是 \(\sum\limits_{i=l}^r \min(rt_i,r)-\max(lf_i,l)+1\)，可以把詢問拆成 \((1,r,l,r)-(1,l-1,l,r)\)，然后只需要離線二維數點了，容易做到 \(\mathcal{O}(n\log n)\)

uoj938方片騎士

幽默

直接換根，有轉移

• 若 \(|son(u)|>1\)，則有 \(f_u=\left \lceil \log_2 \left( \sum\limits_{v\in son(u)} 2^{f_v} \right) \right \rceil\)
• 若 \(|son(u)|=1\)，則有 \(f_u=f_v+1\)

直接寫線段樹可以做到 \(\mathcal{O}(n\log n)\)

而換根時兒子中只有 \(f\) 最大的可能成為新的根，這樣每次就可以暴力做了，復雜度線性

CF1270H Number of Components

首先發現每個連通塊都是一個原序列上的連續段，那我們只要數 \(i\) 和 \(i+1\) 沒有連邊的位置就行了，若 \(i\) 和 \(i+1\) 沒連邊，其充要條件為 \(\min_{j\le i}a_j>\max_{k>i}a_k\)，考慮枚舉 \(v=\max_{k>i}a_k\)，如果把 \(\le v\) 的位置標成 \(0\)，其余位置標成 \(1\)，則最后合法的序列形如 \(11..1100..00\)，那么對每一個 \(v\) 維護 \(f_v\) 表示最后相鄰位置為 \(10\) 的數量，最后只需要判斷是否滿足 \(a_i>v,a_{i+1}\le v\) 且 \(f_v=1\) 就行了，維護 \(f_v\) 也是簡單的，每次修改時只需要考慮兩個相鄰位置的貢獻就行了，復雜度 \(\mathcal{O}(n\log n)\)

CF2002F2 Court Blue (Hard Version)

氣笑了。

當 \(x,y\) 較小時總有合法的構造，假設 \(x<n-B,y<m-B\) 的 \((x,y)\) 都是合法的，直接 dp，取 \(B=120\) 即可通過，復雜度 \(TB^2\log V\)

CF825G Tree Queries

太幽默了

把第一次染成黑色的點當作根，記 \(f_i\) 為 \(i\) 到根鏈上的最小編號，維護一個 \(val\) 表示所有黑點 \(f_i\) 的最小值，查詢時就是 \(\min(val,f_i)\)

CF547D Mike and Fish

把每行和每列都建一個點，一個點 \((x,y)\) 就是連一條第 \(x\) 個行到第 \(y\) 個列的邊，對于最后度數為奇數的點，我們向一個虛點連邊，這樣就構造出了一個歐拉圖，跑歐拉回路給邊定向即可

AT_arc176_e [ARC176E] Max Vector

直接拆點 \(x_{i,j}=[X_i\ge j],y_{i,j}=[Y\ge j]\)，每一個限制都是形如：若存在一個 \(X_j<a_{i,j}\)，需要滿足 \(\forall j,Y_j\ge a_{i,j}\)，而 \(X_j\ge a_{i,j}\) 沒有限制，那么直接建一個虛點刻畫如上限制就行了

實際建圖可以把 \(Y\) 的那一列反過來

qoj7973

好題啊，為啥這么多差評

對于一個括號序列，我們考慮他的前綴和 \(s_i\)，容易發現，對于前綴和最小的位置 \(p\)，\([1,p]\) 的括號只會操作 \()\) \(\rightarrow\) \((\)，\([p+1,n]\) 的括號只會操作 \((\) \(\rightarrow\) \()\)，因為如果我們只考慮前面的操作，最后肯定會有 \(s_p\ge 0\)，此時，\(>p\) 的位置前綴和肯定也大于等于零，那這時候如果對后面的操作 \()\) \(\rightarrow\) \((\)，肯定還要操作一個別的 \((\) \(\rightarrow\) \()\)，這樣肯定不優，我們反過來從后往前考慮，對于 \([1,p]\) 的也可以這樣證明

那現在就有一個貪心，這里先說 \([1,p]\) 的情況，\([p+1,n]\) 的情況類似，我們從左往右掃指針，同時用一個小根堆維護那些沒有被用過的 \(a_i\)，當 \(s_i<0\) 時，我們取出來堆中的最小值即可，這樣對于左半段，需要將 \(\left\lceil -\frac{s_p}{2} \right\rceil\) 個取出來，對于右半段，需要取出來 \(\left\lceil \frac{s_n-s_p}{2}\right\rceil\) 個，這樣直接做可以做到 \(\mathcal{O}(nq\log n)\)

發現這是一個模擬費用流（這里是省選聯考2023人員調度？）可以做到線性對數，具體來說，把每一個 \(s_i<0\) 的位置拉出來，在這些位置建一些左部點，而每個左部點可以向其左邊的所有右部點連邊，那不妨記一個 \(f_i\) 表示 \([1,i]\) 中選中的右部點個數減去左部點的個數，而完美匹配只需要滿足所有的 \(f_i\ge 0\)，那現在考慮加入一個右部點 \(i\)，其會影響所有的 \(j>i,f_{j}\leftarrow f_{j}+1\)，可以用線段樹維護

修改一個右部點時，記其被修改為 \(x\)

• 如果 \(x>a_i\)，且 \(a_i\) 原來也沒有被選中，此時不會造成影響
• 如果 \(x<a_i\)，且 \(a_i\) 原來沒有被選中，如果直接加進去這個點，此時我們肯定要撤銷另一個點，而對于 \(j<i,f_j=0\) 的位置，我們顯然無法撤銷其中任何一個點，于是找到最大的這樣的 \(j\)，查詢區間最小值，和 \(x\) 進行比較就行了
• 如果 \(x>a_i\)，且 \(a_i\) 原來被選中了，此時我們可能會撤銷這個點，這時會導致 \(\forall j>i,f_j\leftarrow f_j-1\)，那么這時候我們需要再加入一個新的點，如果這時候選中了 \(k\)，則需要滿足 \([i,k]\) 中不存在 \(f_j=0\)，和上面的也類似

那么我們只需要用線段樹維護區間加，區間 \(\min\)，區間最小值第一次出現的位置，區間最小值最后一次出現的位置，容易做到 \(\mathcal{O}((n+q)\log n)\)

P3266 [JLOI2015] 騙我呢

這不是那個反射容斥題嗎，當時學的時候就想做來著

題目要求從 \((0,0)\) 開始，每次可以從 \((x,y)\) 走到 \((x+1,y)\) 或者 \((x,y+1)\)，走到 \((n,m)\)，不經過直線 \(y=x+a,y=x-b\)，其中 \(a,b>0\) 的方案數

經典的，我們記一個字符串 \(S\)，當碰到 \(y=x+a\) 時，在字符串后面添加一個 \(A\)，碰到 \(y=x+b\) 時，在字符串后面添加一個 \(B\)，而我們要數的就是 \(S=\emptyset\) 的路徑個數，而我們發現，對于一個 \(S\ne \emptyset\) 的路徑，有 \([S\ne \emptyset]=[A\subseteq S]+[B\subseteq S]-[AB\subseteq S]-[BA\subseteq S]+[ABA\subseteq S]+[BAB\subseteq S]-...\)，這里的 \(\subseteq\) 是子序列，證明的話，若最長的 \(AB\) 相間的字符串 \(T \subseteq S\)，則其相反串肯定不是 \(S\) 的子序列，否則我們肯定可以找到一個更長的 \(T\)，若 \(T\) 前的系數為 \(-1\)，則長度小于 \(T\) 的串的系數之和為 \(2\)，若 \(T\) 前的系數為 \(1\)， 則長度小于 \(T\) 的串的系數之和為 \(0\)，得證

這樣我們就做完了容斥，那反射呢？如果我們把終點按 \(y=x+a\) 翻折過去，再直接計算 \((0,0)\) 道終點的方案數，求得就是包含 \(A\) 的路徑數量，再按 \(y=x-b\) 翻折過去，求得就是包含 \(AB\) 的路徑數量......這樣一直做就行了，復雜度線性

CF1515H Phoenix and Bits

我去年是不是還不會這個題？

我們可以實現 01trie 上的 split 和 merge，從而方便進行區間操作

對于 & 操作，我們可以把他拆成 \(\mathcal{O}(1)\) 個 | 和 ^

對于 ^，其作用就是交換兩個子樹，而且其在整數集上是一個交換群，那我們可以直接打標記

對于 |，其作用就是每次合并兩個子樹，暴力合并即可，可以發現這樣的操作只有 \(\mathcal{O}(n\log V)\) 次，因為每一個節點的深度都是 \(\mathcal{O}(\log V)\) 級別的

這樣在分裂合并的時候可能會下傳一些標記，復雜度 \(\mathcal{O}(n\log^2 V)\)