csp-s102 T1 你相信引力吗

先考虑没有相同数的情况,那么每个点会和左边第一个比它大的和右边第一个比它大的造成1的贡献,此后再无贡献

因为没有相同数所以一对数一定有一个大的有一个小的对于小的来说另一个端点再移动的话就一定不会危险 所以是对的

由于有环,考虑拆掉,正常的方法是在最后一个之后把串重复一遍

然后就会想到单调队列(/栈)

但去重很恶心由于拆环导致一个数左边和右边找到的可能一样,也可能一对数前边算了一次后边算了一次

一种方法是对每个数记录一下左边和右边的数是哪个,,,,,

但细节巨多  而且会走上一条解决不了有相同数的不归路

把有相同数的情况考虑进来:每个数不仅会和左边第一个,右边第一个比它打的构成贡献而且和每个和它相等的数(   可能  )会造成额外的贡献因为端点继续移动没有影响

重复的情况更恶心了

考虑如何避免重复:从找到的性质入手,第一个比它大的,此时移动不了了。

那么考虑拆环时把最大的放在最后一个,那么不会有跨过它的贡献

前边即可用单调栈

考虑后边的:只会和最大的那个可能构成贡献

有贡献的前提就是在前面这一对没有算,中间有更大的,但换成另外一个弧(从后边)是合法的

用到了次大值,在次大值之后的由于次大值的阻挡从后边不能合法, 在它之前的由于次大值的阻挡在前边不能合法

显然只有次大值之前的可能造成新贡献,只要满足从最后一个往后扫到次大值之前的元素,同时记录最大值变量检验合法性,统计贡献,到次大值后break即可

考虑有相同数的情况:在前边:单调栈解决记录权值   遇到相等的  干掉但继承权值算贡献

贡献在于所有在栈中遇到的相等元素互相构成贡献,所有相等元素和第一个左边大的右边大的构成贡献

后边不会有相同数的贡献因为有的话 假如不是最大值那么在前边算过  是最大值的话在前边也算过(相当与一个次大值)。

总结:特殊拆环(看题目性质最大最小值放后边加以限制)

    利用性质解决问题

    次大值和最大值,次小值和最小值的关系运用

原文地址:https://www.cnblogs.com/three-D/p/11803105.html