码迷,mamicode.com
首页 > 其他好文 > 详细

CF5E Bindian Signalizing

时间:2019-10-10 00:24:50      浏览:28      评论:0      收藏:0      [点我收藏+]

标签:若干   请求   若何   地位   nal   article   影响   nbsp   端点   


推敲若何使环变成一条链,等价于 :环中的两点之间假设包含了链的左端点,则这两点必定不克不及相互看到

所以只需包管链的左端点高度最高便可。

关于有若干个最高的山也不会影响。由于两个最高点之间随便任性偏向的弧形都满足条件。

设l[i]表示i左边第一个比i高的地位,r[i]表示i左边第一个比i高的地位,cnt[i]表示在i到r[i]的左开右闭区间内高度等于i的山的数量

随便任性符合请求的两点只会算一次。所以规定符合请求的两点的供献计于靠左且高度较小的点上。

推敲一个点 i 的供献。由于在 i 左边第一个高度大年夜于 i 的点j后的点弗成能 与i配对。所以只需统计 i — j 区间还有若干个与 i 高度相等的点便可

然则当符合请求的两点的靠左的点高度较大年夜时 即 点(i, l[i]) 与 点 (i ,r[i])并没有推敲,在每个点统计答案时加 2 便可

然则当 l[i]=0 且 r[i]=n 时, (i, l[i]),(i ,r[i])实际上是一组

CF5E Bindian Signalizing

标签:若干   请求   若何   地位   nal   article   影响   nbsp   端点   

原文地址:https://www.cnblogs.com/Go-and-Fight/p/11645133.html

(0)
(0)
   
告发
评论 一句话评论(0
登录后才能评论!
© 2014 mamicode.com 版权一切 京ICP备13008772号-2
迷上了代码!