会议最低成本题解

一、问题核心分析

题目要求在区间 ([L_j, R_j]) 中选择一个举办地 (x)，使得所有参会者的成本之和最小。参会者成本定义为从所在山 (y) 到 (x) 路径上的最大山高，总成本是所有参会者成本的总和。

核心难点在于：

1. 路径最大高度的计算具有区间依赖性，直接枚举每个 (x) 计算成本会导致 (O(QN)) 的时间复杂度，无法满足 (N, Q \leq 7.5 \times 10^5) 的数据规模。
2. 需找到区间内最优的 (x)，使得总成本最小，而最优 (x) 通常与区间内的“支配性高点”相关。

关键观察：

• 对于区间 ([L, R])，最优举办地 (x) 大概率是区间内的某个“极大值点”（即比左右相邻山都高的点），因为极大值点能覆盖更大范围的低海拔区域，降低整体最大高度的贡献。
• 利用单调栈、RMQ（区间最大值查询）、并查集等数据结构，可高效维护和查询区间内的极大值点及成本计算所需的信息。

二、算法原理

1. 预处理与区间最大值查询（RMQ）

• 构建 RMQ 结构，支持 (O(1)) 时间查询任意区间 ([L, R]) 内的“字典序最大”极大值点（用 (a[i] \times N + i) 作为键，确保高度相同时索引更小的优先），该点作为初始候选最优举办地。
• RMQ 采用分块优化，将数组分为 64 元素一块，预处理每块的前缀最大值、后缀最大值、块内最大值及单调栈掩码，实现高效查询。

2. 单调栈维护极大值点

• 用单调栈维护当前遍历过程中的极大值点（严格递减栈），栈中元素的高度从栈底到栈顶逐渐减小。
• 当新元素加入时，弹出栈中所有高度小于当前元素的点，这些点的最优覆盖范围被当前元素部分取代，同时计算当前元素的成本相关参数。

3. 成本计算的线性表示

• 对于每个极大值点 (i)，其覆盖的区间内，成本可表示为线性函数 (li[i] = (h_i, c_i))，即对于区间内的位置 (x)，成本贡献为 (h_i \times x + c_i)（通过前缀和预处理推导得出）。
• 利用线性函数的特性，可快速比较不同极大值点在某区间内的成本优劣，找到最优覆盖。

4. 并查集维护有效极大值点

• 用并查集（带位运算优化）维护当前有效的极大值点，当某个极大值点被新点覆盖时，将其从有效集合中删除，确保查询时只遍历有效点，减少冗余计算。

5. 双向遍历处理

• 由于成本计算具有左右对称性，先正向遍历数组处理所有查询，再将数组反转后反向遍历，确保覆盖所有可能的最优举办地，最终取两次遍历的最小值作为答案。

三、完整代码

#include <bits/stdc++.h>
#define pb push_back
#define sz(a) ((int)a.size())
#define re return
#define all(a) a.begin(),a.end()
#define rept(i,a,b) for(int i=(a);i<(b);i++)
#define rep(i,a) rept(i,0,a)
#define vi vector<int>
#define pii pair<int,int>
#define F first
#define S second
#define int long long
#define il inline
using namespace std;
const int MOD = 998244353, INF = 1000000000000000000;

template<typename T>inline void Mx(T &a, T b) { a = max(a, b); }
template<typename T>inline void Mi(T &a, T b) { a = min(a, b); }

void FILEIO(string s) {
    freopen((s + ".in").c_str(), "r", stdin);
    freopen((s + ".out").c_str(), "w", stdout);
}

const int N = 751005, L = 15, E = (N >> 6) + 2;
#define ull unsigned int

struct RMQ {
    int n, bl, *a, st[E][L], pfm[N], sfm[N], stk[64], tp;
    ull msk[N];
    void pre(int _n, int *_a) {
        a = _a;
        bl = (_n + 63) >> 6;
        n = bl << 6;
        rept(i, _n, n)a[i] = -INF;
        rep(i, bl) {
            int cr = i << 6, tmp = -INF;
            rep(j, 64)Mx(tmp, a[j + cr]), pfm[j + cr] = tmp;
            tmp = -INF;
            for (int j = 63; ~j; j--) Mx(tmp, a[j + cr]), sfm[j + cr] = tmp;
            st[i][0] = tmp;
            ull cmk = tp = 0;
            rep(j, 64) {
                while (tp && a[j + cr] >= a[stk[tp - 1] + cr]) cmk ^= 1ull << stk[--tp];
                cmk ^= 1ull << j;
                stk[tp++] = j;
                msk[j + cr] = cmk;
            }
        }
        rep(i, L - 1)rep(j, bl - (2 << i) + 1) st[j][i + 1] = max(st[j][i], st[j + (1 << i)][i]);
    }
    il int blk(int l, int r) {
        if (l > r) re - INF;
        int d = __lg(r - l + 1);
        re max(st[l][d], st[r - (1 << d) + 1][d]);
    }
    il int calc(int l, int r) {
        int cl = l >> 6, cr = r >> 6;
        if (cl < cr) re max(max(sfm[l], pfm[r]), blk(cl + 1, cr - 1));
        re a[__builtin_ctzll(msk[r] >> (l & 63)) + l];
    }
} T;

struct dsu {
    int fa[E];
    ull lp[E];
    il void pre(int n) {
        n++;
        rep(i, (n >> 6) + 2) { lp[i] = -1ull; fa[i] = i; }
    }
    il void era(int x) {
        lp[x >> 6] ^= 1ull << (x & 63);
        if (!lp[x >>= 6]) fa[x] = x + 1;
    }
    int fi(int x) { re(x == fa[x]) ? x : (fa[x] = fi(fa[x])); }
    il int gt(int x) {
        int xr = lp[x >> 6] >> (x & 63);
        if (!xr) { int nx = fi((x >> 6) + 1); re(nx << 6) + __builtin_ctzll(lp[nx]); }
        re x + __builtin_ctzll(xr);
    }
} D;

