差分

程序员文章站 2022-07-12 17:50:30

...

T1:Color the ball
$本题是差分的模板题$
$差分一下两两之间的差值，区间加影响的差值就是cf[l]和$
$cf[r+1]，再做一次前缀和就做完了$

#include<bits/stdc++.h>
using namespace std;

const int N=1e5+5;
int n;
int a,b,p[N];
int main(){
	scanf("%d",&n);
	while(n){
		memset(p,0,sizeof(p));
		for(int i=1;i<=n;i++){
			scanf("%d%d",&a,&b);
			p[a]++,p[b+1]--;
		}
		int sum=0;
		for(int i=1;i<=n;i++)
		{
			sum+=p[i];
			printf("%d ",sum);
		}
		puts("");
		scanf("%d",&n);
	}
}

T2：数列游戏
$线段树是可以的$
$因为修改和询问是分开的，所以我们可以先差分，计算出每个数，再前缀和，然后就可以求区间和了$

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
const ll mod=1e9+7;
const int N=1e6+5;
int n,a,b;
ll cf[N],s[N],aa[N];
int main(){
	scanf("%d%d%d",&n,&a,&b);
	for(int i=1;i<=a;i++){
		int l,r;
		ll c;
		scanf("%d%d%lld",&l,&r,&c);
		cf[l]=((c%mod+cf[l])%mod+mod)%mod;
		cf[r+1]=((cf[r+1]-(c%mod))%mod+mod)%mod;
	}
	for(int i=1;i<=n;i++){
		aa[i]=((aa[i-1]+cf[i])%mod+mod)%mod;
		s[i]=((s[i-1]+aa[i])%mod+mod)%mod;
	}
	for(int i=1;i<=b;i++){
		int l,r;
		scanf("%d%d",&l,&r);
		ll ans=((s[r]-s[l-1])%mod+mod)%mod;
		printf("%lld\n",ans);
	}
}

T3：松鼠的新家

代码中的cf[i]即表示题解中的ans[i]

$对于路径上的值相邻两个数可以看做区间加$
$本题很像树上差分，所以我们直接树上差分，我们将节点s的答案看做子树的和$
$修改就是$
$1.lca是s或t，直接ans[s]或ans[t]++,ans[fa[lca]]--$
$2.lca不是s或t，将ans[s]++,ans[t]++,ans[lca]--,ans[fa[lca]]--$
$由于我还不会倍增求lca，所以我直接上树剖了$
$\color{blue}注意点：$
$1.因为是路径，并不能将相邻节点加两次，所以每次区间加的起点和终点有点难判断，所以不妨直接加$
$s,t的，并且保证不加s(如题意，第一个点不用放)，最后一个节点要减去（如题意），所以最后还需讨论一下，因为情况比较多$
$2.注意题意，最后一个点是不需要加入答案的$

$讨论的情况，$

s,t在一条链上，且s为lca，则ans[s]–,(因为s不用算，所以实际上要算s的子节点，又因为是子节点的父亲–，所以直接ans[s]–),ans[t]++
s,t在一条链上，且t为lca，则ans[fa[s]]++(此时s不用算，因从fa[s]开始计算),ans[fa[v]]–
s,t不在一条链上，所以ans[fa[s]]++,ans[t]++,ans[lca]–,ans[fa[lca]]–

#include<bits/stdc++.h>
using namespace std;

