牛客练习赛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;
}