ZCPC17th E Easy DP Problem
ZCPC17th E Easy DP Problem
Problem
由于这题前面的思维推到部分我没有参与,主要是现学(复习)了一下主席树,所以主要讲主席树的部分。
题目可转化为:
给一个长度为 \(n\) 的数组 \(a_i\),有 \(q\) 个询问,每次询问区间 \([l,r]\) 中最大的 \(k\) 个数之和,再加上 \(\sum_{i=1}^{r-l+1}i^2\)。
\(n\le10^5,q\le10^5,a_i\le10^6\)
\(T\le100,\sum n\le5\times10^5,\sum q\le5\times 10^5\)