day5远行珠宝矩阵

询u，不妨令(A,B)为u所在块中最远的两个点，那么u的最远点必然是A或B，由于 可以直接求。对于加入(u,v)这条边， 相当于要出新联O((N+Q)logN)。当强制时，没有办法预处理出树的倍增数组。那么事实上，在合并两个块时，可以采用启发式合并，把小的合并到大的中去，比如说连接两个点u,v，u所在块比v的大，那么就以uvv的原来的O(logNO(Nlog2NQlogN) 离，这显然可以用LCT来做，那么时间复杂度就变成了20%20%法，可以做到O(KC)，其中C为不同的费用个数。100100对于费用s，假如最终选了i个这样的珠宝，那么然V[s][i]为排好序后的前缀和数组，那么假如要isV[s][i]。并且可以发现的是，总有V[s][i]V[s][i1]≥V[s][i1]V[s][i]，所以V[s]是一个上凸函数（斜率单调不升。scsms,⌊isF[s][i]

{F[s−1][i−sj]+siimods的值分类，对于每一类分开来做。jiimodsjx=i−j，把xF[s1][i]变成平面上的一个点，即(x,F[s1][i])，sF[s1][iY[x]kx，iF[s][ksj]的贡献就是V[s][k−x]+Y[x]。考虑两个点G[x],G[x1]，满足x<x1， 些k≥x1，会有x1的贡献比x大，就相当于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大两者 先枚举模数j，然后从小到大处理k。一个转移队列，队列中每个点都对应着k的某个区间的最优决策。k变大时，把开头不合法或k已经不在最优决策内的点删去，然后加入一个新点(k,F[s−1][ks+j])，令为P点，设队列末尾的点为Q,F，Q,F的决策分界点为t1，F,P的决策分界点为t2，假t2≤t1，那么相当于F是无用状态，直接把F删掉，不断进行即可。对于求决策分界点， 用二分来求。这样总的时间复杂度就是O(NlogN+CKlogK)。度为O(22n2n3) C= ··· A ·· CABABC01矩阵，因此对于每个CjAk来异或得到的，而他们的系数恰好就是Bk,j。所以枚举矩阵A，求出A的秩r，判断对于每个CjAjB的数量就恰好为(2N−r)N个。对于消元部分可以用bitset压位。ωω所以枚举矩阵A，求出A的秩r，判断对于每个CjAjB的数量就恰好为(2N−r)N个。对于消元部分可以用bitset压位。ωO(2n2n3)ω以及C的秩有关，因此可以打表，这样直接就O(1)啦。6060尝试用Dp来解决掉30分中的。不妨设r为C的秩，F[i][j][k]表示当前确定到Ai，对于现在这个Ni的矩阵A′，CjA′的线性空间中，A′kC的线性空间中，A′的个数。那么最终答案就是Ans j2r+kj2r+kj不变，kj2r+kj不变，k 得到了一个状态数为O(N3)转移O(1)的Dp，总的时空复杂度就是O(N3)。30分的做法可以知道，对于所有秩相同的矩阵NNC，他们的答案都是相同的，因此，不妨rCC的对于一个秩为x,x>=r的矩阵A，首先他的贡献是2N(N−x)，那么接下来就是考虑有多少个秩为r的矩阵C，满足C中的列向量全在A的线性空