标签: 树状数组

2 篇文章

Luogu – P5677 – [GZOI2017]配对统计
给定一个数列 $a_1, a_2, \cdots, a_n$.
定义在有序数对 $(x, y)$ 上的“好对”:对于 $a_x$,$y\in[1, x)\cup(x, n]$ 能使 $|a_x-a_y|$ 取最小值。
给定 $q\leq 3\times 10^5$ 组询问,每次询问一个区间 $[l, r]$ 中,有多少个好对。
求:每次询问的答案 $Ans_i$ 与询问编号 $i$ 的乘积的和,即:
$$ \sum_{i=1}^{m}Ans_i\times i $$
密码保护:ZROI – 19普转提 – Day5 – T3 – 背包
有 $n$ 个物品,编号为 $1$ ~ $n$,每个物品有重量 $w_i$,价值 $v_i$.
有 $m$ 个背包,编号为 $1$ ~ $m$,每个背包有容量上限 $t_i$.
物品 $i$ 能够放入背包 $j$,当且仅当 $t_j \geq w_i$.
现在选出 $n$ 个物品,使它们能够通过交换顺序满足:物品的重量和价值从左到右均单调不降。且这 $n$ 个物品能分别放入不同的背包中。
求 $\rm{Max\_n}$.