P3372 【模板】线段树 1

注意size信息应该存放在info里和tag运算，已经tag是表示子树未处理的信息

#include<bits/stdc++.h>
using namespace std;
#define x first
#define y second
typedef pair<int,int> PII;
typedef long long ll;
typedef unsigned long long ull;
typedef unsigned int uint;
typedef vector<string> VS;
typedef vector<int> VI;
typedef vector<vector<int>> VVI;
const int N = 1e5+10;
int n,m;
int a[N];
struct info
{
	ll sum,sz;
};
struct tag
{
	ll add;
};
//处理左右子树
info operator + (const info &l,const info &r)
{
	return {l.sum + r.sum, l.sz + r.sz};
}
//处理节点和标记的作用
info operator + (const info &v,const tag &t)
{
	return {v.sum + t.add*v.sz, v.sz};
}
//处理lazy标记的传递t1作用于t2
tag operator + (const tag &t1, const tag &t2)
{
	return {t1.add + t2.add};
}
struct node
{
	int l,r;
	info val;
	tag t;
}tr[N<<2];

//settag是在pushdown里面用表示用tagt更新p点
void settag(int p,tag t)
{
	//注意tag表示的是下面的区段未更新的值，settag当前p应该由t更新
	tr[p].val = tr[p].val + t;
	tr[p].t = t + tr[p].t;
}
void pushup(int p)
{
	tr[p].val = tr[p<<1].val + tr[p<<1|1].val;
}
void pushdown(int p)
{
	auto &t = tr[p].t;
	if(t.add)
	{
		settag(p<<1,t);
		settag(p<<1|1,t);
		t.add = 0;
	}
}
void build(int l,int r,int p)
{
	tr[p].l = l, tr[p].r = r;
	if(l == r) 
	{
		tr[p].val = {a[r],1};
		return ;
	}
	int m = (l+r)/2;
	build(l,m,p<<1);
	build(m+1,r,p<<1|1);
	pushup(p);
}
void update(int L,int R,tag C,int p)
{
	int l = tr[p].l, r = tr[p].r;
	if(L<=l&&r<=R) 
	{
		settag(p,C);
		return ;
	}
	pushdown(p);
	int m = (l+r)/2;
	if(R<=m) update(L,R,C,p<<1);
	else if(L>m) update(L,R,C,p<<1|1);
	else 
	{
		update(L,m,C,p<<1);
		update(m+1,R,C,p<<1|1);
	}
	pushup(p);
}
info query(int L,int R,int p)
{
	int l = tr[p].l, r = tr[p].r;
	if(L<=l&&r<=R) return tr[p].val;
	pushdown(p);
	int m = (l+r)/2;
	if(R<=m) return query(L,R,p<<1);
	else if(L>m) return query(L,R,p<<1|1);
	else return query(L,m,p<<1) + query(m+1,R,p<<1|1);
}

void solve()
{
    cin>>n>>m;
	for(int i=1;i<=n;++i) cin>>a[i];
	build(1,n,1);
	for(int i=0;i<m;++i)
	{
		int op,l,r,x;
		cin>>op;
		if(op&1)
		{
			cin>>l>>r>>x;
			update(l,r,tag{x},1);
		}
		else
		{
			cin>>l>>r;
			cout<<query(l,r,1).sum<<'\n';
		}
	}
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	int T = 1;
	//cin>>T;
	while(T--)
	{
		solve();
	}
}