PDF《高级数据结构》

105 ,

0 ≤ xi, yi ≤

109 ,

0 ≤ x1 ≤ x2 ≤

109 ,

0 ≤ y1 ≤ y2 ≤

109 首先我们可以根据容斥原理把矩形询问拆成四组形如 ∑ [xi ≤ x, yi ≤ y] 的询问. wzj52501 高级数据结构 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 例题

1 矩形数点 给定 n 个点的坐标 (xi, yi),你需要回答 q 次询问.每次询问给出了一 个以 (x1, y1) 为左上角,(x2, y2) 为右下角的矩形,你需要回答被这个 矩形包含的点(可以在矩形边界上)的个数. n, q ≤

105 ,

0 ≤ xi, yi ≤

109 ,

0 ≤ x1 ≤ x2 ≤

109 ,

0 ≤ y1 ≤ y2 ≤

109 首先我们可以根据容斥原理把矩形询问拆成四组形如 ∑ [xi ≤ x, yi ≤ y] 的询问. 把点的坐标和询问的坐标放在一起排序,x 坐标自然满足偏序结 构,离散 y 坐标后用树状数组维护前缀和即可. wzj52501 高级数据结构 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 例题

1 矩形数点 给定 n 个点的坐标 (xi, yi),你需要回答 q 次询问.每次询问给出了一 个以 (x1, y1) 为左上角,(x2, y2) 为右下角的矩形,你需要回答被这个 矩形包含的点(可以在矩形边界上)的个数. n, q ≤

105 ,

0 ≤ xi, yi ≤

109 ,

0 ≤ x1 ≤ x2 ≤

109 ,

0 ≤ y1 ≤ y2 ≤

109 首先我们可以根据容斥原理把矩形询问拆成四组形如 ∑ [xi ≤ x, yi ≤ y] 的询问. 把点的坐标和询问的坐标放在一起排序,x 坐标自然满足偏序结 构,离散 y 坐标后用树状数组维护前缀和即可. 时间复杂度为 O((n + q) log n). wzj52501 高级数据结构 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 例题

2 逆序对 给定一个长度为 n 的数列 A,定义其逆序对数为满足 i <

j, Ai >

Aj 的(i, j) 二元组数. 现在你可以将其中任意个数字变成其原来的相反数,要求数列的逆序 对数尽量少.请输出最少的逆序对数. n ≤

105 , |Ai| ≤

109 wzj52501 高级数据结构 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 例题

2 逆序对 给定一个长度为 n 的数列 A,定义其逆序对数为满足 i <

j, Ai >

Aj 的(i, j) 二元组数. 现在你可以将其中任意个数字变成其原来的相反数,要求数列的逆序 对数尽量少.请输出最少的逆序对数. n ≤

105 , |Ai| ≤

109 对于每个数字 Ai,考虑其符号的正负会对逆序对数有怎样的影响. wzj52501 高级数据结构 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 例题

2 逆序对 给定一个长度为 n 的数列 A,定义其逆序对数为满足 i <

j, Ai >

Aj 的(i, j) 二元组数. 现在你可以将其中任意个数字变成其原来的相反数,要求数列的逆序 对数尽量少.请输出最少的逆序对数. n ≤

105 , |Ai| ≤

109 对于每个数字 Ai,考虑其符号的正负会对逆序对数有怎样的影响. 我们发现,对于其前后绝对值 ≥ |Ai| 的数字,更改 Ai 的符号不会 改变逆序对的数量. 而对于那些绝对值 <

|Ai| 的数字,设在 i 之前的有 a 个,在i之后的有 b 个.若Ai 符号为正,则逆序对数增加 b 个,否则增加 a 个.这也恰好不重不漏包含了所有的逆序对情况. wzj52501 高级数据结构 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 例题

2 逆序对 给定一个长度为 n 的数列 A,定义其逆序对数为满足 i <