ABC343F 题解

__ryp__ · 2024-03-08 20:37:11 · 题解

很明显就是线段树维护区间次小值的出现次数。

这里主要讲怎么把 push_up 写的简洁一些。

node
push_up (const node &l, const node &r)
{
  vector<pi> z; z.reserve (4);

  z.emplace_back (l.mx), z.emplace_back (l.pmx);
  z.emplace_back (r.mx), z.emplace_back (r.pmx);
  sort (begin (z), end (z), greater<pi> ());
  for (auto p = begin (z); p != prev (end (z)); p++)
    if (p->first == next (p)->first) p->second += next (p)->second;
  return { z[0], z[1].first == z[0].first ? z[2] : z[1] };
}

某些人写了六十行的大模拟还没调过

我们可以把值和出现次数捆绑在一起维护，这样就可以方便更新。先排序，然后维护一下出现次数即可。

完整代码（只有 74 行）