【模板】超级线段树

#include<bits/stdc++.h>

using namespace std;

struct node
{
	int sum, maxn, minn;
}tree[10000010];
int n, v[10000010], add[10000010], m;

void push_down(int x, int l, int r, int a, int b)
{
	int mid = (l + r) >> 1;
	tree[x + x].maxn += add[x];
	tree[x + x].minn += add[x];
	tree[x + x].sum += (mid - l + 1) * add[x];
	tree[x + x + 1].maxn += add[x];
	tree[x + x + 1].minn += add[x];
	tree[x + x + 1].sum += (r - mid - 1 + 1) * add[x];
	add[x + x] += add[x];
	add[x + x + 1] += add[x];
	add[x] = 0;
	return ; 
}

void build_tree(int x, int l, int r)
{
	if(l == r)
	{
		tree[x].sum = v[l];
		tree[x].maxn = v[l];
		tree[x].minn = v[l];
		return ;
	}
	int mid = (l + r) >> 1;
	build_tree(x + x, l, mid);
	build_tree(x + x + 1, mid + 1, r);
	tree[x].sum = tree[x + x].sum + tree[x + x + 1].sum;
	tree[x].maxn = max(tree[x + x].maxn, tree[x + x + 1].maxn);
	tree[x].minn = min(tree[x + x].minn, tree[x + x + 1].minn);
}

void change(int x, int l, int r, int a, int b, int val)
{
	
	if(l == a && r == b)
	{
		tree[x].sum += (r - l + 1) * val;
		tree[x].minn += val;
		tree[x].maxn += val;
		add[x] += val;
		return ;
	}
	if(add[x] > 0) push_down(x, l, r, a, b);	
	int mid = (l + r) >> 1;
	if(a > mid) change(x + x + 1, mid + 1, r, a, b, val);
	else if(b <= mid) change(x + x, l, mid, a, b, val);
	else change(x + x, l, mid, a, mid, val), change(x + x + 1, mid + 1, r, mid + 1, b, val);
	tree[x].sum = tree[x + x].sum + tree[x + x + 1].sum;
	tree[x].maxn = max(tree[x + x].maxn, tree[x + x + 1].maxn);
	tree[x].minn = min(tree[x + x].minn, tree[x + x + 1].minn);
}

int query(int x, int l, int r, int a, int b, int s)
{
	if(l == a && r == b)
	{
		if(s == 2) return tree[x].sum;
		if(s == 3) return tree[x].maxn;
		if(s == 4) return tree[x].minn;
	}
	if(add[x] > 0) push_down(x, l, r, a, b);	
	int mid = (l + r) >> 1;
	if(s == 2)
	{
		if(a > mid) return query(x + x + 1, mid + 1, r, a, b, s);
		else if(b <= mid) return query(x + x, l, mid, a, b, s);
		else return query(x + x, l, mid, a, mid, s) + query(x + x + 1, mid + 1, r, mid + 1, b, s);
	}
	else if(s == 3)
	{
		if(a > mid) return query(x + x + 1, mid + 1, r, a, b, s);
		else if(b <= mid) return query(x + x, l, mid, a, b, s);
		else return max(query(x + x, l, mid, a, mid, s), query(x + x + 1, mid + 1, r, mid + 1, b, s));
	}
	else
	{
		if(a > mid) return query(x + x + 1, mid + 1, r, a, b, s);
		else if(b <= mid) return query(x + x, l, mid, a, b, s);
		else return min(query(x + x, l, mid, a, mid, s), query(x + x + 1, mid + 1, r, mid + 1, b, s));
	}
}

int main()
{
	scanf("%d%d", &n, &m);
	for(int i = 1; i <= n; i++)
	{
		scanf("%d", &v[i]);
	}
	build_tree(1, 1, n);
	for(int i = 1, q, a, b, c, d, e; i <= m; i++)
	{
		scanf("%d", &q);
		if(q == 1)
		{
			scanf("%d%d%d", &a, &b, &c);
			change(1, 1, n, a, b, c);
		}
		else if(q == 2)
		{
			scanf("%d%d", &a, &b);
			printf("%d\n", query(1, 1, n, a, b, 2));
		}
		else if(q == 3)
		{
			scanf("%d%d", &a, &b);
			printf("%d\n", query(1, 1, n, a, b ,3));
		}
		else 
		{
			scanf("%d%d", &a, &b);
			printf("%d\n", query(1, 1, n, a, b, 4));
		}
	}
	return 0;
}