题目链接

昨晚的 CF 让我想起我有多长时间没打吉司机线段树了…重温一下。

吉司机线段树主要是用来解决序列区间上满足部分满足一定性质的修改操作的，比如这里是区间大于 x 的数改成 x。这里线段树的每个节点维护该节点最大值、最大值出现次数、严格次大值、区间和。于是用 x 修改一个区间的时候：

• x 大于等于区间最大值，直接退出。
• x 小于区间最大值，大于等于区间严格次大值，可以打懒标记，懒标记就是这个 x，直接保存在父节点的 max 值中。
• 否则标记下传到两个子区间，继续运算。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e6 + 9, NPOS = -1;
const ll INF = 1e18;
int t, n, m, a[N];
struct SegmentTree
{
	struct Seg
	{
		int l, r;
		ll max, num, smax, sum;
		void upd(ll val) { sum -= num * (max - val), max = val; }
		friend Seg up(const Seg &lc, const Seg &rc)
		{
			Seg ans = lc;
			ans.r = rc.r;
			ans.sum += rc.sum;
			if (lc.max < rc.max)
			{
				ans.max = rc.max;
				ans.num = rc.num;
				ans.smax = std::max(lc.max, rc.smax);
			}
			else if (lc.max > rc.max)
				ans.smax = std::max(lc.smax, rc.max);
			else
			{
				ans.smax = std::max(lc.smax, rc.smax);
				ans.num += rc.num;
			}
			return ans;
		}
	};
	struct Node : Seg
	{
		int lc, rc;
	};
	vector<Node> v;
	SegmentTree(int l, int r) { v.reserve(r - l + 9 << 1), build(l, r); }
	void build(int l, int r)
	{
		int rt = v.size();
		v.push_back({});
		v[rt].lc = v[rt].rc = NPOS;
		v[rt].Seg::operator=({l, r, l < r ? INF : a[l], 1, -INF, a[l]});
		if (l < r) //注意这里置INF，防止初始化的时候不正确的标记下传
			down(rt), v[rt].Seg::operator=(up(v[v[rt].lc], v[v[rt].rc]));
	}
	void down(int rt)
	{
		int m = v[rt].l + v[rt].r >> 1;
		if (v[rt].lc == NPOS)
			v[rt].lc = v.size(), build(v[rt].l, m);
		if (v[rt].rc == NPOS)
			v[rt].rc = v.size(), build(m + 1, v[rt].r);
		upd(v[v[rt].lc].l, v[v[rt].lc].r, v[rt].max, v[rt].lc);
		upd(v[v[rt].rc].l, v[v[rt].rc].r, v[rt].max, v[rt].rc);
	}
	void upd(int l, int r, ll val, int rt = 0)
	{
		if (val >= v[rt].max)
			return;
		if (l <= v[rt].l && v[rt].r <= r && v[rt].smax < val)
			return v[rt].upd(val);
		down(rt);
		if (r <= v[v[rt].lc].r)
			upd(l, r, val, v[rt].lc);
		else if (l >= v[v[rt].rc].l)
			upd(l, r, val, v[rt].rc);
		else
			upd(l, v[v[rt].lc].r, val, v[rt].lc), upd(v[v[rt].rc].l, r, val, v[rt].rc);
		v[rt].Seg::operator=(up(v[v[rt].lc], v[v[rt].rc]));
	}
	Seg ask(int l, int r, int rt = 0)
	{
		if (l <= v[rt].l && v[rt].r <= r)
			return v[rt];
		down(rt);
		if (r <= v[v[rt].lc].r)
			return ask(l, r, v[rt].lc);
		if (l >= v[v[rt].rc].l)
			return ask(l, r, v[rt].rc);
		return up(ask(l, v[v[rt].lc].r, v[rt].lc), ask(v[v[rt].rc].l, r, v[rt].rc));
	}
};
int main()
{
	for (scanf("%d", &t); t--;)
	{
		scanf("%d%d", &n, &m);
		for (int i = 1; i <= n; ++i)
			scanf("%d", &a[i]);
		SegmentTree t(1, n);
		for (int i = 1, o, x, y; i <= m; ++i)
		{
			scanf("%d%d%d", &o, &x, &y);
			if (o)
				printf("%lld\n", o == 1 ? t.ask(x, y).max : t.ask(x, y).sum);
			else
				scanf("%d", &o), t.upd(x, y, o);
		}
	}
}