C26K:Serial

http://poj.openjudge.cn/practice/C26K/

#include <bits/stdc++.h>
using namespace std;

struct DSU {
    vector<int> fa, sz;
    vector<int> mxOdd, mxEven;
    vector<unsigned char> active;
    priority_queue<pair<int,int>> pq; // {score, root}

    DSU(int n = 0) {
        init(n);
    }

    void init(int n) {
        fa.assign(n, -1);
        sz.assign(n, 0);
        mxOdd.assign(n, 0);
        mxEven.assign(n, 0);
        active.assign(n, 0);
        while (!pq.empty()) pq.pop();
    }

    int find(int x) {
        while (fa[x] != x) {
            fa[x] = fa[fa[x]];
            x = fa[x];
        }
        return x;
    }

    void pushRoot(int r) {
        int score = min(mxOdd[r], mxEven[r]);
        pq.push({score, r});
    }

    void activate(int i, int val) {
        active[i] = 1;
        fa[i] = i;
        sz[i] = 1;
        mxOdd[i] = mxEven[i] = 0;

        // i 是 0-based；原题位置 i+1。
        if (i % 2 == 0) mxOdd[i] = val;
        else mxEven[i] = val;

        pushRoot(i);
    }

    void unite(int a, int b) {
        int ra = find(a);
        int rb = find(b);
        if (ra == rb) return;

        if (sz[ra] < sz[rb]) swap(ra, rb);

        fa[rb] = ra;
        sz[ra] += sz[rb];
        mxOdd[ra] = max(mxOdd[ra], mxOdd[rb]);
        mxEven[ra] = max(mxEven[ra], mxEven[rb]);

        pushRoot(ra);
    }

    int getMaxScore() {
        while (!pq.empty()) {
            auto [score, r] = pq.top();
            if (active[r]) {
                int rr = find(r);
                if (rr == r && min(mxOdd[r], mxEven[r]) == score) {
                    return score;
                }
            }
            pq.pop();
        }
        return 0;
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T;
    cin >> T;

    while (T--) {
        int n;
        cin >> n;

        vector<int> a(n);
        int M = 0;

        long long oddMax = 0, evenMax = 0;

        vector<pair<int,int>> vp;
        vp.reserve(n);

        for (int i = 0; i < n; i++) {
            cin >> a[i];
            M = max(M, a[i]);

            if (i % 2 == 0) oddMax = max(oddMax, (long long)a[i]);
            else evenMax = max(evenMax, (long long)a[i]);

            vp.push_back({a[i], i});
        }

        // 2 块盘
        long long cost2 = oddMax + evenMax;

        // 3 块盘
        sort(vp.begin(), vp.end(), [](const auto& p1, const auto& p2) {
            if (p1.first != p2.first) return p1.first > p2.first;
            return p1.second < p2.second;
        });

        DSU dsu(n);

        long long best3 = (1LL << 60);
        long long cnt3 = 0;

        int ptr = 0;
        while (ptr < n) {
            int v = vp[ptr].first;

            // 此时已经激活的是 ai > v 的位置，所以对应 x = v。
            int g = dsu.getMaxScore();
            long long y = max((long long)v, (long long)g);
            long long cost = (long long)M + v + y;

            if (cost < best3) {
                best3 = cost;
                cnt3 = 1;
            } else if (cost == best3) {
                cnt3++;
            }

            int nxt = ptr;
            while (nxt < n && vp[nxt].first == v) nxt++;

            // 激活 ai == v 的位置，供更小的 x 使用。
            for (int k = ptr; k < nxt; k++) {
                int pos = vp[k].second;
                dsu.activate(pos, v);

                if (pos > 0 && dsu.active[pos - 1]) {
                    dsu.unite(pos, pos - 1);
                }
                if (pos + 1 < n && dsu.active[pos + 1]) {
                    dsu.unite(pos, pos + 1);
                }
            }

            ptr = nxt;
        }

        long long ans = min(cost2, best3);
        long long ways = 0;

        if (cost2 == ans) ways++;
        if (best3 == ans) ways += cnt3;

        cout << ans << ' ' << ways << '\n';
    }

    return 0;
}

这道题目涉及到两个主要策略的比较：使用 2 块硬盘和使用 3 块硬盘的最小代价。

题目逻辑解读

1. 2 块硬盘的代价：

   • 代价 = (奇数下标位置的最大值) + (偶数下标位置的最大值)。
   • 这是最基础的情况，直接遍历一次数组即可得到。

2. 3 块硬盘的代价 (核心难点)：

   • 代价公式为：$M+x+y$，其中 $M$ 是整个数组的最大值，$x$ 和 $y$ 是另外两个选定的值。
   • 算法通过并查集（DSU）和优先队列（堆）来动态维护连通分量。
   • 排序与激活：将数组元素按数值从大到小排序。依次遍历这些值，将其作为 $x$。
   • 连通分量属性：对于并查集中的每个连通分量，维护两个值：mxOdd（该分量中奇数位置的最大值）和 mxEven（该分量中偶数位置的最大值）。
   • 得分定义：一个连通分量的“得分”定义为 min(mxOdd, mxEven)。这意味着在该连通段内，我们可以同时选出一个奇数位的值和一个偶数位的值，且两者中较小的那个至少是这个“得分”。
   • 贪心过程：
     1. 遍历到数值 $v$ 时，先计算当前的 $g=max(\text{所有分量的得分})$。
     2. 此时的 $x=v$，$y=max(v,g)$。
     3. 计算 $cost=M+x+y$ 并更新最小值。
     4. 然后将所有等于 $v$ 的位置“激活”并合并相邻的已激活位置，更新并查集。

---

Python 代码实现

由于 Python 的 heapq 是小顶堆，我们需要存入负值来模拟大顶堆。同时，为了提高效率，建议使用 PyPy 3 运行。

import sys
import heapq

def solve():
    # 使用快速读入
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    it = iter(input_data)
    
