冰

注意到原问题等价于{1,3,7,15,31,...}的无限背包 暴力跑背包即可

证明：

令$a_1=v_1,a_2=v_2-2v_1,a_3=v_3-2v_2,...,a_m=v_m-2v_{m-1}$

带入得 $(2^m-1)a_1+...+3a_{m-1}+a_m=n$

其中 $a_1\ge 1$ $a_2,a_3,...,a_m\ge 0$

所以是一个{1,3,7,15,31,...}的无限背包

时间复杂度O(nlogn)

光

对时间建线段树 套线性基

对于每个光源 把它所有存在的时间放到线段树上 注意一直开到最后的光源也要加进去

这样一共是nlogn块存在时间

然后按dfs序遍历线段树来计算答案

进入一个节点的时候 复制当前的线性基 然后用节点中的光源更新线性基

如果到了底层就计算该节点的所有询问

退出一个节点的时候 用备份的线性基恢复原来的线性基

时间复杂度O(nlog^2n)

还有一个O(nlogn)的更优做法

维护一个动态线性基 优先程度为此数的删除时间

删除时间越靠后 优先级越高

删除的时候直接把那一位变成0即可

为了更清楚的理解这个O(nlogn)做法 你可以看这份代码 http://acm.nflsoj.com/submission/5980

影

B和C的贡献是确定的

用费用流计算A的贡献

对每个(i,j) 建一个点 连到t一个流量1费用0的边

如果f(i,j)=1 j向(i,j) 连到一个流量1费用0的边

如果f(i,j)=-1 i向(i,j) 连到一个流量1费用0的边

如果f(i,j)=0 i j各向(i,j) 连到一个流量1费用0的边

s向1-n每个点连n条边 流量都是1 费用都是{A,3A,5A,7A,...}

这样 任何一对(i,j) i和j中恰好一个的出现次数+1

而对i来说 出现k次费用刚好是Ak^2

时间复杂度O(费用流)