T1
拆式子然后主席树维护即可
T2
这题目考试的时候涨的教训
(1,dp) 数组记得维护负下标
(2.1^3+2^3+3^3+dots n^3=(sum_{i=1}^n i)^2)
首先有费用流做法
源点向两个表示干脆面和豆干的点建流量为 (a/b) 的边
然后每个点向猫连上费用为 (p_i/q_i) 的边，流量为 (1)
然后考虑那个 (-p_i imes q_i) 的问题，就直接向汇点链接 ((1,0)/(1,-p_i imes q_i)) 的边即可
觉得收获确实很大
然后是二次 (wqs) 二分的做法
这里注意的是斜率只能是 ([0,1])，同时剪掉代价的时候 (-p_i imes q_i) 并不需要多加个 (c_a imes c_b)
最后算答案的时候直接再做一次就行