P8572 [JRKSJ R6] Eltaw
观察到了一个诡异的复杂度：\(1\le n\times k\le5\mathrm{e}5\)，然后就知道……其实也不知道。
但是这个题的暴力非常好打。先用前缀和维护出来，然后暴力统计即可。
考虑优化，这是个静态的，我查的区间最多是 \(O(n^2)\) 的，所以我可以把每次查询的答案记下来，如果有重复直接输出原来查过的就行。
然后就是设 \(s=n\times k\)，显然 \(s\le5\mathrm{e}5\)，也显然 \(n\) 和 \(k\) 一定有一个 \(<\sqrt{s}\)。
-
\(n<\sqrt{s}\)
显然区间个数 \(n^2\) 与 \(s\) 同级。对于每个区间的复杂度是 \(O(k)\)。总复杂度是 \(O(n^2k)\)，即 \(O(s\sqrt{s})\)。
-
\(k<\sqrt{s}\)
如果不考虑有重复，那么也就是最坏情况，每次询问的复杂度都是 \(O(k)\)，总的也就是 \(O(qk)\)，即 \(O(q\sqrt{s})\)。
P3810 【模板】三维偏序（陌上花开）
挺模板的。我那天学 CDQ 来着，就用 CDQ 做了。
注意到了 \(j\ne i\)，也就是说没有规定顺序，就可以排序了，那么三维偏序也就变成二维偏序了。
钦定整个序列关于 \(a\) 单调递增……等等，有个问题，它要的是 \(\le\)，也就是说所有相等的点对可以互相贡献，但是我们现在钦定的偏序关系是 \(<\)，也就是说这样算会少算的（少算的是相等的互相贡献的那部分）。所以要去重（\(a,b,c\) 都相等才可以去重），然后就可以做了。
现在整个序列变成了关于 \(a\) 单调递增的。这种点对问题用 CDQ 比较好想？比如要找 \([l,r]\)，现在有一个 \(mid\)，分成两部分 \([l,mid]\) 和 \([mid+1,r]\)。这两部分递归处理，然后就是嗯嗯嗯（不太会说但是知道是那个意思就不说了）。显然分成的这两部分也不需要考虑 \(a\) 的，因为从这两部分各取一个点显然能保证 \(a\) 的有序。所以先给这两部分分别关于 \(b\) 排序，双指针扫一遍，用树状数组维护（类似树状数组求逆序对的写法）即可。
ABC326E - Revenge of "The Salary of AtCoder Inc."
小清新概率 dp 题。（好久没做概率了，感觉做这个题有些乏力）
分析一下可知这是要求每个数被选的概率，如果要求 \(k\) 被选的概率，显然有：
\[p_k=\operatorname{inv}_n\times\sum\limits_{i=0}^{k-1}p_i. \]这里钦定 \(p_0=1\)。
所以转化一下就是：
\[p_k=\sum\limits_{i=1}^k(\operatorname{inv}_n)^i. \]所以有答案：
\[ans=\sum\limits_{i=1}^na_i\times p_i. \] 标签：偏序,limits,复杂度,mid,狗屁不通,times,sum From： https://www.cnblogs.com/voah/p/17795452.html