zcmimi's blog

arrow_back线段树共44篇文章

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

点击跳转

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

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

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

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

点击跳转

x>y,看成x\rightarrow y的一条边

若最后的图出现环的话那就是不合法的

但是如果按照普通的建图方式的话每次要添加k(r-l-1-k)条边

我们可以线段树优化建图

因为k \le 3 \times 10^5

所以整个区间最多被划分成3\times 10^5

log n的复杂度是可以接受的

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 19:47:00
查看原题

点击跳转

一个矩形要想被保护的话,必须满足所有行 / 所有列上均有一个车的限制。这样我们解决问题就可以转化为判断一个矩形所有行上是否都有一个车了(对于列只需要把图转一下做就可以)。这样我们自然想到线段树 + 扫描线,我是用列上的扫描线从上到下,每一次扫到一个矩形的下边界就判断一下。线段树上维护每一列上距离最远的一个车的纵坐标,我们判断一个矩形是否被保护就只需要判断最远的车是否在当前矩形的范围内了。感觉OFN说的扫描线就是把问题转化到一个前缀的维护上面去其实是挺有道理的恩~

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

点击跳转

自己写了个莫队,结果51nod跑的太慢,然后TLE(MLE)

题解妙极了:

离线之后,从左向右扫一遍,让每个值存储“当前已扫过的部分中,右边第一个与自己相等的点到自己的距离”,然后如果当前扫到的点是询问的右端点的话,就回答这个询问。

这里面有个很巧妙的地方就是在询问的时候按r的大小从左往右询问,每次更新的时候更新的是和这个点最近的左边的点。因为只有更新到第r个点时才能能查询 l - r 的区间例如:1 2 3 4 1 只有在 r 等于 5 时才能询问 L - 5的区间,此时更新第一个1的值为4,如果L > 1的话区间并未更新所以查询线段树中L- 5的最小值还是INF

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

点击跳转

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

点击跳转

直接建立20棵线段树统计1,2,4,8,...,2^20就可以了

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

点击跳转

把站位当作抵消的部分

建立两棵线段树,统计x轴和y轴被覆盖的情况

每次的答案就是

放过的行数×行长度+放过的列数×列长度-抵消块数

抵消块数就是x轴被覆盖行数\times y轴被覆盖行数 \times 2

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

点击跳转

设选区间[l,r],要穿x号的人数为f(x)

必须满足 \sum_{i=l}^{r}f(i) \le (r-l+1+d) \times k

\sum_{i=l}^{r}(f(i)-k) \le kd

那么用线段树维护全局最大子段和就可以了

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

点击跳转

直接树剖即可

3/5
Search
search