欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

牛客练习赛49 D.筱玛爱线段树(差分)

程序员文章站 2022-03-06 11:58:26
...

题目

给定一个长度为n(n<=1e5)的数组A,刚开始每一项的值均为0。

支持以下两种操作,操作共m(m<=1e5)次:

1 l r:将Al∼Ar的每一项的值加上1。

2 l r:执行操作编号在[l,r]内的所有操作各一次,保证r小于当前操作的编号。

m次操作结束后,你要告诉马爷A数组变成什么样子了。

由于答案可能会很大,你只需要输出数组A中的每个数在模1e9+7意义下的值。

思路来源

官方题解

题解

b[]倒序维护操作差分数组,求后缀和,求出这个点实际的操作次数之后,再对前面的操作差分修改

a[]正序维护值的差分数组,已知b[]中1的操作的实际操作次数之后,对a[]数组差分修改,最后求前缀和

赛中用线段树过的,七八十行,然而差分20多行就能搞过

总是想不到差分,看了差分题解之后自己敲的代码,

虽然感觉取模好像写的不大对,但是AC了就这样叭

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod=1e9+7;
const int N=1e5+10;
int n,m,a[N],b[N];
int op[N],l[N],r[N];
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;++i)
	{
		scanf("%d%d%d",&op[i],&l[i],&r[i]);
		if(op[i]==1)a[l[i]]++,a[r[i]+1]--;
		else b[r[i]]++,b[l[i]-1]--;
	}
	for(int i=m;i>=1;--i)
	{
		b[i]=(1ll*b[i]+b[i+1])%mod;
		if(!b[i])continue;
		if(op[i]==1)(a[l[i]]+=b[i])%=mod,(a[r[i]+1]+=mod-b[i])%=mod;
		else (b[r[i]]+=b[i])%=mod,(b[l[i]-1]+=mod-b[i])%=mod;
	}
	for(int i=1;i<=n;++i)
	{
		(a[i]+=a[i-1])%=mod;
		printf("%d%c",a[i]," \n"[i==n]);
	}
	return 0;
} 

 

相关标签: 差分