• Welcome to the world's largest Chinese hacker forum

    Welcome to the world's largest Chinese hacker forum, our forum registration is open! You can now register for technical communication with us, this is a free and open to the world of the BBS, we founded the purpose for the study of network security, please don't release business of black/grey, or on the BBS posts, to seek help hacker if violations, we will permanently frozen your IP and account, thank you for your cooperation. Hacker attack and defense cracking or network Security

    business please click here: Creation Security  From CNHACKTEAM

Recommended Posts

差分数组

我们令\(a\)表示原数组

\(dif\)表示差分数组

那么我们就有

\[\left\{

\ begin {对齐}

dif[0]=a[0]\\

dif=a-a[i-1],i0

\结束{对齐}

\对。

\]

那么\(a=\sum_{k=0}^idif[k]\)

a

6

3

6

dif

2

-2

-1

-3

假设我们要将a到a[k]的值全部加1,那么在差分数组中只需要一个[我],-一个【k 1】。

树上差分

树上差分有两种,一种是点差分,另一种是边差分。

点差分

现在我们有如下一棵树

lzg2zruo1wm4247.png

仍然是a表示我结点的权值,dif表示差分数组。

对应到树中就有dif[8]=a[8],dif[5]=a[5]-a[8],dif[4]=a[4]-a[5]-a[6]-a[7]。

那么在深度优先搜索回溯时加上一句dif=dif[to] (to为我的子节点),dif就转化为原数组了106 .路径修改

假设我们要将8 - 10这条路径的所有点的权值加x

lpwkinnpmpe4248.png

我们只用dif[8],dif[10],- dif[lca(8,10)](就是四号结点),-dif[父亲[lca(8,10)]](就是2号结点),就可以了106 .例题

最大流量参考代码

#includebits/stdc .h

使用命名空间标准

const int N=5e 410

结构{

int to,next

} e[2 * N];

整数头[N],计数

int f[N][30],lg[N],dep[N];

int n,k,power[N];

inline void add(int a,int b){

e[ cnt].to=b;

e[cnt].next=head[a];

head[a]=CNT;

}

void dfs(int a,int fa){

dep[a]=dep[fa]1;

f[a][0]=fa;

for(int I=1;I=LG[dep[a]];I)f[a]=f[f[a][I-1]][I-1];

(同Internationalorganizations)国际组织到;

for(int I=head[a];我;i=e.下一个){

to=e.到;

if(to==fa)继续;

dfs(to,a);

}

}

int lca(int a,int b){

if(dep[a]dep)swap(a,b);

int d=dep[a]-dep

int t=0;

while(d){

如果(d(1t))a=f[a][t],d-=(1t);

t;

}

如果(a==b)返回b;

for(int I=LG[dep[a]];I=0;- i){

if(f[a]!=f){

a=f[a]

b=f

}

}

return f[a][0];

}

判断是否需要交叉

void get(int a,int fa){

(同Internationalorganizations)国际组织到;

for(int I=head[a];我;i=e.下一个){

to=e.到;

if(to==fa)继续;

得到(到,一);

power[a]=power[to];//将差分数组变为原数组

}

ans=max(ans,power[a]);

}

int main(){

scanf('%d%d ',n,k);

int a,b;

for(int I=2;I=n;I)LG=LG[I-1](1lg[I-1]1==I);

for(int I=1;在;i){

scanf('%d%d ',a,b);

添加(a,b);

添加(b,a);

}

dfs(1,0);

for(int I=1;I=k;i){

scanf('%d%d ',a,b);

int l=lca(a,b);

幂[a],幂,-幂[l],-幂[f[l][0]];//区间修改

}

get(1,0);

printf('%d ',ans);

返回0;

}

边差分

将边的权值给子结点。

qrikolmg0pw4249.png

仍然是刚刚那条路经,由于修改的是边,权值给结点后将不包含生命周期分析(8,10)(4号结点)

那这个时候修改的操作为dif[8],dif[10],dif[lca(8,10)]-=2;

Link to comment
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now