menu zcmimi's blog

arrow_back 差分

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

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

include<bits/stdc++.h>

define gc get

zc
2020-05-16 21:36

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

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

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

in

zc
2020-03-01 19:36

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

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

x\leftrightarrow y区间加可以看成x,yw位置+1,$lca(x,y),

zc
2020-03-01 14:52

这题考验的是仔细读题

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

区间加可以用差分来解决

剩下的部分:

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

查询[l,r]

zc
2020-01-18 22:40

```cpp

include<bits/stdc++.h>

namespace ZDY{

#pragma GCC optimize(3)
#define il __inline__ 
zc
2020-01-18 22:40

解法1(在线):

bfs序,实现较为麻烦

解法2(离线):

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

zc
2020-01-18 22:40

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

应该将f_xy的点的答案+1

我们可以差分一下,

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

然后从下加得到的就是

zc
2020-01-18 22:40

解法1

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

```cpp

include<bits/stdc++.h>

namespace ZDY{

#pragma GCC optimize(3
zc
2019-12-31 11:31

```cpp

include<bits/stdc++.h>

namespace ZDY{

#pragma GCC optimize(3)
#define il __inline__ __attr
zc
2019-12-21 19:47
1 / 1
Search
search