P5044 [IOI2018] meetings 会议

· · 题解

做法思路

首先区间 [L,R] 的笛卡尔树结构是在区间内最大值处 m 劈开，[L,m),(m,R] 两部分的笛卡尔树分别作为 m 的左右儿子拼起来的。而 [L,m),(m,R] 分别是 [L,n] 的笛卡尔树上 m 的左儿子、[1,R] 的笛卡尔树上 m 的右儿子。所以正着倒着各做一遍，考察每个前缀和每个后缀的笛卡尔树，对每个询问分别处理将会议地点放在询问区间最大值的右侧和左侧的最小花费，这是区间 RMQ 类问题的经典处理手法。

从左到右依次考察每个山 i，维护 [1,i] 的递减单调栈，即大根笛卡尔树上，从根不断走向右儿子，经过的结点编号形成的序列。对于 j\in[1,i] 设 r(j) 为单调栈中在 j 右侧的第一个位置，容易发现随着 i 向右移动，如果 r(j) 不变，[1,i] 内的所有人全部去 j 开会的代价就是以 H_{r(j)} 为斜率的关于 i 的同一个一次函数，设为 f_j(i)。

设单调栈为 q，因为对于所有 j\in(q_{t-1},q_t]，都有 r(j)=t，即 f_j(i) 的斜率都相等，所以自然地考虑在 q_t 维护这些 j 中 f_j 截距最小者。i 向右移动时，对于每个应当从单调栈中弹出的 q_t，[1,i-1] 中所有点都到某个 j 的代价最小值可以通过 q_t 处维护的一次函数直接求出，而 i 到每个 j 的代价均为 H_i。

区间 [L,R] 内所有人到 (m,R] 中某个位置开会的最小代价，等于 i 扫描到 R 时，所有 q_t（t\ge r(m+1)）上维护的一次函数在 R 处的最小值（这是 [1,R] 内所有人到 (m,R] 中某个位置开会的最小代价），减去 [1,m) 内所有人到 m 开会的代价（这个值可以递推求出，且因为 m 在笛卡尔树上是 [m,R] 内所有点的祖先，所以 [1,m) 内所有人到 [m,R] 中任意一个点开会的代价都是相等的），再加上 [L,m) 到 m 开会的代价。

维护一次函数

现在需要维护初始为空的一次函数序列，在末尾 O(n) 次加删，查询一段某个后缀中所有函数在 x 处的取值的最小值。保证每次修改后该序列上函数的斜率递减（并非每次插入函数的斜率单调递减），查询的 x 单调递增。

维护原序列的一个子序列 {s_m}，对于上一次询问的 x，满足 s_1(x)<s_2(x)<\cdots<s_m(x)，且若有两个函数 f 在原序列中在 g 之前，f\not\in s 中而 g\in s 中，那么 f(x)\ge g(x)。

插入某函数 t 时，不断弹出 s 末尾在 x 处已经大于等于 t 的元素，因为这些函数斜率大于等于 t，在 x 处不优将来也不会优；如果 s 没有被弹空，将 s 末尾元素和 t 两个一次函数相交的位置标记在数轴上，称为一次 beat 事件。最后将 t 插入 s 末尾。

查询时扫描上一次查询的 x 到此次查询的 x 间标记的所有 beat 事件，删除被 t beat 的前驱，并将 t beat 其新前驱的时刻标记在数轴上。最后查询 s 中编号在查询的后缀内第一个函数在 x 处的取值即可。正确性显然。

删除时如果被删除元素在 s 中，则将其弹出。注意，这里为什么不会出现 p beat q，p 被弹出后查不到 q 的情况呢？这里依赖原问题的性质，如果 i 位置的加入导致单调栈上 p 被弹出，[1,i] 中所有点到新单调栈上 i 处维护的一次函数的决策点，一定不劣于 [1,i] 中所有点到旧单调栈上 p 处维护的一次函数的决策点；而 p 早在 i 之前就不劣于 q 了，之后也不劣于 q，所以如果 q 被 beat，以后一定用不到 p。

