#edu2026. 树状数组例题

树状数组例题

树状数组例题

例:P6278[USACO20OPEN] Haircut G

【题意简化】

给定一个长度为 n(105)n(\le 10^5) 的序列 ai(0ai105)a_i(0\le a_i \le 10^5),询问对于将所有 aia_i 高于 j(0jn1)j(0\le j \le n-1) 的降为 jj 时逆序对个数,需要依次输出 j=0,1,,n1j=0,1,\dots, n-1 时的答案。

【分析】

如果直接暴力,时间复杂度是 O(n2)O(n^2) , 会超时。分析一下,对于 aia_i , 在 a1ai1a_1 \dots a_{i-1} 中高于 aia_i 如果都降低到 ai+1a_i+1 的高度,依然会形成逆序对。那么对于 jai+1j \ge a_i+1aia_i 形成的逆序对 j=[ai+1,n]j=[a_i+1,n] 都是有效的,就是在树状数组 [ai+1,n][a_i+1,n] 做区间加操作。问题就转化为 “区间修改,单点查询”,可以利用差分求前缀和的方法求出。

参考代码:点击

例:P1972[SDOI2009] HH的项链

【题意简化】给定一个长度为 n(106)n(\le 10^6) 的序列 ai(1ai106)a_i(1 \le a_i \le 10^6),不同 aia_i 表示不同的颜色, 进行 mm 次询问,询问区间 [l,r][l,r] 内颜色的种类数。

【分析】多次查询区间种类数。

对于所有询问,按照右端点排序,记录每种颜色上一次出现的位置 pre[i]pre[i] 表示颜色 aia_i 上一次出现的位置。对于每一个 aia_i , 在 ii 位置上 +1 , 在 pre[i](pre[i]>0)pre[i](pre[i]>0) 位置 1-1 ,避免同一种颜色统计重复,对于右端点落在 ii 位置的查询区间和,就是这个区间对应的答案。

例:P2163 [SHOI2007] 园丁的烦恼

【题意简化】二维平面上给定 nn 个点,进行 mm 次询问,询问给定一个矩形: 左下角 (a,b)(a,b) ,右上角 (c,d)(c,d) 区域内点的数量。

【分析】二维平面数点问题经典问题。可以先思考一个简单问题,每次只查询 (c,d)(c,d) 左下角的点的个数 , 可以将点与查询以 xx 排序, 遇到点在对应 yy 位置 +1+1 ,遇到查询,直接询问 yy 前缀和。(注意 xx 相等的时候,需要将点排在前面)

利用容斥原理,每个询问转变为 44 个前缀和 。

参考代码:点击

例: P3755 [CQOI2017] 老C的任务

【题意简化】

【分析】二维平面求和,类似与二维平面数点。

学习完毕

{{ select(1) }}

  • YES
  • NO