链接:https://ac.nowcoder.com/acm/contest/946/D
来源:牛客网
筱玛是一个热爱线段树的好筱玛。
筱玛的爷爷马爷在游戏中被筱玛吊打了,于是他恼羞成怒,决定给筱玛出这样一道数据结构题:
给定一个长度为nn的数组AA,刚开始每一项的值均为00。
支持以下两种操作,操作共mm次:
1 l r1 l r:将Al∼ArAl∼Ar的每一项的值加上11。
2 l r2 l r:执行操作编号在[l,r][l,r]内的所有操作各一次,保证rr小于当前操作的编号。
mm次操作结束后,你要告诉马爷AA数组变成什么样子了。
由于答案可能会很大,你只需要输出数组AA中的每个数在模109+7109+7意义下的值。
输入描述:
第一行两个数n,mn,m,分别表示数组长度及操作次数。
接下来mm行,每行三个数opt,l,ropt,l,r,表示一次操作。
输出描述:
输出一行共nn个数,表示mm次操作结束后,A1∼AnA1∼An的值。
示例1
输入
4 3
1 1 3
2 1 1
1 1 3
输出
3 3 3 0
备注:
对于100%的数据,1≤n≤105,1≤m≤1051≤n≤105,1≤m≤105。
后缀差分可太秀了
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=100005;
ll mod=1e9+7;
ll qpow(ll a,ll n)
{
ll ans=1;
while(n)
{
if(n&1)
ans=ans*a%mod;
a=a*a%mod;
n>>=1;
}
return ans;
}
int choice[maxn];
int l[maxn];
int r[maxn];
ll tp[maxn];//操作次数的后缀差分序列
ll ans[maxn];//答案的后缀差分序列
int main()
{
int n,m;
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++)
{
scanf("%d%d%d",&choice[i],&l[i],&r[i]);
}
for(int i=m;i>=1;i--)
{
if(choice[i]==1)
{
tp[i]=(tp[i]+tp[i+1]);//得到第i次操作的操作次数
tp[i]%=mod;
ans[l[i]-1]+=mod-tp[i]-1;
ans[l[i]-1]%=mod;
ans[r[i]]+=tp[i]+1;
ans[r[i]]%=mod;
}
else if(choice[i]==2)
{
tp[i]=tp[i]+tp[i+1];//得到第i次操作的操作次数
tp[i]%=mod;
tp[l[i]-1]+=mod-(tp[i]+1);
tp[l[i]-1]%=mod;
tp[r[i]]+=(tp[i]+1);
tp[r[i]]%=mod;
}
}
for(int i=n;i>=1;i--)
{
ans[i]=ans[i]+ans[i+1];
ans[i]%=mod;
}
for(int i=1;i<=n;i++)
printf("%lld ",ans[i]);
}
/*
4 4
1 1 1
2 1 1
2 1 2
2 1 3
*/