Description 给出一个序列a&#xff0c;你需要求出一个0/1序列c&#xff0c;使得 ∑i1n∑jin∏kijCk−∑i1nCiAi最大 给出m次修改形如(x,y)&#xff0c;表示把a[x]改成y&#xff0c;每次修改之间独立&#xff0c;对于每次修改之后求出答案n,m<3*1e5 Solution 首先一次询…

1D1D动态规划是指状态数为O(n)&#xff0c;每个状态的决策数为O(n)&#xff0c;直接求解的复杂度为O(n^2)的动态规划方程。但这种方程往往都能够通过一些合理的组织和决策优化到O(n log n)甚至O(n)的。 由于博主比较弱所以只分析下面几种情况&#xff08;其他的等会了有时间再…

https://www.luogu.com.cn/problem/P6246 决策单调性 若 d p i dp_i dpi​ 由 j j j 转移&#xff0c;则 d p i 1 dp_{i1} dpi1​ 转移点 k k k 满足 k ≥ j k\ge j k≥j 发现决策点满足单调&#xff0c;但遍历的点不满足单调&#xff0c;不能用双指针&#xff0c;考虑…