O(n)-O(1) RMQ

RMQ 即区间查询 \max。按照字长 w=64 分块，块内预处理前缀、后缀 max，对 \frac nw 个块内最大值预处理 ST 表。查询区间如果包含至少一个块间分界线，若干连续整块用 ST 表查询最大值，散块前后缀直接查询。

对每个块预处理每个前缀的 \max 单调栈（每个单调栈用一个长为 w 的 01 序列描述块内每个位置是否在单调栈里），若询问 [l,r] 被某个块 [L,R] 包含，查询 l 之后第一个在 [L,r] 对应的单调栈中的位置，常数次位运算和一次 __builtin_clz/ctz 就可以解决。

时间复杂度 O(\frac{n\log n}w)-O(1)，常数很小。

序列并查集

维护一次函数时，我们需要快速维护一个初始全 1 的 01 序列，每次单点把 1 改成 0，查询某个位置前面最后一个 1 和某个位置后面第一个 1 的位置。序列长度和修改次数同阶。

将一个位置和它前面一段极长的 0 对应到并查集上的一个连通块，单点修改形如合并两个相邻的区间对应的连通块，查询后继 1 位置就是并查集查询连通块根。按秩合并+路径压缩复杂度为 O(n\alpha(n,n))。

按照字长 w=64 分块，每个块对应并查集的一个元素，将极长连续全 0 段对应到并查集上的一个连通块。如果一个块在某次修改后变为全 0 就进行只多两次连通块合并。查询只需常数次位运算、__builtin_clz/ctz 和一次查询连通块根。

根据 Tarjan 的分析，总时间复杂度为

O\left(n\alpha\left(n,\frac nw\right)\right)=O(n\min\{i\ge1\mid A(i,w)\ge \log n\})=O(n)

注意，这样的并查集必须启发式合并（按秩合并或按照 size 合并）+路径压缩才能做到正确的复杂度。

还有一种不常规的写法，合并两个区间时暴力将较小区间的父亲暴力改成较大区间的父亲的根，时间复杂度为 O(\frac{n\log n}w)。

至此，我们已经线性解决了这个问题。以下这份代码截止 2025.2.8 仍然是 UOJ 和洛谷的最优解。

#include<algorithm>
#include<iostream>
#include<cstring>
#include<numeric>
#include<vector>
#include<tuple>
#define ctz __builtin_ctzll
#define clz __builtin_clzll
using ull = unsigned long long;

