传送门
题面言简意赅，就不翻译了。
这个似乎就是Segment Tree Beats了，参考自2016年国家集训队论文，吉如一《区间最值操作与历史最值问题》。但是有关时间复杂度的证明我没有看懂，这里只是记录一下实现方法。
我们需要维护区间和、最大值(Max1)、严格次大值(Max2)，以及最大值的出现次数(num)。
对于一次修改操作，我们要让区间([L,R])对(x)取( extrm{min})。具体做法是先正常在线段树上二分，找到这个区间对应的节点。当找到这个节点时，要分三种情况讨论：
- 当(Max1 leqslant x)时，显然修改不会产生影响，直接返回。
- 当(Max2 < x < Max1)时，这次修改只会影响到最大值，遂把区间和减去(num * (Max1 - x))，再把最大值改成(x).
- 当(x leqslant Max2)时，继续递归到子区间。
综上，当且仅当区间满足条件2的时候，才会被修改。
而对于标记的下传，会发现我们并没有维护lazy标记，而是选择直接下传(Max1)：当子区间和当前区间的(Max1)也满足上述条件2时，我们才会更新子区间。实际上，对于当前区间(now)的最大值和子区间的关系，只会出现上述1,2两种情况。因为在没修改时，(now)的最大、次大值肯定分别大于等于子区间的最大、次大值；当修改的时候，只有满足条件2才会修改，因此次大值并没有改变，也就是说，仍满足(now)的次大值大于等于子区间的次大值，所以下传的时候只会出现条件1,2.
而至于为什么只用下传(Max1)，我是这么想的：因为在区间修改的时候，只会改最大值，而(now)和子区间的最大值是单调的：即如果(x > now.Max1)，那么必有(x > son.Max1)，所以子区间的最大值是否会被修改的前提是(now)的最大值一定被修改了，那么对于子区间来说，用(now.Max1)代替(x)，一定也能考虑到所有修改的情况。所以我们下传的时候传最大值即可，而不用单独维护(lazy)标记。
时间复杂度是(O(m log n))的。
#include<cstdio>
#include<iostream>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<cstdlib>
#include<cctype>
#include<vector>
#include<queue>
#include<assert.h>
#include<ctime>
using namespace std;
#define enter puts("")
#define space putchar(' ')
#define Mem(a, x) memset(a, x, sizeof(a))
#define In inline
#define forE(i, x, y) for(int i = head[x], y; ~i && (y = e[i].to); i = e[i].nxt)
typedef long long ll;
typedef double db;
const int INF = 0x3f3f3f3f;
const db eps = 1e-8;
const int maxn = 1e6 + 5;
In ll read()
{
ll ans = 0;
char ch = getchar(), las = ' ';
while(!isdigit(ch)) las = ch, ch = getchar();
while(isdigit(ch)) ans = (ans << 1) + (ans << 3) + ch - '0', ch = getchar();
if(las == '-') ans = -ans;
return ans;
}
In void write(ll x)
{
if(x < 0) x = -x, putchar('-');
if(x >= 10) write(x / 10);
putchar(x % 10 + '0');
}
In void MYFILE()
{
#ifndef mrclr
freopen(".in", "r", stdin);
freopen(".out", "w", stdout);
#endif
}
int n, m;
struct Tree
{
int l, r;
int Max1, Max2, num;
ll sum;
In Tree operator + (const Tree& oth)const
{
Tree ret; ret.l = l, ret.r = oth.r;
ret.sum = sum + oth.sum;
ret.Max1 = max(Max1, oth.Max1);
if(Max1 > oth.Max1) //看了两种写法，还是分三种情况讨论比较好写，还不容易写错
{
ret.Max2 = max(Max2, oth.Max1);
ret.num = num;
}
else if(Max1 < oth.Max1)
{
ret.Max2 = max(Max1, oth.Max2);
ret.num = oth.num;
}
else
{
ret.Max2 = max(Max2, oth.Max2);
ret.num = num + oth.num;
}
return ret;
}
}t[maxn << 2];
In void build(int L, int R, int now)
{
t[now].l = L, t[now].r = R;
if(L == R)
{
t[now].Max1 = t[now].sum = read();
t[now].Max2 = -1, t[now].num = 1;
return;
}
int mid = (L + R) >> 1;
build(L, mid, now << 1), build(mid + 1, R, now << 1 | 1);
t[now] = t[now << 1] + t[now << 1 | 1];
}
In void Change(int now, int d)
{
t[now].sum -= 1LL * t[now].num * (t[now].Max1 - d);
t[now].Max1 = d;
}
In void pushdown(int now)
{
int tp = t[now].Max1;
if(t[now << 1].Max2 < tp && tp < t[now << 1].Max1) Change(now << 1, tp);
if(t[now << 1 | 1].Max2 < tp && tp < t[now << 1 | 1].Max1) Change(now << 1 | 1, tp);
}
In void update(int L, int R, int now, int d)
{
if(t[now].Max1 <= d) return;
if(t[now].l == L && t[now].r == R && t[now].Max2 < d) return (void)Change(now, d);
pushdown(now);
int mid = (t[now].l + t[now].r) >> 1;
if(R <= mid) update(L, R, now << 1, d);
else if(L > mid) update(L, R, now << 1 | 1, d);
else update(L, mid, now << 1, d), update(mid + 1, R, now << 1 | 1, d);
t[now] = t[now << 1] + t[now << 1 | 1];
}
In int queryMax(int L, int R, int now)
{
if(t[now].l == L && t[now].r == R) return t[now].Max1;
pushdown(now);
int mid = (t[now].l + t[now].r) >> 1;
if(R <= mid) return queryMax(L, R, now << 1);
else if(L > mid) return queryMax(L, R, now << 1 | 1);
else return max(queryMax(L, mid, now << 1), queryMax(mid + 1, R, now << 1 | 1));
}
In ll querySum(int L, int R, int now)
{
if(t[now].l == L && t[now].r == R) return t[now].sum;
pushdown(now);
int mid = (t[now].l + t[now].r) >> 1;
if(R <= mid) return querySum(L, R, now << 1);
else if(L > mid) return querySum(L, R, now << 1 | 1);
else return querySum(L, mid, now << 1) + querySum(mid + 1, R, now << 1 | 1);
}
int main()
{
// MYFILE();
int T = read();
while(T--)
{
n = read(), m = read();
build(1, n, 1);
for(int i = 1; i <= m; ++i)
{
int op = read(), L = read(), R = read();
if(op == 0) update(L, R, 1, read());
else if(op == 1) write(queryMax(L, R, 1)), enter;
else write(querySum(L, R, 1)), enter;
}
}
return 0;
}