Done
QOJ #970 Best Subsequence $ _{6.3}$
定义 \(f(\{a\},k)\) 为最小的 x 使得存在一个 \(a\) 的长度为 \(k\) 的子序列首尾相接以后每两个相邻向之和均 \(\le x\)。
给定数组 \(a\) 和 \(q\) 组询问，每组询问给定 \(l,r,k\)，需要求出 \(f(a[l:r],k)\)。
\(1\le n,q\le 10^5,1\le a_i\le 10^9\)。4s 1GB。
View solution
QOJ #6101 Ring Road $ _{6.7}$
给定一棵 \(n\) 个点、以 \(1\) 为根的树，边有边权。保证点编号为一个 \(\text{dfn}\) 序。保证根的度数 \(\ge 2\)。
树上还有一些附加边，具体地，这些边会按 \(\text{dfn}\) 序将所有叶子节点连起来。
询问 \(q\) 个点对之间的最短路。\(1\le n\le 10^5,1\le q\le 2.5\times 10^5,1\le w\le 10^12\)，4s 1GB。
View solution
QOJ #3998 The Profiteer $ _{6.5}$
给定长度为 \(n\) 的数组 \(v,a,b\) 和整数 \(k,E\)。保证对于每个 \(1\le i\le n\) 都有 \(a_i<b_i\)。
设 \(f(x,\{w\},\{v\})\)（\(|w|=|v|=m\)）为对价值为 \(w\)，重量为 \(v\) 的 \(m\) 个物品做容量为 \(x\) 的背包问题所得到的最大价值。
求有多少个区间 \([l,r]\) 使得将下标在 \([l,r]\) 之间的 \(a_i\) 全部替换为 \(b_i\) 后 \(\frac 1k \sum\limits_{i=1}^k f(i,a',v)\le E\)。
\(1\le n,k\le 2\times 10^5,nk\le 10^7,1\le E\le 10^9,1\le v_i\le 10^4,1\le a_i<b_i\le k\)。1s，512MB。