分析
刚开始看着挺懵的。注意到题目的条件
1.区间加一 2.操作数区间加一
根据分析,如果某一个类型为2的操作不可能形成一个自环,且只会影响前面的操作。据此,我们可以尝试从后往前做(重点一),每次求出后面对当前操作的影响,然后接着更新前面的操作。我们建立一棵以操作编号为
关键字的线段树,如果为类型二操作,明显,就得更新[l,r]的区间,至于要添加上多少操作数,肯定就是求之前的操作对当前点的影响。对于操作1,因为编号比其小的对它无法产生影响,编号比他大的已经算完了,直接加上求出这个操作的次数即可。
代码(线段树好啊)
#include<bits/stdc++.h> #define ls now<<1 #define rs now<<1|1 #define ll long long using namespace std; const int N=1e5+10; const ll mod=1e9+7; int n,m; ll s[N<<2],tag[N<<2],d[N]; int l[N],r[N],id[N]; inline void pd(int now,ll l,ll r) { if(!tag[now]) return ; ll mid=(l+r)>>1; tag[ls]+=tag[now]; tag[rs]+=tag[now]; s[ls]+=(mid-l+1)*tag[now]; s[rs]+=(r-mid)*tag[now]; s[ls]%=mod;s[rs]%=mod; tag[ls]%=mod;tag[rs]%=mod; tag[now]=0; } inline ll find(int now,ll l,ll r,ll x) { if(l==r) return s[now]; pd(now,l,r); ll mid=(l+r)>>1; if(x<=mid) return find(ls,l,mid,x); else return find(rs,mid+1,r,x); } inline void add(int now,ll l,ll r,ll x,ll y,ll z) { if(l>=x&&r<=y) { tag[now]+=z;tag[now]%=mod; s[now]+=(r-l+1)*z; s[now]%=mod; return ; } pd(now,l,r); ll mid=(l+r)>>1; if(x<=mid) add(ls,l,mid,x,y,z); if(mid<y) add(rs,mid+1,r,x,y,z); s[now]=s[ls]+s[rs]; } int main() { scanf("%d%d",&n,&m); for (int i=1;i<=m;i++) scanf("%d%d%d",&id[i],&l[i],&r[i]); add(1,1,m,1,m,1); for (int i=m;i>=1;i--) { if(id[i]==1) continue; ll ok=find(1,1,m,i); add(1,1,m,l[i],r[i],ok); } for (int i=m;i>=1;i--) { if(id[i]==2) continue; ll ok=find(1,1,m,i); d[l[i]]+=ok,d[r[i]+1]-=ok; } for (int i=1;i<=n;i++) d[i]=((d[i]+d[i-1]+mod)%mod+mod)%mod; for (int i=1;i<=n;i++) printf("%lld ",d[i]); return 0; }