WA on #19 95pts求调

#include <bits/stdc++.h>
#define maxn 100001
using namespace std;

long long a[maxn];
struct Node
{
	// data维护区间和，lazy为当前节点的延迟标记
	long long data, lazy = 0;
}tree[4 * maxn];

// 维护各节点的数据
void pushup(int u)
{
	tree[u].data = tree[u * 2].data + tree[u * 2 + 1].data;
}

//建树
void build(int u, int L, int R)
{	
	tree[u].lazy = 0;
	// 到达叶节点
	if(L == R)
	{
		tree[u].data = a[L];
		return;
	}
	
	// 递归建树
	int M = R + L >> 1;
	build(u * 2, L, M), build(u * 2 + 1, M + 1, R);
	// 更新区间和
	pushup(u);
}

// 区间判断
bool InRange(int L, int R, int l, int r) // 判断[L, R]是否被[l, r]包含
{
	return L >= l && R <= r;
}

bool OutofRange(int L, int R, int l, int r) // 判断[L, R]是否与[l, r]有交集
{
	return L > r || R < l;
}

// 制作延迟标记
void maketag(int u, int len, long long x)
{
	tree[u].lazy += x;
	tree[u].data += len * x;
}

// 下传延迟标记
void pushdown(int u, int L, int R)
{
	int M = L + R >> 1;
	maketag(u * 2, M - L + 1, tree[u].lazy); // 下传左子树
	maketag(u * 2 + 1, R - M, tree[u].lazy); // 下传右子树
	tree[u].lazy = 0; // 清空当前节点的延迟标记
}

// 查询
long long query(int u, int L, int R, int l, int r)
{
	// 如果包含
	if(InRange(L, R, l, r))
	{
		return tree[u].data;
	}
	// 如果有交集
	else if(!OutofRange(L, R, l, r))
	{
		int M = L + R >> 1;
		pushdown(u, L, R); // 先下传延迟标记
		return query(u * 2, L, M, l, r) + query(u * 2 + 1, M + 1, R, l, r); // 递归查询
	}
	// 如果无交集
	else
	{
		return 0;
	}
}

// 区间更新
void update(int u, int L, int R, int l, int r, long long x)
{
	// 如果包含
	if(InRange(L, R, l, r))
	{
		maketag(u, R - L + 1, x); // 直接打标记
	}
	// 如果有交集
	else if(!OutofRange(L, R, l, r))
	{
		int M = L + R >> 1;
		pushdown(u, L, R); // 先下传延迟标记
		update(u * 2, L, M, l, r, x); // 递归更新左子树
		update(u * 2 + 1, M + 1, R, l, r, x); // 递归更新右子树
		pushup(u); // 更新当前节点的data
	}
	// 如果没有交集
	else
	{
		return;
	}
}

int main()
{
	int n, m;
	scanf("%d%d", &n, &m);
	for(int i = 1; i <= n; i++) scanf("%d", &a[i]);
	build(1, 1, n);
	
	for(int i = 1; i <= m; i++)
	{
		int op;
		scanf("%d", &op);
		
		if(op == 1)
		{
			int x, y;
			long long k;
			scanf("%d%d%lld", &x, &y, &k);
			update(1, 1, n, x, y, k);
		}
		else
		{
			int x, y;
			scanf("%d%d", &x, &y);
			printf("%lld\n", query(1, 1, n, x, y));
		}
	}
	
	return 0;
}