T1 United Cows of Farmer John

algorithm: segtree

一道非常神奇的数据结构题。

考虑枚举每个区间的右端点，设当前点为 \(i\)，值为 \(v_i\)，上一个 \(v_i\) 的位置为 \(pre_i\)。

显然，左端点只能在 \((pre_i,i-1]\) 这个范围内。

当我们加入点 \(i\)，那么 \((pre_i,i-1]\) 中左端点的方案数均可以加 \(1\)，线段树维护即可。

但有一个问题，左端点不一定是连续的，所以我们再维护一个 \(0/1\) 的系数，表示这个点能否作为左端点。

T2 Permutation

algorithm: dp

考虑答案的图应该长什么样子：

首先有一个三角形，每次选择一个点，分类讨论：

  1. 在三角形内，图还是一个三角形。
  2. 在三角形外，它会与原三角形的两个顶点构成一个新的三角形。

就两种情况，我们可以用动态规划来解决。

设 \(dp_{p,i,j,k}\) 为当前已经计算了 \(i\) 个点，答案为 \(i,j,k\) 三个顶点构成的三角形。

  1. 内部转移，相当于把 \(l\) 取出后，在 \(i,j,k\) 中随便选一个点，预处理三角形内部的点的数目即可。

    格外注意，预处理时请用标准的计算几何方法，不要用什么三角形面积相加等于大三角形,sqrt 精度不够。

  2. 外部转移，枚举三角形内部的一个点，假设上一个三角形是这个点与原来的两个点构成的，这时直接加上上一个三角形的答案。

注意long long。

T3 中位数（middle）

algorithm: PST,binary

考虑把小于 \(mid\) 的权值设为 -1，其他设为 1。

问题就变成询问区间和大于等于 \(0\)，把区间拆成 \([l1,r1),[r1,l2],(l2,r2]\) 三个区间，分别处理区间和，最大前缀和，最大后缀和。

再发现本质不同的区间只有 \(n\) 个，用主席树维护，每次二分答案即可。

T4 破烂森林（garakuta）

暂缺