评测记录

代码：

#include<iostream>
#include<cstdio>
using namespace std;
const int freak = 2147483647;
int n, q, leftt, rightt, x, op, a[1000001];
struct tree{
	int maxx;
	int tg;
	int tj;
	int l;
	int r;
}t[4000001];
void build(int index, int ll, int rr)
{
	t[index].l = ll;
	t[index].r = rr;
	t[index].tg = freak;
	if(t[index].l == t[index].r)
		t[index].maxx = a[t[index].l];
	else
	{
		int m = (ll + rr) / 2;
		build(index * 2, ll, m);
		build(index * 2 + 1, m + 1, rr);
		t[index].maxx = max(t[index * 2].maxx, t[index * 2 + 1].maxx);
	}
}
bool qb(int l1, int r1, int l2, int r2)
{
	return l1 <= l2 && r1 >= r2;
}
bool noj(int l1, int r1, int l2, int r2)
{
	return l1 > r2 || l2 > r1;
}
void pushdown(int);
void tagging(int, int, int);
void pluss(int L, int R, int index, int xx)
{
	if(noj(L, R, t[index].l, t[index].r))
		return;
	if(qb(L, R, t[index].l, t[index].r))
		tagging(index, 2, xx);
	else
	{
		pushdown(index);
		pluss(L, R, index * 2, xx);
		pluss(L, R, index * 2 + 1, xx);
		t[index].maxx = max(t[index * 2].maxx, t[index * 2 + 1].maxx);
	}
}
void xg(int L, int R, int index, int xx)
{
	if(noj(L, R, t[index].l, t[index].r))
		return;
	if(qb(L, R, t[index].l, t[index].r))
		tagging(index, 1, xx);
	else
	{
		pushdown(index);
		xg(L, R, index * 2, xx);
		xg(L, R, index * 2 + 1, xx);
		t[index].maxx = max(t[index * 2].maxx, t[index * 2 + 1].maxx);
	}
}
int query(int L, int R, int index)
{
	if(noj(L, R, t[index].l, t[index].r))
		return -2147483647;
	if(qb(L, R, t[index].l, t[index].r))
		return t[index].maxx;
	else
	{
		pushdown(index);
		return max(query(L, R, index * 2), query(L, R, index * 2 + 1));
	}
}
int main()
{
	cin >> n >> q;
	for(int i = 1; i <= n; i++)
		cin >> a[i];
	build(1, 1, n);
	for(int i = 1; i <= q; i++)
	{
		cin >> op;
		if(op == 1)
		{
			cin >> leftt >> rightt >> x;
			xg(leftt, rightt, 1, x);
		}
		if(op == 2)
		{
			cin >> leftt >> rightt >> x;
			pluss(leftt, rightt, 1, x);
		}
		if(op == 3)
		{
			cin >> leftt >> rightt;
			cout << query(leftt, rightt, 1) << endl;
		}
	}
	return 0;
}
void pushdown(int index)
{
	tagging(index * 2, 2, t[index].tj);
	tagging(index * 2 + 1, 2, t[index].tj);
	if(t[index].tg != freak)
	{
		tagging(index * 2, 1, t[index].tg);
		tagging(index * 2 + 1, 1, t[index].tg);
	}
	t[index].tj = 0;
	t[index].tg = freak;
}
void tagging(int index, int oper, int xx)
{
	if(oper == 1 && oper != freak)//修改操作
	{
		t[index].maxx = xx;
		t[index].tg = xx;	
	} 
	else
	{
		t[index].maxx += xx;
		t[index].tj += xx;
		if(t[index].tg != freak)
		{
			tagging(index * 2, 1, t[index].tg);
			tagging(index * 2 + 1, 1, t[index].tg);
			t[index].tg = freak;
		}
	}
}