const int N=3e5+5;
int n,a[N];
struct edge{
	int link,v;
}q[N<<1];
int head[N],cnt=0;
void put(int u,int v){q[++cnt].v=v;q[cnt].link=head[u];head[u]=cnt;}
int dfn[N],size[N],son[N],fa[N],id[N],num[N],headline[N],depth[N],cf[N];
void dfs1(int s,int fath){
	int maxson=0;
	size[s]++;depth[s]=depth[fath]+1;
	for(int i=head[s];i;i=q[i].link){
	      int v=q[i].v;
	      if(v==fath) continue; 
		  fa[v]=s;
	      dfs1(v,s);
	      size[s]+=size[v];
		  if(size[v]>maxson){
		  	maxson=size[v];
		  	son[s]=v;
		  }	  
	}
}
int tnt=0,cntid=0;
void dfs2(int s,int fath){
	dfn[s]=++tnt;
	if(son[s]){
	 id[son[s]]=id[s];headline[son[s]]=headline[s];
	 dfs2(son[s],s);
	}
	for(int i=head[s];i;i=q[i].link){
		int v=q[i].v;
		if(v==fath||v==son[s]) continue;
		id[v]=++cntid;num[cntid]=v;headline[v]=v;
		dfs2(v,s);
	}
}
int ans[N];
int find(int u,int v){
	while(headline[u]!=headline[v]){
		if(depth[headline[u]]<depth[headline[v]]) swap(u,v);
		u=fa[headline[u]];
	}
	if(headline[u]==headline[v]){
		if(depth[u]<depth[v])
		swap(u,v);
	    return v;
	}
}
void solve(int now){
	if(now>n) return;
	while(now<=n){
		if(now==2){
			int u=a[now-1],v=a[now];
			cf[v]++;
			now++;
			continue;
		}
		int u=a[now-1],v=a[now],uu=u,vv=v;;
		if(headline[uu]==headline[vv]){
			if(depth[uu]<depth[vv]) swap(uu,vv);
			int lca=vv;
			if(lca==u) {
				cf[u]--,cf[v]++;
			}
			if(lca==v){
				cf[fa[u]]++,cf[fa[v]]--;
			}
			now++;
			continue;
		}
		int lca=find(u,v);
		if(lca==0) lca=a[1];
		cf[fa[u]]++,cf[v]++,cf[lca]--,cf[fa[lca]]--;
		now++;
	}
}
int sum=0;
void dfs(int s,int fath){
    ans[s]=cf[s];
	for(int i=head[s];i;i=q[i].link){
		int v=q[i].v;
		if(v==fath) continue;
		dfs(v,s);
		ans[s]+=ans[v];
	}
}
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]);
	}
	for(int i=1;i<n;i++){
		int u,v;
		scanf("%d%d",&u,&v);
		put(u,v),put(v,u);
	}
	put(0,a[1]),put(a[1],0);
	fa[a[1]]=0;
	dfs1(a[1],0);	
	id[a[1]]=++cntid;num[cntid]=a[1];headline[a[1]]=a[1];
	dfs2(a[1],0);
	solve(2);
	dfs(a[1],0);
	ans[a[n]]--;
	for(int i=1;i<=n;i++){
		printf("%d\n",ans[i]);
	}
}

T4：天天爱跑步

感谢这位大佬的博客让我明白了这道题
 洛谷题面
$不知道这题和差分有什么关系，但既然放到这个专题中，就当做是吧$
$我们发现，没法统计s到t路径上的点是否，所以我们考虑点S，对于S，我们考虑能给S的贡献$
$这样，我们根据NOIP历年套路。显然想到拆分路径，s——lca和lca——t$
$对于s——lca的路径，我们发现能贡献给点S需满足：deep[s]-deep[S]=w[S]$
$对于lca——t的路径，我们发现能贡献给点S需满足：dis[i]-w[S]=deep[v]-deep[S](其中，dis[i]为s——t的路径长，这个可以在计算lca的时候顺便记下来)$
$画个图就能明白$
$化简一下式子，我们发现$
$deep[S]+w[S]=deep[S]$
$w[S]-deep[S]=dis[i]-deep[v]$
$很快想到用树状数组，但本题应该用桶$
然后就做完了
$\color{green}注意点：$

w[S]-deep[S]可能会爆，所以左右同时加n，w[S]-deep[S]+n=dis[i]-deep[v]+n
lca可以看成从s——lca，也可以看成lca——t，所以如果lca满足条件，要-1
倍增求lca时，跳的步数应该到0

#include<bits/stdc++.h>
using namespace std;

