Inverse
这个 (dp) 分为四个部分
-
区间和 ([i,j]) 的端点没有交集，这时候答案是 (inom {i-1}2+inom {j-i-1}2+inom {n-j} 2)
-
区间包含左端点，也就是 (lle ile r< j)，此时吧 (l+r-i) 翻到了 (i)
也就是
设 (Sum(n,j)=sum_{i=1}^n f_{i,j},Tum=sum_{i=1}^n S_1(i,j))，前缀和优化得到
- 如果区间只包含右端点，从 (f_{i,l+r-j}) 转移到
这样设 (Sum_{i,n}=sum_{j=1}^n f_{i,j},Tum_{i,n}=sum_{j=1}^n Sum_{i,j})
得到式子甚至和上面的是对称的
- 区间整个包含
整个对对角线做一个类似的前缀和就行
所以就可以 (O(n^2k)) 计算这些贡献
Subsequence
(O(n^2) dp:) 设 (f_{i,j}) 表示前 (i) 个选 (j) 个，(f_{i,j}=max(f_{i-1,j},f_{i-1,j-1}+a_i imes j))
这部分是 (trivial) 的，考虑优化，其实这东西是有决策分界的
证明：设 (p(i, j) = frac{f(i,j)-f(i,j-1)}j)，所以当 (p(i-1, j) ≥ a_i) 时，(f(i, j) =f(i-1, j))，即选择前 (1) 种决策。
事实上当 (i) 定时，(p(i,j)) 随 (j) 增加而递减。这只要考虑转移时 (p(i,j)) 的变化：
那么如果 (p(i,j)) 是关于 (j) 递减的，那么 (p(i,j+1)) 也是单调的
所以用平衡树维护差分数组 (val[i]=f_{i,j}-f_{i,j-1})，每次二分到端点之后对右边区间加
Convex
-
凸包相关的点：
面积：任意选一个平面上的点 (x)，对于相邻的顶点 (a,b)，求 ((a-x) imes (b-x))
这题中选的点是 ((0,0))，方便维护前缀和
极角序：从原点开始的射线从 (x) 轴正半轴开始顺时针扫，扫到一个算一个，这样得到的点的序列
暴力是枚举每个对角线，对着 ((0,0)) 按照算面积，貌似要 (Theta(n^3))
剩下的还不会，先鸽着