int n, q, a[N], b[N], tp, rt;
int ql[N], qm[N], qr[N], ans[N];
vi pc[N];
pii stk[N], li[N];
int tol[N], tor[N], prf[N];
vector<pii>bt[N];

il int nxt(pii x, pii y) {
    if (x.F == y.F) { if (x.S < y.S) re n; re 0; }
    re min(n, 1 + (y.S - x.S) / (x.F - y.F));
}

il void l_era(int x) {
    tor[tol[x]] = tor[x];
    tol[tor[x]] = tol[x];
    D.era(x);
}

il void l_add(int x, int y) {
    tol[tor[x]] = y;
    tor[y] = tor[x];
    tol[y] = x;
    tor[x] = y;
}

void solve() {
    rep(i, q)pc[qr[i]].pb(i);
    stk[0] = {INF, -1};
    tp = 1;
    tol[n] = n + 1;
    tor[n + 1] = n;
    D.pre(n);
    rep(i, n) {
        int tmp = INF;
        while (a[i] > stk[tp - 1].F) {
            int la = stk[--tp].S;
            if (tol[n] == la) l_era(la);
            tmp = min(tmp, li[la].F * (i - 1) + li[la].S + a[i]);
        }
        prf[i] = ((tp > 1) ? prf[stk[tp - 1].S] : 0) + a[i] * (i - stk[tp - 1].S);
        Mi(tmp, prf[i]);
        stk[tp++] = {a[i], i};
        li[i] = {a[i], tmp - a[i] * i};
        if (tol[n] < n) bt[max(i, nxt(li[tol[n]], li[i]))].pb({tol[n], i});
        l_add(tol[n], i);
        rep(j, sz(bt[i])) {
            pii pp = bt[i][j];
            if (D.gt(pp.F) == pp.F && D.gt(pp.S) == pp.S) {
                l_era(pp.F);
                if (tol[pp.S] < n) bt[max(i, nxt(li[tol[pp.S]], li[pp.S]))].pb({tol[pp.S], pp.S});
            }
        }
        for (int j : pc[i]) {
            int lx = qm[j];
            int add = -prf[lx] + a[lx] * (lx - ql[j] + 1);
            int nxp = D.gt(lx + 1);
            if (nxp <= i) Mi(ans[j], li[nxp].F * i + li[nxp].S + add);
        }
    }
}

void run() {
    cin >> n >> q;
    rep(i, n) { cin >> a[i]; b[i] = a[i] * n + i; }
    T.pre(n, b);
    rep(i, q) {
        int l, r;
        cin >> l >> r;
        ql[i] = l;
        qm[i] = T.calc(l, r) % n;
        ans[i] = a[qm[i]] * (r - l + 1);
        pc[qr[i] = r].pb(i);
    }
    solve();
    rep(i, n)pc[i].clear();
    rep(i, n + 1)bt[i].clear();
    rep(i, q) {
        ql[i] = n - 1 - ql[i];
        qm[i] = n - 1 - qm[i];
        qr[i] = n - 1 - qr[i];
        swap(ql[i], qr[i]);
        pc[qr[i]].pb(i);
    }
    reverse(a, a + n);
    solve();
    rep(i, q)cout << ans[i] << "\n";
}

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int T = 1;
    while (T--) run();
    re 0;
}

四、代码关键步骤解析

1. RMQ 预处理与区间极大值查询

• RMQ 结构体通过分块处理数组，预处理每块的前缀/后缀最大值、块内最大值及单调栈掩码，支持 (O(1)) 时间查询任意区间的“字典序最大”极大值点（高度优先，索引次之）。
• 该极大值点作为初始候选举办地，其成本为 a[qm[i]] * (r - l + 1)（假设所有参会者成本均为该极大值点高度）。

2. 单调栈与线性成本函数构建

• solve 函数中，单调栈 stk 维护当前有效极大值点（严格递减）。对于每个新点 i，弹出栈中所有高度更小的点，计算这些点被覆盖后的成本贡献。
• 每个极大值点 i 对应的线性成本函数 li[i] = (h_i, c_i)，其中 c_i = tmp - a[i] * i，tmp 是该点覆盖范围内的最小成本前缀和推导值。

3. 并查集维护有效极大值点

• dsu 结构体（带位运算优化）维护当前未被覆盖的有效极大值点。当某个极大值点被新点覆盖时，通过 l_era 函数将其从有效链表和并查集中删除，确保后续查询仅遍历有效点。

4. 双向遍历优化

• 第一次正向遍历处理所有查询后，将数组反转，调整查询区间的左右边界，进行第二次反向遍历。这是因为最优举办地可能在区间的右侧，正向遍历未充分覆盖，反向遍历可弥补该缺陷，确保找到全局最小值。

5. 查询处理与答案更新

• 所有查询按右边界 r 分组存储在 pc 数组中，遍历到 r 时处理对应查询。通过 D.gt 找到区间内的有效极大值点，计算其对应的总成本并更新答案。

五、复杂度分析

• 时间复杂度：(O(N + Q + N \log N + Q \log N))。RMQ 预处理为 (O(N))，单调栈遍历为 (O(N))，并查集操作均为近似 (O(1))，查询处理为 (O(Q))，双向遍历不改变整体复杂度。
• 空间复杂度：(O(N + Q))。用于存储数组、栈、并查集、查询分组等数据结构，可满足 (N, Q \leq 7.5 \times 10^5) 的内存约束。