随机数据

洛谷题库 P8868 [NOIP2022] 比赛

本文记号可能稍显凌乱,但都能在题面或者前文中找到定义。

部分分

20 pts\text{20 pts}n,Q3000n,Q\leq 3000

考虑枚举所有 O(n2)\newcommand\bigO{\operatorname{O}}\bigO(n^2) 个区间,预先计算它们本身的答案。记 ga(l,r)={max{ailir},(1lrn)0otherwisegb(l,r)={max{bilir},(1lrn)0otherwise\begin{aligned}g_a(l,r)&=\begin{cases}\max\{a_i\mid l\leq i\leq r\},&(1\leq l\leq r\leq n)\\0&\text{otherwise}\end{cases}\\g_b(l,r)&=\begin{cases}\max\{b_i\mid l\leq i\leq r\},&(1\leq l\leq r\leq n)\\0&\text{otherwise}\end{cases}\end{aligned} 则做前缀和 s(l,r)=i=lrga(l,i)gb(l,i)s(l,r)=\sum_{i=l}^{r}g_a(l,i)g_b(l,i),对于询问 [ql,qr][\text{ql},\text{qr}] 只需回答 i=qlqrs(i,qr)\sum_{i=\text{ql}}^{\text{qr}}s(i,\text{qr}) 即可。

n,Qn, Q 同阶,时空复杂度 O(n2)\bigO(n^2)(更多…)

More
  • 2022年12月8日