codeforces 12D Ball

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

这道题有两种做法一种用树状数组/线段树维护区间最值，一种用map维护折线，昨天我刚遇见了一道类似的用STL维护折线的题目：
392D Three Arrays
参考题解：http://blog.csdn.net/rzo_kqp_orz/article/details/70666174
参考代码：http://codeforces.com/contest/392/submission/8930531

现在来谈谈这道题：

(借一下另一题题解的图)
假设现在图中有一些点，那么对于每个点，它会使在它左下角的点自杀。显然，如果有点出现在折线左下角都会自杀。所以这道题本质就是要判断当前点在折线的哪一侧，以及更新折线。