zcmimi's blog

arrow_back差分共9篇文章

avatar
zc
2020-05-16 21:36:00
查看原题

点击跳转

相同的定义为:两个子串长度相同且一个串的全部元素加上一个数就会变成另一个串

那么我们差分之后再判断即可

avatar
zc
2020-03-01 19:36:00
查看原题

点击跳转

先离散化权值为排名,从大到小排序

遍历所有点,用权值树状数组统计,结果是 遍历完该子树后答案 - 遍历该子树前答案

(为什么一开始会去想什么dsu on tree和线段树合并

avatar
zc
2020-03-01 14:52:00
查看原题

点击跳转

树上差分,统计的时候每个节点都合并自身子节点的结果

每个点都维护一颗动态开点权值线段树

x\leftrightarrow y区间加可以看成x,yw位置+1,lca(x,y),f_{lca(x,y)}w位置-1

统计的时候不断向上线段树合并

具体看代码

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

点击跳转

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

点击跳转

我们可以用倍增求出能控制某个点x的最远的点y的位置

应该将f_xy的点的答案+1

我们可以差分一下,

++ans_{f_x},--ans_{f_y}

然后从下加得到的就是当前点的答案

记得开long long

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

点击跳转

这题考验的是仔细读题

可以发现修改带查询的只有1000个,这部分直接暴力求就可以了

区间加可以用差分来解决

剩下的部分:

可以预处理出[1,i]的答案ans_i

查询[l,r]的答案就是ans_r-ans_{l-1}

代码很短

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-31 11:31:00
查看原题

点击跳转

解法1

主席树+离散化(深度太大需要离散化)

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

点击跳转

1/1
Search
search