题意:
一个长度为n的数组,初始值都是0,给出2个操作:
操作1: 区间[l:r] 加1
操作2: 执行操作编号在[l,r]内的所有操作各一次
求最后序列是多少?
分析:
1、首先操作2是在之前操作再进行一次,所以我们可以先统计当前这个位置被操作了多少次,怎么统计呢,每个2的操作是对前面操作的重复,
所以我们把操作从后往前跑,维护差分数组,求后缀和。
2、其次我们计算答案的时候,也是维护差分数组。最后答案就是前缀和跑一下。
详细看代码:
#include <bits/stdc++.h> #define int long long using namespace std; const int mod=1e9+7; const int N=1e5+100; int n,m; int op; struct Node { int op,l,r; }q[N]; int cnt[N]; int ans[N]; signed main() { scanf("%lld%lld",&n,&m); for(int i=1;i<=m;i++) { scanf("%lld%lld%lld",&q[i].op,&q[i].l,&q[i].r); } cnt[m+1]=1; for(int i=m;i>=1;i--) { cnt[i]=(cnt[i]+cnt[i+1])%mod; int l=q[i].l; int r=q[i].r; if(q[i].op==2) { cnt[r]=(cnt[r]+cnt[i])%mod; cnt[l-1]=(cnt[l-1]-cnt[i]+mod)%mod; } } // for(int i=1;i<=m;i++) // { // printf("%d%c",cnt[i]," \n"[i==m]); // } for(int i=1;i<=m;i++) { int l=q[i].l; int r=q[i].r; if(q[i].op==1) { ans[l]=(ans[l]+cnt[i])%mod; ans[r+1]=(ans[r+1]-cnt[i]+mod)%mod; } } for(int i=1;i<=n;i++) { ans[i]=(ans[i]+ans[i-1])%mod; printf("%lld%c",ans[i]%mod," \n"[i==n]); } return 0; }