前言
题目链接：洛谷。
感觉 T4 比 T3 水，虽然我都没做出来。
题意简述
给定 \(1 \sim n\) 的排列 \(a\) 和 \(m\) 个区间 \([l_i, r_i]\)。定义值域区间 \([L, R]\) 的价值为 \(\operatorname{val}([L, R]) \operatorname{:=} \max \limits_{i = 1}^m \sum\limits_{k = l_i}^{r_i}[L \le a_k \le R]\)。求将 \([1, n]\) 划分为若干不交的区间的价值之积的最大值，对 \(998244353\) 取模。
题目分析
划分值域，其实一个序列上的问题，不妨考虑 DP。设 \(f_i\) 表示 \([1, i]\) 的值域区间已经被划分成若干值域区间的价值的最大积。特别地，不妨令 \(f_0 = 1\)。
接下来考虑转移。考虑求 \(f_i\)，可以不进行任何操作，直接继承 \(i - 1\)。也可以进行一次划分，那么令新划分的值域区间为 \([j, i]\)，则有转移：
\[f_i = \max _ {j=1} ^ {i} \Big \lbrace f_{j - 1} \cdot \operatorname{val}([j, i]) \Big \rbrace \]具体地，我们让 \(j\) 从 \(i\) 开始向左扫，同时维护 \(m\) 个区间的桶，对于当前 \([j, i]\) 扩展出的新的一个值 \(j\)，我们找到 \(a_p = j\) 的位置 \(p\)，让 \(l_i \leq p \leq r_i\) 的区间的桶计数加一，转移就很简单了。
另外，由于同时要最大值和取模后的值，套路化地，记真实值为 \(x\)，我们只用维护 \((\log x, x \bmod M)\) 的二元组，由对数性质，比较最值是取前者，答案则是后者。易知 double 精度足够。
这样做的时间复杂度是 \(\Theta(n^2m)\)，怎么优化呢？不妨输出一下最优决策时的相关信息，发现 \(\operatorname{val}([j, i]) \in \lbrace 2, 3 \rbrace\)，或者可能在 \(i\) 较小时有 \(1\)，这是为什么呢？理解起来很简单，因为我们在价值 \(>3\) 的时候，总是能够把 \([j, i]\) 划分成两个区间，使得它们价值之积不劣于之前的价值。读者自证不难。
于是，DP 只能决策一个价值为 \(2\) 或 \(3\) 的区间。现在的问题就是对于每一个 \(i\)，找到最后一个 \(j\)，使 \(\operatorname{val}([j, i]) = 2\)，再用相同算法求得 \(\operatorname{val}([j, i]) = 3\) 的 \(j\)，最后就能 \(\Theta(n)\) DP 了。
发现，区间越大，其价值越大，要维护区间价值为 \(2 / 3\)，类似于滑动窗口，可以用双指针预处理。时间复杂度降为了 \(\Theta(nm)\)，瓶颈在于预处理。还有没有更好的处理方式呢？我们发现，双指针已经无法优化了，现在迫切需要一个能维护这 \(m\) 个桶的数据结构，支持查询全局最值、给能够包含某一个点的区间对应的桶加。
这并不套路。全局最值通常很好维护，难点再做一些毫无规律的单点加。但是注意到区间对我们来说是没有先后顺序之分的，不妨排个序。至于关键字，为了服务我们的目的，不妨按照左端点先排一次序。现在，我们已经能够通过二分快速缩小我们想要做单点加的范围了。我们只需要在这些左端点 \(l_i \leq p\) 的区间中，找到右端点 \(r_i \geq p\) 的区间，对这些区间做单点加。
可是，右端点不是单调的，我们还是无法便捷地操作。有没有什么方法使得在左端点单增的同时，右端点也单增呢？即，不存在一个区间包含另一个区间的情况。这似乎意味着我们必须要删除一些区间。发现，对于 \(a\) 包含 \(b\) 的情况，我们完全可以删除被包含的 \(b\) 而不影响答案，应为如果某一个值域区间 \([L, R]\) 的 \(\operatorname{val}\) 在 \(b\) 取到了 \(\max\)，在 \(a\) 一定不劣。预处理删除是 naive 的。于是，我们就能做到左右端点分别单增。
这就意味着，我们能够迅速地定位一段区间，并对这段区间的每一个桶做单点加。等等！这不就退化到区间加了吗，结合所求的最值，直接上一棵线段树就行了。
至此，我们通过了这道题，时间复杂度：\(\Theta((n + m) \log m)\)。
当然，有些常数优化，例如排序值域很小，直接用桶；对于每个点，我们可以双指针处理出要区间加的范围。于是乎，卡脖子的瓶颈就在于线段树了。具体请看代码。
代码
以及正解，妥妥地跑到了（除了出题人之前交的）Rank 1。
#include <cstdio>
using namespace std;
const int MAX = 1 << 26;
char buf[MAX], *p = buf;
#define getchar() *p++
#define isdigit(ch) (ch >= '0' && ch <= '9')
inline void read(int &x) {
x = 0; char ch = getchar();
for (; !isdigit(ch); ch = getchar());
for (; isdigit(ch); x = (x << 3) + (x << 1) + (ch ^ 48), ch = getchar());
}
constexpr const double lg2 = 0.693147180559945286226763982995180413126945495605468750000000000736520;
constexpr const double lg3 = 1.098612288668109782108217586937826126813888549804687500000000000736520;
constexpr inline int max(int a, int b) { return a > b ? a : b; }
const int N = 300010;
const int mod = 998244353;
int n, m, mxR[N];
int val[N], whr[N];
struct Segment {
int L, R;
} line[N];
int two[N], san[N];
struct node {
double sum;
int val;
constexpr node(double s = 0, int v = 0) : sum(s), val(v) {}
inline friend bool operator < (const node & a, const node & b) {
return a.sum < b.sum;
}
inline friend node operator + (const node & a, const node & b) {
return node(a.sum + b.sum, 1ll * a.val * b.val % mod);
}
inline friend node max(const node & a, const node & b) {
return a < b ? b : a;
}
} dp[N];
constexpr node TWO(lg2, 2), SAN(lg3, 3);
struct Segment_Tree {
#define lson (idx << 1 )
#define rson (idx << 1 | 1)
struct node {
int l, r, lazy, mx;
} tree[N << 2];
void build(int idx, int l, int r) {
tree[idx] = {l, r, 0, 0};
if (l == r) return;
int mid = (l + r) >> 1;
build(lson, l, mid), build(rson, mid + 1, r);
}
inline void pushtag(int idx, int v) {
tree[idx].mx += v;
tree[idx].lazy += v;
}
inline void pushdown(int idx) {
if (!tree[idx].lazy) return;
pushtag(lson, tree[idx].lazy);
pushtag(rson, tree[idx].lazy);
tree[idx].lazy = 0;
}
void modify(int idx, int l, int r, int v) {
if (l <= tree[idx].l && tree[idx].r <= r) return pushtag(idx, v);
pushdown(idx);
if (l <= tree[lson].r) modify(lson, l, r, v);
if (r >= tree[rson].l) modify(rson, l, r, v);
tree[idx].mx = max(tree[lson].mx, tree[rson].mx);
}
#undef lson
#undef rson
} yzh; // yzh i love you!
inline int getmx() {
return yzh.tree[1].mx;
}
int LEFT[N], RIGHT[N];
// 第一个右端点不小于 whr[i] 的位置
// 最后一个左端点不大于 whr[i] 的位置
inline void add(int i, int v) {
i = whr[i];
if (LEFT[i] <= RIGHT[i]) yzh.modify(1, LEFT[i], RIGHT[i], v);
}
signed main() {
fread(buf, 1, MAX, stdin);
read(n), read(m);
for (int i = 1; i <= n; ++i) read(val[i]), whr[val[i]] = i;
for (int i = 1, L, R; i <= m; ++i) read(L), read(R), mxR[L] = max(mxR[L], R);
m = 0;
for (int i = 1, curR = 0; i <= n; ++i)
if (mxR[i] > curR) {
line[++m] = {i, mxR[i]};
curR = mxR[i];
}
for (int i = 1; i <= n; ++i) {
LEFT[i] = LEFT[i - 1];
while (line[LEFT[i]].R < i) ++LEFT[i];
}
RIGHT[n + 1] = m;
for (int i = n; i >= 1; --i) {
RIGHT[i] = RIGHT[i + 1];
while (line[RIGHT[i]].L > i) --RIGHT[i];
}
yzh.build(1, 1, m);
for (int i = 1; i <= n; ++i) {
add(i, 1);
if (getmx() < 2) continue;
two[i] = two[i - 1];
if (!two[i]) two[i] = 1;
while (true) {
add(two[i]++, -1);
if (getmx() < 2) {
add(--two[i], 1);
break;
}
}
}
yzh.build(1, 1, m);
for (int i = 1; i <= n; ++i) {
add(i, 1);
if (getmx() < 3) continue;
san[i] = san[i - 1];
if (!san[i]) san[i] = 1;
while (true) {
add(san[i]++, -1);
if (getmx() < 3) {
add(--san[i], 1);
break;
}
}
}
dp[0].val = 1;
for (int i = 1; i <= n; ++i) {
dp[i] = dp[i - 1];
if (two[i]) dp[i] = max(dp[i], dp[two[i] - 1] + TWO);
if (san[i]) dp[i] = max(dp[i], dp[san[i] - 1] + SAN);
}
printf("%d", dp[n].val);
return 0;
}
后记
遇到最值取模，不一定是存在一种构造的方法，能够保证算出最值，然后在算法过程中取模，也可能是取对数 DP 等决策。
若干区间，每次给出一个点，对包含这个点的所有区间操作，可以尝试去掉包含的区间，这样就能二分出连续的一段，就能区间操作了。
标签：node,1.5,val,idx,int,题解,tree,区间,莫队 From： https://www.cnblogs.com/XuYueming/p/18370812