我受 @I_will_AKIOI 的启发，仿效他来维护区间最值来快速筛出操作一需要操作哪些区间。

不同的是，我多维护了一个最大值，这样可以保证严格的时间复杂度。

结果要维护的状态太多了，一下子给自己写炸了。

求大佬帮忙看看，大样例未过但答案接近，误差 $\leq 0.1 \%$，悬关。

#include <bits/extc++.h>

const int invaild = -1;
#define inline	__always_inline
using pll = std::pair<int64_t, int64_t>;

inline void read(int &x)
{
	char ch;
	for (ch = getchar(); !isdigit(ch); ch = getchar());
	for (x = 0; isdigit(ch); ch = getchar())	x = x * 10 + ch - '0';
}

class segment_tree_t
{
public:
	struct segment_t
	{
		int l, r;
		inline int size()					const	{ return r - l; }
		inline int mid()					const	{ return l + r >> 1; }
		inline segment_t left()				const	{ return {l, mid()}; }
		inline segment_t right()			const	{ return {mid(), r}; }
		inline bool in(const segment_t &s)	const	{ return s.l <= l && r <= s.r; }
		inline bool out(const segment_t &s)	const	{ return s.r <= l || r <= s.l; }
	};
	struct node_t
	{
		node_t *left, *right;
		segment_t s;
		int64_t set_a, set_b;
		int64_t value_prod, value_sum;
		int64_t add_t;
		pll max_prod, min_prod;
		inline int64_t sum() const
		{
			if (set_a != invaild)
				return (int64_t)(set_a + set_b) * (int64_t)s.size();
			return value_sum + (int64_t)(add_t << 1) * (int64_t)s.size();
		}
		inline int64_t prod() const
		{
			if (set_a != invaild)
				return ((int64_t)set_a * set_b) * (int64_t)s.size();
			return value_prod + value_sum * add_t + (int64_t)add_t * add_t * s.size();
		}
		inline pll max() const 
		{
			if (set_a != invaild)
				return {((int64_t)set_a * set_b), set_a + set_b};
			return {max_prod.first + (max_prod.second + add_t) * add_t, max_prod.second + (int64_t)(add_t << 1)};
		}
		inline pll min() const 
		{ 
			if (set_a != invaild)
				return {((int64_t)set_a * set_b), set_a + set_b};
			return {min_prod.first + (min_prod.second + add_t) * add_t, min_prod.second + (int64_t)(add_t << 1)};
		}
	};
	node_t *root, *stack, *top;
	segment_tree_t(const segment_t &s, int size)
	{
		root = stack = (node_t *)calloc(size, sizeof(node_t));
		*root = {NULL, NULL, s, invaild, invaild};
		top = root + 1;
	}
	~segment_tree_t() { free(stack); }
	inline void push_down(node_t *u)
	{
		if (u->set_a != invaild)
		{
			u->left->set_a = u->right->set_a = u->set_a;
			u->left->set_b = u->right->set_b = u->set_b;
			u->set_a = u->set_b = invaild;
			u->add_t = 0;
		}
		else if (u->add_t)
		{
			if (u->left->set_a == invaild)
				u->left->add_t += u->add_t;
			else
			{
				u->left->set_a += u->add_t;
				u->left->set_b += u->add_t;
			}
			if (u->right->set_a == invaild)
				u->right->add_t += u->add_t;
			else
			{
				u->right->set_a += u->add_t;
				u->right->set_b += u->add_t;
			}
			u->add_t = 0;
		}
	}
	inline void push_up(node_t *u)
	{
		u->value_sum = u->left->sum() + u->right->sum();
		u->value_prod = u->left->prod() + u->right->prod();
		u->max_prod = std::max(u->left->max(), u->right->max());
		u->min_prod = std::min(u->left->min(), u->right->min());
	}
	void build(node_t *u, const segment_t &s, int *a, int *b)
	{
		u->s = s;
		if (s.size() == 1)
		{
			u->set_a = a[s.l];
			u->set_b = b[s.l];
			return;
		}
		u->set_a = u->set_b = invaild;
		build(u->left = top++, s.left(), a, b);
		build(u->right = top++, s.right(), a, b);
		push_up(u);
	}
	void set(node_t *u, const segment_t &s, int a, int b)
	{
		if (u->s.out(s))
			return;
		if (u->s.in(s))
		{
			u->set_a = a;
			u->set_b = b;
			return;
		}
		push_down(u);
		set(u->left, s, a, b);
		set(u->right, s, a, b);
		push_up(u);
	}
	void add(node_t *u, const segment_t &s, int k, int t)
	{
		if (u->s.out(s) || u->min().first > k)
			return;
		if (u->s.in(s) && u->max().first <= k)
		{
			if (u->set_a == invaild)
				u->add_t += t;
			else
			{
				u->set_a += t;
				u->set_b += t;
			}
			return;
		}
		push_down(u);
		add(u->left, s, k, t);
		add(u->right, s, k, t);
		push_up(u);
	}
	int64_t sum(node_t *u, const segment_t &s)
	{
		if (u->s.out(s))
			return 0;
		if (u->s.in(s))
			return u->sum();
		push_down(u);
		push_up(u);
		return sum(u->left, s) + sum(u->right, s);
	}
};


int main()
{
	freopen64("sample1.in", "r", stdin);
	int n, m;
	read(n), read(m);
	int a[n], b[n];
	for (int i = 0; i < n; i++)	read(a[i]);
	for (int i = 0; i < n; i++)	read(b[i]);
	segment_tree_t tree({0, n}, n * 4);
	tree.build(tree.root, {0, n}, a, b);
	int op, x, y; segment_tree_t::segment_t s;
	for (int i = 0; i < m; i++)
	{
		read(op);
		if (op == 1)
		{
			read(s.l), read(s.r), read(x), read(y); s.l--;
			if (y == 0)
				continue;
			tree.add(tree.root, s, x, y);
		}
		else if (op == 2)
		{
			read(s.r), read(x), read(y); s.l = s.r - 1;
			tree.set(tree.root, s, x, y);
		}
		else
		{
			read(s.l), read(s.r); s.l--;
			printf("%ld\n", tree.sum(tree.root, s));
		}
	}
	return 0;
}