    t_cases = int(next(it))
    
    for _ in range(t_cases):
        n = int(next(it))
        a = []
        m_val = 0
        odd_max = 0
        even_max = 0
        
        # 记录数值和位置，用于后续从大到小激活
        vp = []
        for i in range(n):
            val = int(next(it))
            a.append(val)
            if val > m_val: m_val = val
            
            # 计算 2 块硬盘的情况
            if i % 2 == 0:
                if val > odd_max: odd_max = val
            else:
                if val > even_max: even_max = val
            
            vp.append((val, i))
            
        cost2 = odd_max + even_max
        
        # 3 块硬盘的情况
        # 按数值降序排列
        vp.sort(key=lambda x: x[0], reverse=True)
        
        # 并查集初始化
        fa = list(range(n))
        sz = [0] * n
        mx_odd = [0] * n
        mx_even = [0] * n
        active = [False] * n
        pq = [] # 大顶堆 (存储负值): (-score, root)
        
        def find(x):
            while fa[x] != x:
                fa[x] = fa[fa[x]]
                x = fa[x]
            return x

        def get_max_score():
            """获取当前所有连通分量中的最大得分"""
            while pq:
                neg_score, r = pq[0]
                score = -neg_score
                # 懒惰删除：检查 r 是否仍是根，且得分是否未改变
                if active[r] and find(r) == r:
                    current_score = min(mx_odd[r], mx_even[r])
                    if current_score == score:
                        return score
                heapq.heappop(pq)
            return 0

        best3 = float('inf')
        cnt3 = 0
        
        ptr = 0
        while ptr < n:
            v = vp[ptr][0]
            
            # 在激活等于 v 的元素之前，计算当前最优的 y
            g = get_max_score()
            y = max(v, g)
            cost = m_val + v + y
            
            if cost < best3:
                best3 = cost
                cnt3 = 1
            elif cost == best3:
                cnt3 += 1
            
            # 激活所有数值等于 v 的位置
            nxt = ptr
            while nxt < n and vp[nxt][0] == v:
                pos = vp[nxt][1]
                active[pos] = True
                sz[pos] = 1
                if pos % 2 == 0:
                    mx_odd[pos] = v
                    mx_even[pos] = 0
                else:
                    mx_even[pos] = v
                    mx_odd[pos] = 0
                
                # 检查左右邻居并合并
                for neighbor in [pos - 1, pos + 1]:
                    if 0 <= neighbor < n and active[neighbor]:
                        ra = find(pos)
                        rb = find(neighbor)
                        if ra != rb:
                            # 按大小合并
                            if sz[ra] < sz[rb]: ra, rb = rb, ra
                            fa[rb] = ra
                            sz[ra] += sz[rb]
                            if mx_odd[rb] > mx_odd[ra]: mx_odd[ra] = mx_odd[rb]
                            if mx_even[rb] > mx_even[ra]: mx_even[ra] = mx_even[rb]
                            pos = ra # 更新当前根
                
                # 更新根节点的得分到堆
                root = find(pos)
                score = min(mx_odd[root], mx_even[root])
                heapq.heappush(pq, (-score, root))
                nxt += 1
            ptr = nxt
            
        # 最终比较两种方案
        ans = min(cost2, best3)
        ways = 0
        if ans == cost2: ways += 1
        if ans == best3: ways += cnt3
        
        sys.stdout.write(f"{ans} {ways}\n")

if __name__ == "__main__":
    solve()

---

解读与要点

1. 并查集的动态维护： 该算法之所以有效，是因为它将问题转化为了“寻找满足条件的连续子段”。并查集可以动态地合并相邻节点，并在 $O(\alpha (n))$ 时间内维护子段内奇偶位置的最大值。

2. 堆的懒惰删除 (Lazy Deletion)： 当两个集合合并时，旧的根节点的得分信息依然留在堆中。我们不需要手动去堆里寻找并删除它，而是在 get_max_score 时，通过检查 find(r) == r 和 score 的一致性来剔除失效的信息。这是处理动态优先级问题的常见高效手段。

3. 计算 y 的逻辑： $y=max(v,g)$。这里 $v$ 是当前遍历到的值（作为 $x$），而 $g$ 是之前已经激活（比 $v$ 更大或相等）的元素所形成的连通分量中，能够提供的最大“奇偶对”中的较小值。

4. Python 性能提示：

   • 在处理 $N={10}^5$ 规模且包含大量堆操作和并查集操作的题目时，CPython 可能会超时。建议使用 PyPy 3，它对这类循环和对象操作有极大的加速。
   • 使用 sys.stdin.read().split() 是一次性读取所有数据的最高效方式。