zcmimi's blog

arrow_back线段树共46篇文章

avatar
zcmimi
2020-05-25 19:22:00

SPOJ的GSS系列是关于区间统计技巧的集合

非常适合锻炼码力

LG GSS1 | SPOJ GSS1

[LG GSS2](

avatar
zc
2020-10-29 09:11:32

查看原题

点击跳转

将草按生长速度排序,可以发现每次收割完草的高度仍为单调的

维护区间加,区间覆盖,区间和,区间最大值即可

avatar
zc
2020-10-29 07:02:30

查看原题

点击跳转

考虑离线

把所有数排序后,可以发现经过4种操作后所有数还是有序的

这样我们维护区间加,区间乘,区间加变形,区间覆盖

avatar
zc
2020-10-16 13:31:15

查看原题

点击跳转

编号在[L,R]的同学添加第x位同学为自己的观察对象。保证x<L\le R

从左到右考虑,如果当前这个人没有观察在他之前的人,那么就必须让他听到指令

否则他观察的人在之前已经考虑过了

所以需要听到指令的人就是没有观测的人

那么用线段树维护区间就可以了

avatar
zc
2020-09-23 16:31:00

查看原题

点击跳转

记录每段区间操作后:

向上k级祖先,向下d级孩子,该层向右的第i个孩子

线段树维护即可

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

点击跳转

可以发现查询的c\le 20,那么我们直接对每个节点记录每个c的答案

区间加

设当前区间a_1,a_2,\dots,a_n

区间加后:a_1+x,a_2+x,\dots,a_n+x

选取i个方案:

\begin{aligned} &\quad (a_1+x)(a_2+x)\cdots(a_i+x)\\ &=a_1a_2\cdots a_i+xa_2a_3\cdots a_i+x^2a_3a_4\cdots a_i+\dots\\ &=a_1a_2\cdots a_i+\sum_{j=1}^ix^j \left( \text{从i个数中取出i-j个数的乘积之和} \right) \end{aligned}

该区间取i个数的乘积之和增加的贡献:

\displaystyle ans_i\operatorname{+=}\sum_{j=0}^i x^{i-j}ans_j{n-j\choose i-j}

区间反转

选取奇数个的答案变成相反数

选取偶数个的答案没有影响

区间查询

设当前答案为ans,左儿子答案为l,右儿子答案为r

\displaystyle ans_i=\sum_{j=0}^i l_j\times r_{i-j}

(左边选j个,右边选i-j个)

avatar
zc
2020-09-08 17:08:00
查看原题

点击跳转

题意:

给出一棵n个点的树,每次询问给出两对叶子,求这两对叶子产生路径的交点数

解法:

先把一条链上的点都+1,然后查询另一条链的权值和就是答案

也就是链加、链查询

可以直接树剖套线段树/树状数组 \log^2

更优秀的线性做法: 虚树

avatar
zc
2020-09-08 07:47:00
查看原题

点击跳转

线段树维护动态直径

考虑设A_x为每个点的深度

答案可以写成这样的形式:

ans=\max_{1\le x<y\le n}\{ A_x + A_y - 2A_{\text{lca}(x,y)} \}

考虑欧拉序

因为边权为正,且欧拉序,那么

ans=\max_{1\le x<z<y\le n}\{ A_x + A_y - 2A_z \}

线段树维护区间内的min,max,sl,sr,s

其中min为区间最小值,max为区间最大值

sl_x=\max_{l<i<j<r} \{ A_i-2A_j \}\\ sr_x=\max_{l<i<j<r} \{ A_j-2A_i \}\\ s_x=\max_{l<i<k<j<r} \{ A_i+A_j-2A_k \}

最终答案就是s_1

修改边权可转化为子树(区间)加

avatar
zc
2020-09-07 16:56:00
查看原题

点击跳转

可以离线处理,按照左右端点排序

考虑每个点的贡献?

记录左边(L_i)/右边(R_i)第一个比它大的地方

  1. 对于区间[L_i,R_i],它有p_1的贡献
  2. 对于区间[l,R_i],l\in [L_i+1,i-1],它有p_2的贡献
  3. 对于区间[L_i,r],r\in [i+1,R_i-1],它有p_2的贡献

每个询问[l,r]可以转化为r的答案减去l-1的答案

把转化后的询问和每个点的贡献区间按位置排序

对于1,我们在扫到R_i时,更新点L_i的贡献

对于2,我们在扫到R_i时,更新区间L_i+1i-1的贡献

对于3,我们在扫到L_i时,更新区间i+1到R_i-1的贡献

avatar
zc
2020-07-25 23:00:00
查看原题

点击跳转

https://zoj.pintia.cn/problem-sets/91827364500/problems/91827370149

题意:

给一个序列A,要求支持以下操作:

  1. 区间乘

  2. 区间里所有数都变成自己的k次幂

  3. 求区间乘积(mod 10000000007)

由于模数是质数,所以可以将每个数都变成原根的次幂

这样区间乘转化为区间加,区间次幂转化为区间乘,求区间乘积转化为求区间和

1/5
Search
search