zcmimi's blog

arrow_back树状数组共33篇文章

avatar
zc
2020-01-19 11:09:00
查看原题

点击跳转

avatar
zc
2020-01-18 22:40:00
查看原题

点击跳转

看到交换相邻字母,就想到逆序对

考虑一下,一定是将A的每个字母移动到离它最近的B中相同字母的位置

我们可以用讲位置存起来然后处理一下

之后数组变成了A中每个位置最后在B中的位置

这个数组中逆序对的数目就是答案

avatar
zc
2020-01-18 22:40:00
查看原题

点击跳转

可以先看一下LG P4868 Preprefix sum,很经典一道题,维护一下后缀和就可以了

这题的话就是把上面那道题变了一下

由于值域太大,我们可以使用 动态开点线段树 或 树状数组+离散化

avatar
zc
2020-01-18 22:40:00
查看原题

点击跳转

解法1(在线):

bfs序,实现较为麻烦

解法2(离线):

考虑单独的一个节点u,它的操作影响的都是在它子树内的与u深度差小于等于k的节点,那么我们只要维护每层深度的操作总和就行了

修改x影响的只有x的子树,我们可以在dfs时这样操作:

1.进入该点

  1. 实现该点的所有操作
  2. 递归它的子树
  3. 撤销操作

这样就不会影响到其他点了

avatar
zc
2019-12-22 13:54:00
查看原题

点击跳转

区间加,单点查询

设差分数组d_i=a_i-a_{i-1}

修改:d_l+=v,d_{r+1}-=v

查询:a_i=\sum\limits_{j=1}^id_j

区间加,区间查询

\sum_{i=1}^na_i=\sum_{i=1}^n\sum_{j=1}^id_i \\ =\sum_{i=1}^nd_i\times(n-i+1) \\ =n\sum_{i=1}^nd_i-\sum_{i=1}^n d_i\times(i-1)

维护两个树状数组,一个记录d_i,另一个记录d_i\times(i-1)

修改:

d_l+=v,d_{r+1}-=v

d'_l+=v\times(l-1),d'_{r+1}-=v\times(l-1)

查询:如上述

avatar
zc
2019-12-21 21:54:00
查看原题

点击跳转

avatar
zc
2019-12-21 19:47:00
查看原题

点击跳转

S_i[1,i]\ge w的数的个数

如果一个区间要满足中位数\ge w,那么\frac {S_r-S_{l-1}}{\frac {r-l+1}2} \ge w

化简一下:2S_r-r > 2S_{l-1}-(l-1)

那么二分w然后用树状数组统计之后判断排名是否\ge k就可以了

avatar
zc
2019-12-21 19:47:00
查看原题

点击跳转

二分第k大平均数w,统计平均数大于等于它的区间的个数

这样的区间满足\frac {s_r - s_{l-1}}{r-l+1} \ge w

化简一下: s_r - s_{l-1} \ge w(r-(l-1)) \\\\ s_r - wr \ge s_{l-1} - w(l-1) 那么我们只要用树状数组统计一下就可以了(当然你要用权值线段树也可以)

因为平均数可能不是整数,所以我们要离散化一下才能统计

avatar
zc
2019-12-21 19:47:00
查看原题

点击跳转

连续和相当于区间和,题目的意思是求所有S_i-S_j的异或和

一般位运算的题我们都拆成二进制下32位来解决

考虑每一位

枚举k

如何统计有多少个((S_i-S_j)>>k)\&1呢?

可以开两个权值树状数组来统计01的数量

如果当前S_i的第k位为1,如果S_j\&(1<<k) = 0S_i+S_j在二进制下进位不会影响到第k位的都符合条件

也就是S_j\&((1<<k)-1) \not = (S_i\&((1<<k)-1))

\&((1<<k)-1)也就是取前k

avatar
zc
2019-12-21 19:47:00
查看原题

点击跳转

这题真的很妙

可以想到二分最大值

问题就转化为如何判断是否合法

从左到右扫描区间的左端点,扫描到的就把右端点放入堆

每个点的权值可以用线段树树状数组维护

扫描时遇到点值不够时,就从优先队列中找到最大的右端点,区间加一遍

当优先队列为空或次数不足时就不符合要求

3/4
Search
search