char bf[20000000], *bp = bf;
void inline rd(auto&x) {
    for (x=0; !isdigit(*bp); bp++);
    for (; isdigit(*bp); bp++) x = x*10+(*bp^48);
}
const int N = 7.5e5, LG = 17;
int n, m, tp, o[N], a[N], l[N], r[N], mx[N], q[N], p[N], bl[N], br[N];
unsigned long long b[N], ms[N+1], pr[N], sf[N+1], st[LG][N/64];
long long ans[N], c[N], f[N];
std::vector<int>rg[N+1];
std::vector<std::tuple<int, int, int>>qr[N];
bool inline ck(int u) { return ms[u>>6]>>(u&63)&1; }
void inline gf(int&u) { while (p[u] != u) u = p[u] = p[p[u]]; }
int tl(int u) {
    if (!~u) return -1;
    if (auto x=ms[u>>6]&-1ull>>(~u&63)) return (u|63)^clz(x);
    if (!(u>>=6)) return -1;
    if (ms[--u]) return u<<6|63^clz(ms[u]);
    return gf(u), ~bl[u] ? bl[u]<<6|63^clz(ms[bl[u]]) : -1;
}
int tr(int u) {
    if (auto x=ms[u>>6]&-1ull<<(u&63)) return u&~63|ctz(x);
    if (ms[u=(u>>6)+1]) return u<<6|ctz(ms[u]);
    return gf(u), br[u]<<6|ctz(ms[br[u]]);
}
void md(int u) {
    if (ms[u>>6]&=~(1ull<<(u&63))) return;
    auto mg = [](int x, int y) {
        if (gf(x), gf(y), br[x]-bl[x] <= br[y]-bl[y])
            p[x] = y, bl[y] = bl[x];
        else p[y] = x, br[x] = br[y];
    };
    u >>= 6, p[u] = u, bl[u] = u-1, br[u] = u+1;
    if (u && !ms[u-1]) mg(u-1, u);
    if (u+1<n>>6 && !ms[u+1]) mg(u, u+1);
}
void sv() {
    for (int i=0, j=0, t; i<n; qr[i].clear(), rg[i].clear(), i++) {
        for (c[i]=1e18; ~tp && b[q[tp]]<=b[i]; tp--)
            if (c[i] = std::min(c[i], (a[q[tp]]-a[i])*(i-1ll)+c[q[tp]]), ck(q[tp])) md(q[tp]);
        auto upd = [&](int x) { int y = x;
            while (~(y=tl(y-1)) && 1ll*(a[x]-a[y])*i+c[x]-c[y]<=0) md(y);
            if (~y && a[x]!=a[y]) rg[std::min((c[y]-c[x])/(a[x]-a[y])+1, 1ll*n)].push_back(x);
        };
        c[i] = std::min(c[i], f[i]=~tp?f[q[tp]]+1ll*q[tp]*a[q[tp]]-1ll*a[i]*q[tp]:a[i]);
        for (upd(q[++tp]=i); int x : rg[i]) if (ck(x)) upd(x);
        for (; j<m && r[o[j]]==i; j++) if (mx[o[j]] < i) t = tr(mx[o[j]]+1),
            ans[o[j]] = std::min(ans[o[j]], 1ll*a[t]*i-a[mx[o[j]]]*(l[o[j]]-1ll)+c[t]-f[mx[o[j]]]);
    }
}
int main() {
    fread(bf, 1, sizeof bf, stdin), rd(n), rd(m);
    for (int i=0; i<n; i++) rd(a[i]), b[i] = 1ull*a[i]<<32|i;
    for (int i=0; i<n; i++) pr[i] = i&63?std::max(pr[i-1], b[i]):b[i];
    for (int i=n; i--; sf[i] = ~i&63?std::max(sf[i+1], b[i]):b[i], ms[i]|=1ull<<(i&63))
        for (ms[i]=~i&63?ms[i+1]:0; ms[i] && a[ctz(ms[i])+(i&~63)]<a[i];) ms[i] -= ms[i]&-ms[i];
    for (int i=0; i<n>>6; i++) st[0][i] = sf[i<<6];
    for (int i=1, j; 1<<i<=n>>6; i++) for (j=0; j+(1<<i)<=n>>6; j++)
        st[i][j] = std::max(st[i-1][j], st[i-1][j+(1<<i-1)]);
    for (int i=0, u, v, t; i<m; i++) if (rd(l[i]), rd(r[i]), (u=l[i]+64>>6)<(v=r[i]>>6))
        t = std::__lg(v-u), mx[i] = std::max({sf[l[i]], st[t][u], st[t][v-(1<<t)], pr[r[i]]});
    else mx[i] = u==v?std::max(sf[l[i]], pr[r[i]]):r[i]-clz(ms[l[i]]<<(~r[i]&63));
    for (int i=0; i<m; i++) ans[i] = a[mx[i]]*(r[i]-l[i]+1ll);
    std::iota(o, o+m, 0), std::sort(o, o+m, [](int i, int j){return r[i]<r[j];});
    memset(ms, -1, n+8>>3), tp = -1, sv(), std::reverse(a, a+n), std::reverse(b, b+n);
    for (int i=0; i<m; i++) l[i] = n-l[i]-1, r[i] = n-r[i]-1, mx[i] = n-mx[i]-1, std::swap(l[i], r[i]);
    std::sort(o, o+m, [](int i, int j){return r[i]<r[j];}), memset(ms, -1, n+8>>3), tp = -1, sv();
    for (int i=0; i<m; i++) std::cout << ans[i] << '\n';
}