牛客练习赛49 D筱玛爱线段树

筱玛爱线段树

差分数组、前缀和

定义一个tg[i]表示在i处操作需要进行多少次

对于操作一，将Al~Ar的每一项的值加上1。

在l处标记+1*tg[i]，在r+1处标记-1*tg[i]，求前缀和，可以实现l~r间每一项+1*tg[i]

对于操作二，在tg[r]处标记+1*tg[i]，在tg[l-1]处标记-1*tg[i]，求后缀和，求得tg[i]

#include<bits/stdc++.h>
using namespace std;
const int mod=1e9+7;
const int N=1e5+100;
typedef long long ll;

ll a[N];
int p[N],l[N],r[N];
ll tg[N]={0};
int main(){
	int n,m;
	cin>>n>>m;
	memset(a,0,sizeof(int)*(n+2));
	for(int i=1;i<=m;i++)
		cin>>p[i]>>l[i]>>r[i];
	tg[m]=1;
	for(int i=m;i>=1;i--){
		tg[i]=(tg[i]+tg[i+1])%mod;//后缀和
		if(p[i]==1){
			a[l[i]]=(a[l[i]]+tg[i])%mod;
			a[r[i]+1]=(a[r[i]+1]-tg[i]+mod)%mod;
		}
		else{
			tg[r[i]]=(tg[r[i]]+tg[i])%mod;
			tg[l[i]-1]=(tg[l[i]-1]-tg[i]+mod)%mod;
		}
	}
	ll cnt=0;
	for(int i=1;i<=n;i++){//前缀和
		cnt=(cnt+a[i])%mod;
		cout<<cnt<<(i==n?"\n":" ");
	}
	return 0;
}