const int N=3e5+5;
int n,m,head[N],cnt=0;
struct edge{
	int link,v;
}q[N<<1];
int h1[N],h2[N*3],hcnt1=0,hcnt2=0;
void put(int x,int y){
	q[++cnt].v=y;
	q[cnt].link=head[x];
	head[x]=cnt;
}
struct eg1{
	int link,v;
}q1[N<<1];
struct eg2{
	int link,v;
}q2[N<<1];
void put1(int x,int y){
	q1[++hcnt1].v=y;
	q1[hcnt1].link=h1[x];
	h1[x]=hcnt1;
}
void put2(int x,int y){
	q2[++hcnt2].v=y;
	q2[hcnt2].link=h2[x];
	h2[x]=hcnt2;
}
int d1[N*3],vals[N],d2[N*3],lg[N],w[N],fa[N][20],deep[N],s[N],t[N],lca[N],dis[N];
void dfs(int ss,int fath){
	deep[ss]=deep[fath]+1;
	for(int i=1;i<=lg[deep[ss]-1];i++){
		fa[ss][i]=fa[fa[ss][i-1]][i-1];
	}
	for(int i=head[ss];i;i=q[i].link){
		int v=q[i].v;
		if(v==fath) continue;
		fa[v][0]=ss;
		dfs(v,ss);
	}
}
int Lca(int x,int y){
	if(deep[x]<deep[y]) swap(x,y);
	while(deep[x]>deep[y]){
		x=fa[x][lg[deep[x]-deep[y]]];
	}
	if(x==y) return x;
	for(int i=lg[deep[x]-1];i>=0;i--){//能跳的一定要跳完，所以下界是0，因为当两步到lca时，还需要判断0步的点是不是lca 
		if(fa[x][i]!=fa[y][i]){
			x=fa[x][i],y=fa[y][i];
		}
	}
	return fa[x][0];
}
int valsum[N];
void solve(int ss,int fath){
	int tmp1=d1[deep[ss]+w[ss]],tmp2=d2[w[ss]-deep[ss]+n];
	for(int i=head[ss];i;i=q[i].link)
	{
		int v=q[i].v;
		if(v==fath) continue;
		solve(v,ss);
	}
	d1[deep[ss]]+=vals[ss];
	for(int i=h2[ss];i;i=q2[i].link){
		int v=q2[i].v;
		d2[dis[v]-deep[ss]+n]++;
	}
	valsum[ss]+=d1[deep[ss]+w[ss]]-tmp1+d2[w[ss]-deep[ss]+n]-tmp2;
	for(int i=h1[ss];i;i=q1[i].link){
		int v=q1[i].v;
		int ls=s[i],rt=t[i];
		d1[deep[ls]]--;//只出一个点，其它的点不用出，所以不是dp[deep[ls]]-=vals[ls] 
		d2[dis[v]-deep[rt]+n]--;
	}
}

int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<n;i++){
		int u,v;
		scanf("%d%d",&u,&v);
		put(u,v),put(v,u);
	}
	fa[1][0]=1;
	lg[1]=0;
	for(int i=2;i<=n;i++){
		lg[i]=lg[i>>1]+1;
	}
	dfs(1,0);
	for(int i=1;i<=n;i++){
		scanf("%d",&w[i]);
	}
	for(int i=1;i<=m;i++){
		scanf("%d%d",&s[i],&t[i]);
	    lca[i]=Lca(s[i],t[i]);
	    vals[s[i]]++;
		dis[i]=deep[s[i]]+deep[t[i]]-2*deep[lca[i]];
	    put1(lca[i],i);
	    put2(t[i],i);
	    if(deep[lca[i]]+w[lca[i]]==deep[s[i]]) valsum[lca[i]]--;//如果lca有贡献，我们发现，lca既可以看成是s-lca的，也可以看成是lca-t的贡献，
		                                                        //会重复计算，所以判断一下，提前减去
																//直接看是否满足条件，看看有没有贡献 
	}
	solve(1,0);
	for(int i=1;i<=n;i++){
		printf("%d ",valsum[i]);
	}
}

相关标签：例题差分差分例题 noip

上一篇： effective c++条款10

下一篇： iOS之《Effective Objective-C 2.0》读书笔记（10）

差分

代码中的cf[i]即表示题解中的ans[i]

DxOMark发布一加7T Pro评测：总分114分与P30 Pro仅差2分

图论小结（一）包括一些最短路，最小生成树，差分约束，欧拉回路，的经典题和变种题。强连通，双连通，割点割桥的应用。二分匹配

洛谷P4926 [1007]倍杀测量者(差分约束)

洛谷P1600 天天爱跑步(差分 LCA 桶)

P1438 无聊的数列 (差分+线段树)

P3028 汽水机(差分)

P2352 队爷的新书(差分)

D - Snuke Prime（大数差分）

iPhone 13包装华强北1分钟破解？业内人士：精度差很多

js计算两个时间差天时分秒毫秒的代码

差分

代码中的cf[i]即表示题解中的ans[i]

DxOMark发布一加7T Pro评测：总分114分 与P30 Pro仅差2分

图论小结（一）包括一些最短路，最小生成树，差分约束，欧拉回路，的经典题和变种题。强连通，双连通，割点割桥的应用。二分匹配

洛谷P4926 [1007]倍杀测量者(差分约束)

洛谷P1600 天天爱跑步(差分 LCA 桶)

P1438 无聊的数列 (差分+线段树)

P3028 汽水机(差分)

P2352 队爷的新书(差分)

D - Snuke Prime（大数差分）

iPhone 13包装华强北1分钟破解？业内人士：精度差很多

js计算两个时间差 天 时 分 秒 毫秒的代码

DxOMark发布一加7T Pro评测：总分114分与P30 Pro仅差2分

js计算两个时间差天时分秒毫秒的代码