牛相遇后必须再分离后才能再打招呼。。。

一种类似离散化的思想，避免遍历对结果没有贡献的信息。
可以二分优化。

用堆优化的迪杰斯特拉写的。。
对任意2节点求单元最短路。把结果存到系统红黑树map里(这样保证内存不会爆)。
然后对应每条询问输出结果即可。
但是为何伤心的T了7组

好多DP都是可以用线段树写的。
一种简单容易看出的DP(可以直接以区间建树)有以下特点：
1.子问题数量少(太多的话会把一个节点建的巨复杂)(这种情况下还是交给cstdio大神来建一些高大上的树)
甚至可以写成O(n)的地推。子问题处理到该问题的状态转移更一般形式的方程就是子节点计算父节点的运算法则。
2.相关子问题不要调用相邻很远的节点的值，譬如石子归并。不过话说区间DP还是可以套线段树的。要不然再套一颗建立与其他节点之间的联系。要不按照子问题建树而非区间。(这是的时间复杂度就不是以区间长度为准的了)
更多的研究还有待寡人继续学习,或咨询@cstdio 和线段树导师@digital-T
不过也不至于又让我用32min的单指敲键盘敲得内存和时间压制你们吧

用AVL树写的。。竟然还是TTTTT
主要是数据太大。而且分布相当集中。。
所以还是用splay吧。。用set(红黑树)也会超时＝＝

有一个浪漫的童话故事：一位英俊帅气万人迷的王子因为天资过高被巫婆诅咒，诅咒他永远无法自己独立不用stl写出一个n(lgn)的排序。。但是，2年多后，王子遇到了一个可爱漂亮的公主，他们相恋了。然后王子的归并排序就过了。。。
果断又交上，sort，qsort，手打2分快排，手打随机化快排，优先队列Priority_Queue。。
后来，公主发现王子是弯的。。。

每次都会内存压制全场
0.27 MB

发现Scanf与Cin的效率差太大

第二问最上升子序列

如图所示，如何统计不相交下降序列(元素不相交)的个数呢。
我们只需从最靠左下的序列出发，可知，若要找下一个上升元素，不可能存在于改元素所在的不上升序列中。
故最长上升序列就为不上升序列的个数。

回复 @CSY.Girl_Queen :
对于一个问题而言，存在某种贪心策略可得到局部最优解。
但是若证明该贪心策略所得到的局部最优解亦是全局最优解仍需严格的证明过程。
在这里，我误认为三集合就可以表示所有的状态，但是存在以下问题：
1。集合$ABC$都代表着在全局中始终为最优解的集合。却无法确定集合的合并方式。
2.无法确定先选取哪个集合为B进行合并$(A(BCD)),((ABC)D)$

我们都知道这是一道很基础的DP。
$F$为所需求的状态值，在石子归并问题中理解为权重。$W$为物品重量，$φ$为与参数(状态$K$)相关的状态转移权重。
$F(A)=Min(F(A-K)+φ(K))$类型的动归(A,K表状态集合，在石子归并问题中我们使它内部元素有序)。
在石子归并问题中，我们认为$φ(K)=W(A)+W(A-K)$
可是，如何证明它不可以使用贪心算法呢？
假设有序集合$A,B,C$表示不同的状态。终止状态为$(ABC)$初始价值(状态)则为$Ω(INIT)=F(A)+F(B)+F(C)$
策略1$F(ABC)=W(A)+W(B)+W(AB)+W(ABC)+Ω(INIT)$
策略2$F(ABC)=W(B)+W(C)+W(BC)+W(ABC)+Ω(INIT)$
两式比较取差异部分：
策略1$δ(ABC)=2W(A)$
策略2$δ(ABC)=2W(C)$
此时的可以看出在初末状态相同时，策略1与策略2有明显的优劣。我们只需修改$ABC$集合代表的状态（只需保证其始终为有序态即可），既可以得到全局最优解

