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

· · 题解

更好的阅读体验

这个是反悔贪心？是不是不太像，感觉说直接贪是不是更自然。

首先考虑问题的静态情形怎么做。思考一个括号序列什么时候是合法的：当且仅当前 2i - 1 个字符中有至少 i 个 (。然而 i 和 2i - 1 不是倍数关系，不太好。但是注意到第一个位置一定是 (，最后一个位置一定是 )，所以不用考虑。所以我们可以把第一个和最后一个位置去除，在执行完去除操作所剩下的括号序列上，前 2i 个字符有至少 i 个 (。

那么我们从左往右考虑，维护目前未被确定为 ( 的所有位置（下文称为“未确定集合”）。维护一个变量 i 从左往右扫描，每次将 i, i+1 先加入未被确定为 ( 的集合，然后直接贪心地从未确定集合中选出 w_j 最大的 j 确定为左括号，随后将 i 增加 2。

这么做为什么正确？发现，一个决策会影响一个后缀，也就是一个 i 加入后，后续的所有位置都可以选择这个 i 产生贡献。这就意味着如果我在某个位置没有选择最优决策 j，而选择了一个决策 j'，那么我们把 i 处的决策调整成 j，然后在后续的一个位置把决策修改为 j'，这样做是不劣的。至此我们说明了这个做法的正确性。下文中这个做法被称为做法 1。

至此可以解决只有 1 或 3 操作的做法。

接下来考虑同时存在 1, 3 的做法。注意到，这个问题其实完全等价于另外一个问题：求所有括号序列中，所有 ) 对应位置的 w 之和的最小值。这个问题的做法也是对称的：我们从右往左扫描，维护目前还未确定为 ) 的位置集合，每次取出集合中 w 最小的位置即可。下文中这个做法被称为做法 2。

然后发现这两个做法可以合并！具体地，我们发现做法 1 中未被确定为 ( 的集合就是目前确定为 ) 的集合，做法 2 中未被确定为 ) 的集合就是目前确定的 ( 的集合，因此这两个集合是互补的！因此假设目前 ( 的集合为 S_l，) 的集合是 S_r。则当我在末尾加入元素的时候，我们使用做法 1，将我加入的元素加入 S_r，随后弹出 S_r 的最大值加入 S_l；当我在开头加入元素的时候，我们使用做法 2，将我加入的元素加入 S_l，随后弹出 S_l 的最小值加入 S_r。

至此解决了同时存在 1, 3 的情况。

再考虑操作 2，你发现由于我们做法 1，做法 2 都只能支持一次在同一方加入 2 个元素，然而操作 2 是分别在左端、右端各加入一个元素，使用已有的做法做不了。

但是发现，我们可以把上述 S_l, S_r 及其对应的操作封装为一个数据结构，然后维护两个数据结构 \operatorname{out}, \operatorname{in}，分别表示现在整个序列对应的数据结构，以及现在的序列去除首尾元素后对应的数据结构。则当我在首尾各加入一个元素时，在原来 \operatorname{in} 的首尾各加入两个元素之后就可以得到新的 \operatorname{out}，而原来的 \operatorname{out} 就是新的 \operatorname{in}，这样在首尾各加入一个元素的情况也得到解决。

至此问题在 O(q \log q) 的时间内得到解决！

#include<bits/stdc++.h>
#define endl '\n'
#define N 400006
using namespace std;
using i64=long long;
int q;
struct DS {
  int l,r; i64 sum;
  priority_queue<int> rb;
  priority_queue<int,vector<int>,greater<int> > lb;
  DS():l(-2e9),r(-2e9),sum(0) {}
  void push_back(int x,int y)
  {
    if(l==-2e9)return l=x,r=y,(void)0;
    rb.push(r),rb.push(x),r=y;
    lb.push(rb.top()),sum+=rb.top(),rb.pop();
  }
  void push_front(int x,int y)
  {
    if(l==-2e9)return l=y,r=x,(void)0;
    lb.push(l),lb.push(x),sum+=l+x,l=y;
    rb.push(lb.top()),sum-=lb.top(),lb.pop();
  }
};
void solve()
{
  scanf("%d",&q);
  DS in,out; deque<int> dq;
  for(int i=1,o,x,y;i<=q;i++)
  {
    scanf("%d%d%d",&o,&x,&y);
    if(o==3||o==2&&i==1)
    {
      out.push_back(x,y);
      if(i>1)in.push_back(dq.back(),x);
      dq.push_back(x),dq.push_back(y);
    } else if(o==1) {
      out.push_front(x,y);
      if(i>1)in.push_front(dq.front(),x);
      dq.push_front(x),dq.push_front(y);
    } else {
      in.push_front(dq.front(),x),in.push_back(dq.back(),y);
      swap(in,out),dq.push_front(x),dq.push_back(y);
    }
    printf("%lld\n",out.l+out.sum);
  }
}
main()
{
  int T; scanf("%d",&T);
  while(T--)solve();
  return 0;
}