T1

problem

[NOIP2016]蚯蚓

ans

我们可以观察到,对于两条蚯蚓,他们切开后对应段的长度顺序和切之前一样.所以我们按照长度顺序从大到小排序,然后维护三个队列.分别放完整的蚯蚓,切完后的一段和另一段.这样能够保证单调性.然后每次取出最大的队头处理.至于长度的增加,每条蚯蚓设置一个时间戳即可.

T2

problem

有$n$块石头围成一个环,第$i$块石头高度为$a[i]$,两块不同的石头$i,j$互相能够看到当且仅当他们在环上的两条路径中至少有一条路径满足除了这两个点以外其他石头的高度都不大于$min(a[i],a[j])$.求有多少对石头能互相看到.

ans

我们仔细观察可以发现一条性质:如果我们找到了最大值所在的位置,那么其他任何$i,j$都不会选择经过最大值的这条弧.所以我们直接删掉这个最大值,问题就变成了链.

两个点能互相看到的条件是对于两个点$i<j,i$右边到$j$为止都没有比$i$大的,$j$左边到$i$为止都没有比$j$大的.所以我们设置两个数组$left$和$right$.表示左边或者右边第一个比当前大的值的位置.那么如果$right[a[i]]>j,left[a[j]]<i,i$和$j$就能看到这可以通过单调栈在$\Theta(n)$时间内解决.还有一种特殊情况是$a[i]=a[j]$,这时候我们对于栈的元素不再记录石头的编号和高度,而是记录高度以及石头个数.也就是当$a[i]=a[x]$时,我们不让$i$入栈,而让$tot[top]++$,其中$tot[top]$为$top$位置的石头有多少个.这样,每次出现这种情况,直接给答案加上$tot[top]-1$即可.

T3

problem

有n个城市和m调公路,每条公路的价格是ci,有q次询问,每次询问在只用[l,r]编号的公路,在连通块数量尽量少的情况下,花费最少多少.

ans

——Gensokyo