存下操作， 从后往前 用树状数组维护操作的次数， 编号从大到小，防止重复调用递归。
然后再遍历一次，操作一的次数对线段树修改，大概 m*O（logn）
代码语言：javascript复制#include <bits/stdc .h>
using namespace std;
#define ll long long
const int maxn = 100005;
const int mod = 1e9 7;
ll b[maxn];
struct N{
int l,r;
ll pre,add;
}node[4*maxn 5];
struct Q{
int op,l,r;
}q[maxn];
int lowbit(int k)
{
return k&(-k);
}
void update(int k,ll val)
{
while(k<maxn){
b[k] =val;
k =lowbit(k);
}
}
ll sum(int k)
{
ll ans = 0;
while(k>0){
ans=(ans (ll)b[k])%mod;
k-=lowbit(k);
}
return ans%mod;
}
void build(int p,int l,int r){//区间编号p
node[p].l = l;
node[p].r = r;
node[p].add = 0;
if(l==r){//叶子结点直接赋值
node[p].pre = 0;
return ;
}
int mid = l r >>1;
build(2*p,l,mid);
build(2*p 1,mid 1,r);
node[p].pre = node[p*2].pre node[p*2 1].pre;//维护区间和
}
void spread(int p){
if(node[p].add){//如果标记不为0 向下传递
node[2*p].pre =(node[2*p].r - node[2*p].l 1)*node[p].add%mod;
node[2*p].pre%=mod;
node[2*p 1].pre =(node[2*p 1].r - node[2*p 1].l 1)*node[p].add%mod;
node[2*p 1].pre%=mod;
node[2*p].add = node[p].add;
node[2*p 1].add = node[p].add;
node[p].add = 0;
}
}
void change(int p,int l,int r,int v){
if(node[p].l>=l&&node[p].r<=r){//区间被覆盖 就对其进行修改
node[p].pre =((ll)v*(node[p].r-node[p].l 1))%mod;
node[p].pre%=mod;
node[p].add = v; //加上懒惰标记
return ;
}
spread(p);//没有覆盖 下放懒惰标记 考虑儿子区间可能因为懒惰标记存在而没有修改
int mid = node[p].l node[p].r>>1;
if(l<=mid)change(p*2,l,r,v);
if(r>mid)change(p*2 1,l,r,v);
node[p].pre = (node[2*p].pre node[2*p 1].pre)%mod;
}
ll query(int p,int l,int r){
if(l<=node[p].l&&r>=node[p].r){//被覆盖 返回值
return node[p].pre;
}
spread(p);
ll ans = 0;
int mid = node[p].r node[p].l>>1;
if(l<=mid)ans =query(p*2,l,r),ans%=mod;
if(r>mid)ans =query(p*2 1,l,r),ans%=mod;
return ans%mod;
}
int main()
{
int n,m;
scanf("%d %d",&n,&m);
build(1,1,n);
for(int i=1;i<=m;i ){
scanf("%d %d %d",&q[i].op,&q[i].l,&q[i].r);
}
for(int i=m;i>=1;i--){
if(q[i].op==2){//维护 第 i 条指令 对指令 l r 操作 的次数
int val = (sum(i) 1)%mod;
update(q[i].l,val);
update(q[i].r 1,-val);
}
}
for(int i=1;i<=m;i ){
if(q[i].op==1){
int val = (sum(i) 1)%mod;
change(1,q[i].l,q[i].r,val);
}
}
for(int i = 1;i<=n;i ){
printf("%lld%c",query(1,i,i)%mod," n"[i==n]);
}
return 0;
}
/*
5 5
1 1 1
2 1 1
2 1 2
2 1 3
2 1 4
*/
