zcmimi's blog

arrow_back线段树共44篇文章

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

点击跳转

线段树裸题

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

点击跳转

并查集技巧:记录每个点后面和它不属于同一个集合的第一个点

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

点击跳转

图形可以分割成一个个小矩阵

于是我们可以把每个矩形变成两条线段后对这些线段进行排序

如此

那么总共覆盖了多少长度?

线段树求!

那管儿子节点的事干嘛,让他们自生自灭得了

于是,我们想到,除左右端点l,r之外,在线段树的每个节点上维护两个值:该节点代表的区间被矩形覆盖的长度len,该节点自身被覆盖的次数cnt。最初,二者均为0.

注意: 每个节点代表的范围是[l,r+1],最后面的那个节点不算入统计

对于每一个(x,y1,y2,k),我们再[val(y1),val(y2)-1](离散化后的区间)上执行期间修改。该区间被线段树划分成 \log n个节点,我们把这些节点的cnt都加k

对于线段树中任意一个节点 [l,r] ,若cnt>0,则len等于raw(r+1)-raw(l)(离散化前的距离),否则,该店len等于两个子节点的len之和。在一个节点的cnt被修改,以及线段树从下往上传递信息时,我们都按照该方法更新len值。根节点的len值就是整个扫描线上被覆盖的长度

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

点击跳转

打算直接把标记用vector记录里,以为可以水过去,结果mle了

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

点击跳转

线段树解法:

我们记录d_x表示x的深度还有dfs

每个点修改的时候把它的子树都加上val

因为记录了深度,所以d_{x'}如果和d_x同奇偶则加上val,否则减去val

树状数组解法:

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

点击跳转

f[i][k]为第i位,分成k

f[i][k] = MAX(f[j][k-1] + cnt[j+1][i])

这样的话肯定复杂度爆炸

既然看到MAX,那是不是可以用线段树优化呢?

记录每个点贡献的范围,更新时把这个范围的点++就可以了。

相信看代码可以看懂

其实我还加了滚动数组OwO

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

点击跳转

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

点击跳转

一段区间检查后能不被吃掉的汉堡满足其他汉堡的能量值都是它的倍数

那我们就求出区间\gcd. 而这个汉堡的能量值必须等于区间gcd,所以它的能量值也是区间最小值。

那我们就再记录区间最小值并且记录数量

那么满足这个复杂度而且最方便的当然是线段树了

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

点击跳转

我们可以发现如果p\le x,那么x\mod p \le \frac x2

所以取模最多\log x

记录区间最大值,如果小于p那么直接返回

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

点击跳转

$$ \frac{1}{n}\sum_{i=1}^{n}(a_i-\bar a)^2

\\

= \frac 1n \sum_{i=1}^{n}(a_i^2-2\bar a\times a_i+{\bar a}^2)

\\

= \frac 1n (\sum_{i=1}^nai^2 - 2\bar a\sum{i=1}^n a_i + n \bar a^2)

\\

= \frac 1n \sum_{i=1}^n a_i^2 - \bar a^2 $$

4/5
Search
search