day5遠(yuǎn)行珠寶矩陣

詢u，不妨令(A,B)為u所在塊中最遠(yuǎn)的兩個點(diǎn)，那么u的最遠(yuǎn)點(diǎn)必然是A或B，由于 可以直接求。對于加入(u,v)這條邊， 相當(dāng)于要出新聯(lián)O((N+Q)logN)。當(dāng)強(qiáng)制時，沒有辦法預(yù)處理出樹的倍增數(shù)組。那么事實(shí)上，在合并兩個塊時，可以采用啟發(fā)式合并，把小的合并到大的中去，比如說連接兩個點(diǎn)u,v，u所在塊比v的大，那么就以uvv的原來的O(logNO(Nlog2NQlogN) 離，這顯然可以用LCT來做，那么時間復(fù)雜度就變成了20%20%法，可以做到O(KC)，其中C為不同的費(fèi)用個數(shù)。100100對于費(fèi)用s，假如最終選了i個這樣的珠寶，那么然V[s][i]為排好序后的前綴和數(shù)組，那么假如要isV[s][i]。并且可以發(fā)現(xiàn)的是，總有V[s][i]V[s][i1]≥V[s][i1]V[s][i]，所以V[s]是一個上凸函數(shù)（斜率單調(diào)不升。scsms,?isF[s][i]

{F[s?1][i?sj]+siimods的值分類，對于每一類分開來做。jiimodsjx=i?j，把xF[s1][i]變成平面上的一個點(diǎn)，即(x,F[s1][i])，sF[s1][iY[x]kx，iF[s][ksj]的貢獻(xiàn)就是V[s][k?x]+Y[x]。考慮兩個點(diǎn)G[x],G[x1]，滿足x<x1， 些k≥x1，會有x1的貢獻(xiàn)比x大，就相當(dāng)于V[s][k?x1]+Y[x1]>V[s][k?x]+Y[x1]?Y[x]>V[s][k?x]?V[s][k?Y[x1]?x1?

>V[s][k?x]?V[s][k?x1?V[s][k?x]?V[s][k? (k?x)?(k?tktk，x1x大兩者 先枚舉模數(shù)j，然后從小到大處理k。一個轉(zhuǎn)移隊(duì)列，隊(duì)列中每個點(diǎn)都對應(yīng)著k的某個區(qū)間的最優(yōu)決策。k變大時，把開頭不合法或k已經(jīng)不在最優(yōu)決策內(nèi)的點(diǎn)刪去，然后加入一個新點(diǎn)(k,F[s?1][ks+j])，令為P點(diǎn)，設(shè)隊(duì)列末尾的點(diǎn)為Q,F，Q,F的決策分界點(diǎn)為t1，F(xiàn),P的決策分界點(diǎn)為t2，假t2≤t1，那么相當(dāng)于F是無用狀態(tài)，直接把F刪掉，不斷進(jìn)行即可。對于求決策分界點(diǎn)， 用二分來求。這樣總的時間復(fù)雜度就是O(NlogN+CKlogK)。度為O(22n2n3) C= ··· A ·· CABABC01矩陣，因此對于每個CjAk來異或得到的，而他們的系數(shù)恰好就是Bk,j。所以枚舉矩陣A，求出A的秩r，判斷對于每個CjAjB的數(shù)量就恰好為(2N?r)N個。對于消元部分可以用bitset壓位。ωω所以枚舉矩陣A，求出A的秩r，判斷對于每個CjAjB的數(shù)量就恰好為(2N?r)N個。對于消元部分可以用bitset壓位。ωO(2n2n3)ω以及C的秩有關(guān)，因此可以打表，這樣直接就O(1)啦。6060嘗試用Dp來解決掉30分中的。不妨設(shè)r為C的秩，F(xiàn)[i][j][k]表示當(dāng)前確定到Ai，對于現(xiàn)在這個Ni的矩陣A′，CjA′的線性空間中，A′kC的線性空間中，A′的個數(shù)。那么最終答案就是Ans j2r+kj2r+kj不變，kj2r+kj不變，k 得到了一個狀態(tài)數(shù)為O(N3)轉(zhuǎn)移O(1)的Dp，總的時空復(fù)雜度就是O(N3)。30分的做法可以知道，對于所有秩相同的矩陣NNC，他們的答案都是相同的，因此，不妨rCC的對于一個秩為x,x>=r的矩陣A，首先他的貢獻(xiàn)是2N(N?x)，那么接下來就是考慮有多少個秩為r的矩陣C，滿足C中的列向量全在A的線性空