czy
bzoj5424燒橋計劃
f[i][j]暴力，可以分兩段轉移，更近的一段單調隊列
發現，最多分成sqrt(n)段。
因為如果只有一段，ans=n*2000
而如果多段，至少是∑i*1000，那么，i的上界是sqrt(n)級別的。
所以，O(nsqrt(n))
（什么題啊）
?
ywy
CF1086F?Forest Fires?
考慮統計f[i]，i時刻能覆蓋的個數
ans=t*f[t]-∑f[i]
∑f[i]矩形面積并，插值
?
yjc
https://codeforces.com/problemset/problem/1172/C2?tdsourcetag=s_pcqq_aiomsg
f[w][i][j][k]大暴力
k可以省去，f[w][i][j]，j，i可以砍到m
有結論：f[w][i][j]=w*f[1][i][j]
關于輪數i，進行歸納法可以證明，i=0顯然成立，求出i>=1時f[1][i][j]的式子，對比f[w][i][j]的式子，發現f[w][i][j]=w*f[1][j][k]，
得證。
?
zky
51nod1584 加權約數和
沒出太大的鍋，但是線性篩好像做不了了。
?
zrq
P4566?[CTSC2018]青蕈領主
類析合樹
然后把兒子縮點，推式子，cdq分治FFT
?
ztb
?
PKUSC2019 D2T2
zzh
n個人，每個人手上有?a_i??個相同物品，兩人的物品不同，有先后m次交換，每個x和y可以交換一件物品（可以不交換），最大化最終1手上的物品種類。n≤3000
m,n,xi,yi,ai給定
?
首先，每個人手上的ai個等于1個。最終目標是給1，只算一種，讓那條路徑給過去即可。所以多了沒用。
ai的作用是限制第i個人手上同時最多ai個。
然后網絡流：
對時間拆點，n*m個點，
如果(x,y)在t時刻交換，則$(x_t)->(y_{t+1})$,$(y_t)->(x_{t+1})$流量為1
任意t，$(i_t)->(i_{t+1})$流量ai
S到$(i_t)$流量1，表示一種物品
$(1_m)$到T流量inf，表示最終種類數。
?
n*m個點只保留有用的即可。
最大流。
?
如果$(x_t)->(y_{t+1})$流過去，代表：“決定把某個種類最終傳給1”，所以把這個“種類”傳過去。
（某一時刻，x的$(x_t)->(x_{t+1})$沒有滿流，代表手上還有一些x號物品（初始的），
此處，如果沒有同時的$(y_t)->(x_{t+1})$，其實代表x交換給了y一個x的初始元素過去，
由于并不想到達1，所以沒有把“種類”傳過去。
）
?
1和種類有關，所以就是種類代表點了。即1點流量。
?
)
)
)
![[HDU517] 小奇的集合](http://pic.xiahunao.cn/[HDU517] 小奇的集合)
