Mato is No.1

原題見這里（BZOJ和BSOJ都掛了，真杯具，只能借助RQ了囧……）

難度不是很大，就是特殊情況比較多，比較猥瑣（不過本題數據弱，就算不考慮所有的特殊情況也能過7個點）。
首先O(NM)的樸素算法很好想到：枚舉K，然后給每個結點編號即可。在編號時，先隨便指定一個未編號的點，設它的編號為0，然后遍歷所有和它相關聯的邊（這里可以把原圖想象成一個無向圖），將這些邊的另一個端點編上號即可，中間若某個點的編號出現矛盾，則這個K不合法，否則這個K合法。
然后進行優化：合法的K實際上是有限制的，它必然是某個數的因數，具體來說，對這個圖進行DFS，并考察其中所有的跨越邊和逆向邊，對于跨越邊<i, j>，設遍歷樹中i、j間距離為D，則合法的K必然是(D-1)的因數（因為i和遍歷樹中j的父結點都有指向j的邊，它們的編號應相同，而它們之間的距離為(D-1)）；對于逆向邊<i, j>，設遍歷樹中i、j間距離為D'，則合法的K必然是(D'+1)的因數（因為這里形成了一個環，環的長度為(D'+1)）。這樣一來就明顯縮小了K的取值范圍，再進行枚舉，就可以顯著縮短時間。

下面是一些極其猥瑣的特殊情況：
（1）根據題意，必須是K類每類都有，因此在嘗試編號成功（沒有發生任何矛盾）后，還要看一下實際出現的編號數目是否等于K，若小于K，同樣不合法；
（2）該圖的基圖可能不連通，此時對于其基圖的每個連通塊，其編號互不影響，所以要對每個連通塊分別統計實際出現的編號數目，設它們的和為SUM，則不大于SUM的K值均合法（只要中間不出現矛盾），因此可以直接得到最大值為SUM，提前結束；不過，這種特判只有在總共實際出現的編號數目小于K的情況下才能進行；
（3）由于考察的是實際出現的編號數目，因此最后求出的最大值、最小值可能小于3，這時應作出如下處理：若最大值小于3，則無解；若最小值小于3，則將最小值改為3。

本題比較猥瑣的數據是第4、5、6個點，分別出現了上述的第（1）、（2）、（3）種特殊情況，此外，這三個點建出的圖中竟然沒有一條跨越邊或逆向邊！

代碼：

     摘要: 【2-SAT問題】現有一個由N個布爾值組成的序列A，給出一些限制關系，比如A[x] AND A[y]=0、A[x] OR A[y] OR A[z]=1等，要確定A[0..N-1]的值，使得其滿足所有限制關系。這個稱為SAT問題，特別的，若每種限制關系中最多只對兩個元素進行限制，則稱為2-SAT問題。由于在2-SAT問題中，最多只對兩個元素進行限制，所以可能的限制關系共...  閱讀全文

多重背包問題樸素時間復雜度為O(NMS)（這里S是所有物品的數量s之和），經過二進制優化后時間復雜度為O(NMlog2S)，這個復雜度已經能夠應付大多數題了，但對于某些特別卡時間的題（比如N*M=10⁷的)，仍然會TLE。這時，可以用單調隊列優化，時間復雜度降為O(NM)。

首先看一下多重背包問題的樸素轉移方程：
F[i][j] = max{F[i-1][j-x*w[i]]+x*v[i]} (0<=x<=s[i], j>=x*w[i])
如果使用滾動數組，忽略i這一維，設w0=w[i]，v0=v[i]，s0=s[i]，得：
F[j] = max{F[j-x*w0]+x*v0} (0<=x<=s0, j>=x*w0)
看上去這和單調隊列木有神馬關系，因為決策下標（j-x*w0）不是一個整數區間，中間是有間隔的。然而可以發現，這個方程的限制條件“0<=x<=s0，j>=x*w0”，也就是x的下界是max{0, j/w0（下取整）}，當j單調遞增時，這個下界也是單調遞增的。這滿足單調隊列優化的條件中的“決策下標的下界單調”……不是，還不能這樣說，因為這里的決策下標是j-x*w0，而不是x。
那么怎樣才可以把決策下標變為x？

