思路:宋文杰的题解很详细.一开始每个点30s,结果在OJ上一共30s...也就是说原来莫队是能过的,结果我无悬念TLE.莫队怎么做我就不说了.(貌似官方正解就是莫队...)莫队很暴力,因为没有利用一个题目中的性质:就是数据随机生成!询问随不随机意义是不大的.但是如果询问很特殊,我们就可以用科学的方法去处理:(1)任意两个区间不互相包含.这种情况我们将区间随便排个序就能发现总移动次数是\(O(n)\)的.(2)任意两个区间要么互相包含,要么不相交.这样就会形成一棵树.我们利用启发式合并,插入次数就为\(O(nlogn)\).但是随机数据显然没有这种性质.那么唯一可能有比较优秀的性质的就是随机数列了.考虑一种朴素算法:将所有询问离线按照右端点从小到大排序.从前向后依次加入右端点,令\(f_i\)表示当前以\(i\)为起点的后缀的答案,那么朴素来看,如果当前加入的是\(n\),那么\(f_1-f_{n-1}\)都需要更新.但是有很多冗余的更新.例如我们考虑所有大于\(a_n\)的数,不妨令\(a_i,a_j>a_n,a_i>a_j,i于是我们发现了某些单调性.我们利用数据结构维护后缀的答案,那么只需更新一些点就行了.那么我们的任务就是找到,对于\(n\)之前的数,一个均\(>a_n\)的递减序列,一个均\(然而由于是随机数据,序列中的元素个数是\(O(logn)\)级别的.这样总时间复杂
...
继续阅读
(428)