设集合 $n=i+j+k;F(n)$表示对集合n的权值（即果子重量）， $Fruit(n)$为体力耗费。
决策1$Fruit(n)=F(k)+F(i)+F(k)+F(i)+F(j)$;//先合并i，再合并j。
决策2$Fruit(n)=F(k)+F(j)+F(k)+F(i)+F(j)$;//先合并j，在合并i。
2种方式对比会发现仅含不同项F(i),F(j),只许比较i，j大小选取小的先合并便可保证从某一相同初始状态转换至相同末状态的花费最小。

想必看完楼上们的评论，大家对这道题的算法已经饥渴难耐了，为了满足大家的兽欲，这里我给出一个简易版的证明(没有按照严格的贪心算法的证明方法走)。
设K为某种状态下的常数，其大小与巧克力当前状态下x，y方向上的块数大小有关。
情况1设$X_{n},X_{n+1}$为相邻位(n+1为n的第一个小于的元素)，$W_{n}$为切完第n刀后的权值和。
可知切2刀之前状态与切2到之后的状态相同，与中间决策无关。
决策1$W_{n,first}=W_{n-1}+K*(X_{n}+X_{n+1})$
决策2$W_{n,second}=W_{n-1}+K*(X_{n+1}+X{n})$
$W_{n,first}=W_{n,second}$;这种情况下两种决策效果相同。
情况2设$X_{n},Y_{m}$为相邻位(定义同上，但在这可以假设2大小关系未知)，$W_{n}$为切完第n刀后的权值和。
可知切2刀之前状态与切2到之后的状态相同，与中间决策无关。
决策1$W_{n,first}=W_{n-1}+K*(X_{n}+2*Y_{m})$等式1
决策2$W_{n,second}=W_{n-1}+K*(Y_{m}+2*X{n})$等式2
等式1与等式2同时减去相同部分得
$First=K*Y_{m}$等式3
$Second=K*X_{n}$等式4
此时可知W值与决策有关，既若使某状态下W值越小，则应先从大的切起。
对于全局的决策，可以分为数个阶段，在这里可以证明：
若$W_{n}$最优，则$W_{n-1}$最优(反证法：由于决策过程权值是确定的，若存在更优$W_{n-1}$，则$W_{n}$不为最优，与前提矛盾)
$W_{n-1}$最优且使用最优决策，则$W_{n}$最优。
由此可递推得最终可以获得最优答案(可以用类似循环不变量的东西，这个比较开放了~)
最终得到巧克力问题满足局部最优解亦是全局最优解，该贪心算法成立。
看来2楼的贪心算法大部分还是正确的，除了少量细节（情况一），不过我们是真男人，何必在意这些细节!

哪位仁兄能提供一下历年的分数线

TMD。此等错误题目描述如此坑爹。。我换了个题库才看懂！！@闫星光

<p></p>

警告这道题不建议用海伦公式。
海伦公式中有乘法和开方运算
$ S=\sqrt{p(p-a)(p-b)(p-c)} $，要小心浮点误差。

奇偶判断少不了。
这道题输入数据比较大，所以评测机可能会有些慢，请耐心等待。

分成3种情况讨论。x轴方向，y轴方向，对角线的方向。(使n<m)
$num(x)=n*(n-1)*m;$
$num(y)=m*(m-1)*n;$
$num(x+-y=0)$
$=2*n*(m-n+1)*(n-1)+\sum_{i=1}^{n} {i(i-1)} $
$= \sum_{i=1}^{n} {i^2}-\sum_{i=1}^{n} {i} + 2*n*(m-n+1)*(n-1) $
$\sum_{i=1}^{n} {i^2}=\frac{(n+1)(2n+1)n}{6}$
$\sum_{i=1}^{n} {i}=\frac{n(n+1)}{2}$
最终化简得
$num(x+-y=0)=$
$2*n*(m-n+1)*(n-1)+\frac{(n+1)(2n+4)n}{3} $
Ans=num(x)+num(y)+num(x+-y=0)
警告PS:输入输出真心只有1组数据，且没有字符串。