牛客练习赛（49）筱玛爱线段树

筱玛爱线段树

题目描述

筱玛是一个热爱线段树的好筱玛。
筱玛的爷爷马爷在游戏中被筱玛吊打了，于是他恼羞成怒，决定给筱玛出这样一道数据结构题：
给定一个长度为n的数组AA，刚开始每一项的值均为0。
支持以下两种操作，操作共m次：
1 l r：将A_l~ A_r的每一项的值加上1。
2 l r：执行操作编号在[l,r]内的所有操作各一次，保证r小于当前操作的编号。
m次操作结束后，你要告诉马爷A数组变成什么样子了。
由于答案可能会很大，你只需要输出数组A中的每个数在模10^9+7意义下的值。

输入描述:

第一行两个数n,m，分别表示数组长度及操作次数。
接下来m行，每行三个数opt,l,r，表示一次操作。

输入

4 3
1 1 3
2 1 1
1 1 3

输出

3 3 3 0

题目意思已经很明显，但是容易忽略的是2操作包含的范围里面如果还有2操作那么又要进行叠加；
但是还是不好做啊，题目说是线段树，但是看了很多题解都是用差分来做；其实这道题也可以用线段树，不过是麻烦一点，建两颗树；一颗是以m为节点建一颗树，一颗是以n为节点建一颗树；先从后往前判断，当操作为2时，就进行add操作，这时要注意加的值是当前操作2时累计下来的值，不是1；进行完这个操作以后，就可以进行节点为n的树的操作，只要考虑操作为1就行，加上的值依然为操作1累加的值，不是1；最后逐个访问一下就行；

#include<bits/stdc++.h>
#define LL long long
using namespace std;
const LL mod=1e9+7;
struct Node{
	int l,r;
	LL w,f;
}tree[400010];
int x,y,q;
LL z;
LL sum[100010];//记录每个操作可以做的次数 
LL sta;
int fx[100010],fy[100010],fq[100010];
inline void build(int k,int ll,int rr){
	tree[k].l=ll,tree[k].r=rr,tree[k].f=0;
	if(ll==rr){
		tree[k].w=sta;
		return;
	}
	int m=(ll+rr)>>1;
	build(k<<1,ll,m);
	build(k<<1|1,m+1,rr);
}
inline void pd(int k){
	if(tree[k].f){
		tree[k<<1].f=(tree[k<<1].f+tree[k].f)%mod;
		tree[k<<1|1].f=(tree[k].f+tree[k<<1|1].f)%mod;
		tree[k<<1].w=(tree[k<<1].w+tree[k].f*(tree[k<<1].r-tree[k<<1].l+1))%mod;
		tree[k<<1|1].w=(tree[k<<1|1].w+tree[k].f*(tree[k<<1|1].r-tree[k<<1|1].l+1))%mod;
		tree[k].f=0;
	}
}
inline void add(int k){
	if(tree[k].l>=x&&tree[k].r<=y){
		tree[k].w=(tree[k].w+(tree[k].r-tree[k].l+1)*z)%mod;
		tree[k].f=(tree[k].f+z)%mod;
		return;
	}
	pd(k);
	int m=(tree[k].l+tree[k].r)>>1;
	if(x<=m) add(k<<1);
	if(y>m) add(k<<1|1);
	tree[k].w=(tree[k<<1].w+tree[k<<1|1].w)%mod;
}
inline LL ask(int k){
	if(tree[k].l==tree[k].r){ 
		return tree[k].w;
	}
	pd(k);
	int m=(tree[k].l+tree[k].r)>>1;
	if(x<=m) ask(k<<1);
	else ask(k<<1|1);
}
int main(){
	int n,m;
	scanf("%d%d",&n,&m);
	sta=1;//每个结点初始值， 
	build(1,1,m);//m个操作建树 
	for(int i=1;i<=m;i++){
		scanf("%d%d%d",&q,&x,&y);
		fx[i]=x,fy[i]=y,fq[i]=q;
	}
	for(int i=m;i>=1;i--){//反向询问，思考 
		if(fq[i]==2){
			x=i;
			z=ask(1);
			x=fx[i],y=fy[i];
			add(1);
		}
	}
	for(int i=1;i<=m;i++){
		x=i;
		sum[i]=ask(1);
	} 
	sta=0;//记得重置 
	build(1,1,n);//n个数组建树 
	for(int i=1;i<=m;i++){
		if(fq[i]==2) continue;
		z=sum[i];
		x=fx[i],y=fy[i];
		add(1);
	}
	for(int i=1;i<=n;i++){
		x=i;
		printf("%lld ",ask(1));
	}
	printf("\n");
	return 0;
}