分治

P4755

一道神奇的题

本来想了个\(\Theta(nlogn)\)的算法，结果只得了20pts

想法是：对于每个单调递增的序列，对内的答案贡献为所有1乘以1后面的那段长度；对外用主席树维护，最大值永远为序列最后一个数

hack：

6

1 3 9 3 12 4

没有考虑到后面更大的数对答案的影响

正解：

启发式枚举

考虑分治.对于每个区间[l,r],用st表\(\Theta(1)\)找出最大值及其位置；

随后分类递归(l,m),(m+1,r)或(l,m-1),(m,r)

最后统计自己的答案.

对于两段子区间，永远启发式地枚举小区间，这样的目的是将总枚举次数均摊为\(\Theta(nlogn)\)，加上主席树的\(\Theta(logn)\)应该为\(\Theta(nlog^2n)\).

每次枚举的树的贡献为大区间中<=\(\frac {maxn}{a[i]}\)的数的个数，用主席树维护.

枚举小区间的正确性： 因为大区间永远用主席树，所以复杂度为\(\Theta(logn)\)；分治共有\(\log n\)层，每层小区间加在一起最坏情况为\(\frac{n}{2}\)长度，因此总复杂度为\(\Theta(nlogn)\)