將決策下標按照模w0的余數進行分類，可以分成w0類，分別對應模w0余0、余1……余(w0-1)的情況。這時，上面方程中的所有決策下標j-x*w0都是同一類的。進一步，設q =j/w0（下取整），r=j%w0，則j=q*w0+r，對于某個決策下標j'，設k=(j'-r)/w0，即j'=k*w0+r。顯然可以發現，k的取值范圍是：k>=0且q-s0<=k<=q，也即k的下界是max{0, q-s0}——隨j的單調而單調。
然后，轉移方程可以改為（這里把r當成一個已知量了）：
F[q*w0+r] = max{F[k*w0+r]+(q-k)*v0} (k>=0且q-s0<=k<=q)
即F[q*w0+r]=max{F[k*w0+r]-k*v0}+q*v0 (k>=0且q-s0<=k<=q)
設G[k]=F[k*w0+r]得：
G[q]=max{G[k]-k*v0}+q*v0 (k>=0且q-s0<=k<=q)
這個方程已經可以使用單調隊列來優化了！

這樣可以得出算法：
（1）從1到n，枚舉i，建立w[i]個空的單調隊列，每個隊列的元素都是兩個int值：(k, val)，表示轉換后下標和決策值(G[k]-k*v[i])；
（2）從0到m，枚舉j，得出q、r的值，對于隊列r：
【1】刪去隊首過時（k<q-m[i]）的元素；
【2】F[j]入隊（這里的F[j]指上一階段的F[j]，即F[i-1][j]。因此這一步操作一定要先進行），刪去隊尾所有決策值val不大于(F[j]-q*v[i])的元素。
【3】取出隊首結點，其val值加上q*v[i]后即為本階段F[j]的值。
最后F[m]即為結果?？倳r間復雜度為O(NM)。

其實這個是可以推廣的，即對于如下形式的轉移方程（其中H、G和W均為常量，B[i]為決策下標的下界，隨i單調）：
F[i] = opt{F[i-x*H+W]}+G (B[i]<=i-x*H+W<i，x∈N）
都可以用上述的辦法進行轉化，從而進行單調隊列優化。

在沒有修改操作時，應用劃分樹可以在O(MlogN)時間內解決查找區間第K小的問題，但是在引入修改（將原序列中的某個值改為另一個值）之后，劃分樹就不行了。
這時，需要數據結構聯合的思想。
可以觀察一下：
（1）區間操作：使用線段樹；
（2）修改值（其實是先刪除再插入）和找第K?。菏褂闷胶鈽洌?br />現在這兩種操作都有，應該使用線段樹+平衡樹！
準確來說是線段樹套平衡樹，即對原序列建立一棵線段樹，其中的每個結點內套一棵對該結點管轄區間內的平衡樹。

<1>結點類型（結構）： 其中seg_node是線段樹結點類型，SBT_node是平衡樹(SBT)結點類型。需要注意的是seg_node里面的rt域（root的縮寫），它是該結點內套的平衡樹的根結點下標索引（因為對于任意一棵平衡樹，只要知道了其根結點就可以遍歷整棵樹）。

<2>建樹：
建樹是線段樹和平衡樹一起建。在建立線段樹結點的時候，先建立一棵空的平衡樹（rt域置0），然后再在平衡樹里面逐個插入該結點管轄區間內的所有元素即可；

<3>修改：
修改操作要注意：如果要將A[x]（A為原序列）的值修改為y，則需要自頂向下遍歷整棵線段樹，將所有包含了A[x]的結點內的平衡樹全部執行“刪除v=A[x]（這個可以通過真正維護一個序列得到），再插入y”的操作；

<4>找區間第K?。?br />這個操作極其麻煩。需要借助二分。
設要在區間[l, r]中找到第K小。首先將[l, r]拆分成若干個線段樹結點，然后二分一個值x，在這些結點的平衡樹中找到x的rank（這里的rank指平衡樹中有多少個值比x小，不需要加1），加起來，最后再加1，就是x在[l, r]中的總名次。問題是，設[l..r]中第K小的數為v1，第(K+1)小的數為v2（如果不存在的話，v2=+∞），則[v1, v2)內的數都是“第K小”的。因此，不能二分數字，而應該二分元素。設S[i]為原序列中第i小的數，二分i，然后在根結點的平衡樹中找到第i小的即為S[i]，再求其名次，這樣直到找到總名次為K的元素為止。問題還沒完，序列中可能有元素的值相同，這時可能永遠也找不到第K小的（比如序列1 2 3 3 3 4 5，K=4，若“序列中比x小的元素總數+1”為x的名次，則永遠也找不到第4小的），因此，若這樣求出的“名次”小于等于K，都應該將下一次的左邊界設為mid而不是(mid+1)，而“名次”大于K時，該元素肯定不是第K小的，所以下一次右邊界設為(mid-1)。

代碼（本機測最猥瑣數據4s以內，交到ZJU上TLE，不知為什么，神犇指點一下，3x）：