题解：P17543 [JAG 2026 Summer Camp #2] Deque Bracket Optimization

· · 题解

先考虑只有 3 操作怎么做。

这是一个经典反悔贪心问题。

我们动态维护当前最优的左、右括号集合 S, T。每次从 [1, i-2] 扩展到 [1, i] 时：

由于 i 只能作为右端点，我们只有这两种决策：

手玩一些简单情况，或者简单分讨一下可以发现，这样每一步到达的都是最优情况。场上猜到这个就可以了，但场外我们还是要证一下的。

具体来讲，当前的状态对应的是 [1, i] 中的恰好 (i/2) 个作为左括号。如果有一个左括号出现在 (i-1)，那么它和 i 形成匹配，这种情况已经被前面的决策覆盖掉了。否则，(i-1), i 都是右端点，不难发现其实也没有比上面所述的“决策”更好的方案。

由于向左向右扩展都没什么区别，我们会做 3 操作之后，就会 1 操作了。

现在关键的问题是 2 操作很难处理。

有一个很神仙的想法，我们同时维护 [l, r] 和 [l+1, r-1] 的答案，记作 X, Y。

对于每次 1, 3 操作，将这两个区间同步扩展。

对于 2 操作，我们直接让 Y 继承之前的 X；而新的 X 就是分别在旧 Y 的基础上从左右两边分别加入两个数。这可以被 1, 3 操作表示出来。

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

const int N = 2e6 + 5;
int x, y, opt, q, a[N], head, tail;
long long sum;


struct node
{
    long long ans = 0;
    multiset<int> stt, ntt;

    void opt(int id, int x, int y)
    {
        if(id == 1)
        {
            if(stt.empty())
            {
                stt.insert(y); ans += y;
                ntt.insert(x);
            }
            else
            {
                int mn = *stt.begin(); 
                if(ans - mn + x + y <= ans + y)
                {
                    stt.insert(y), ans += y;
                    ntt.insert(x);
                }
                else
                {
                    stt.insert(x);
                    stt.insert(y);

                    ntt.insert(mn);
                    stt.erase(stt.find(mn));

                    ans = ans - mn + x + y;
                }
            }
        }
        else if(id == 3)
        {
            if(stt.empty())
            {
                stt.insert(x); ans += x;
                ntt.insert(y);
            }
            else
            {
                int mx = *--ntt.end(); 

                if(ans + mx <= ans + x) // (x, y)
                {
                    stt.insert(x), ans += x; ntt.insert(y);
                }
                else
                {
                    stt.insert(mx);
                    ntt.erase(ntt.find(mx));

                    ntt.insert(x); ntt.insert(y);
                    ans += mx;
                }
            }
        }
    }
} X, Y;

void solve()
{
    head = 1e6, tail = head - 1;
    X.stt.clear(), X.ntt.clear();
    Y.stt.clear(), Y.ntt.clear();
    X.ans = Y.ans = 0;

    cin >> q;
    for(int qid = 1; qid <= q; qid++)
    {
        cin >> opt >> x >> y;
        if(opt == 1)
        {
            a[--head] = x;
            a[--head] = y;
            X.opt(1, x, y);
            if(qid != 1) Y.opt(1, a[head + 2], a[head + 1]);
        }
        else if(opt == 2)
        {           
            a[--head] = x, a[++tail] = y;
            swap(X, Y);

            if(qid == 1) X.opt(1, a[head + 1], a[head]);
            else
            {
                X.opt(1, a[head + 1], a[head]);
                X.opt(3, a[tail - 1], a[tail]);
            }
        }
        else
        {
            a[++tail] = x, a[++tail] = y;
            X.opt(3, x, y);
            if(qid != 1) Y.opt(3, a[tail - 2], a[tail - 1]);
        }
        cout << X.ans << '\n';
    }
    return;
}

int main()
{
    ios :: sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    int t; cin >> t;
    while(t--) solve();
    return 0;
}