牛客挑战赛49 D筱玛爱线段树 线段树+树状数组计数

#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
 
 */