「Summary」2023-07-07 做题记录

啪的一下我就搬了 5 道题。

2023-07-07

BZOJ 3144 向量 / CF678F

其实没写 BZOJ 这题，因为之前写过一道几乎一样的题，这里指 CF678F。
所以以下的题解是 CF678F 的。

如果没有删除，直接李超树上就可以了。考虑离线，线段树分治来做，维护每对 $(x, y)$ 出现的范围，直接给每个叶子节点建一颗动态开点李超树。
因为时间比较久远通过代码头部注释内容判断，放个代码自己复习一下。

int n, cnt, re[MAXN], pos[MAXN];
struct Range { int l, r; } ra[MAXN];
struct Opt { int k, ind, x, y; } opt[MAXN];
struct Line { int x, y; } li[MAXN];

inline int getval(int ind, int k) { return k * li[ind].x + li[ind].y; }
struct LichaoTree {
  int tot, root[MAXN * MAXM];
  struct Node { int l, r, dat; } s[MAXN * MAXM];
  inline void insert(int& p, int l, int r, int ind) {
    if (!p) p = ++tot;
    if (!s[p].dat) return s[p].dat = ind, void();
    int mid = (l + r) >> 1;
    if (getval(ind, mid) > getval(s[p].dat, mid)) swap(s[p].dat, ind);
    if (getval(ind, l) > getval(s[p].dat, l)) insert(s[p].l, l, mid, ind);
    else if (getval(ind, r) > getval(s[p].dat, r)) insert(s[p].r, mid + 1, r, ind);
  }
  inline int query(int p, int l, int r, int k) {
     if (!p) return -INF;
     if (l == r) return getval(s[p].dat, k);
     int mid = (l + r) >> 1, res = getval(s[p].dat, k);
     if (k <= mid) res = Max(res, query(s[p].l, l, mid, k));
     else res = Max(res, query(s[p].r, mid + 1, r, k));
     return res;
  }
} lt;
struct SegmentTree {
  struct Node { int l, r; } s[MAXN << 2];
  inline void build(int p, int l, int r) {
    s[p] = Node{l, r};
    if (l == r) return pos[l] = p, void();
    int mid = (l + r) >> 1;
    build(p << 1, l, mid), build(p << 1 | 1, mid + 1, r);
  }
  inline void update(int p, int l, int r, int ind) {
    if (s[p].l >= l && s[p].r <= r) {
      lt.insert(lt.root[p], -LIM, LIM, ind);
      return;
    }
    int mid = (s[p].l + s[p].r) >> 1;
    if (l <= mid) update(p << 1, l, r, ind);
    if (r > mid) update(p << 1 | 1, l, r, ind);
  }
} seg;

CF1149C

首先考察一下括号序列和树的直径的关系，给左括号赋值为 $1$，给右括号赋值为 $-1$，设 $x, y$ 分别为树的直径的两个端点，结合图看一下发现

以三角形符号代替的子树都会自行内部括号匹配消化，于是直径就相当于把括号序列中匹配的中间匹配的括号扣掉之后不能被匹配的括号数。

相当于找一条分界线，求右边的最大字段和，求左边的最小字段和，然后做差。
因为我会 GSS 3 - Can you answer these queries III，所以这道题我一眼秒了，然后 WA * 3。因为有点细节，放一下部分代码。

struct Element {
  int dat, lmax, rmax, lmin, rmin, sum, maxl1, maxl2;
  inline Element operator + (const Element oth) {
    Element res;
    res.sum = sum + oth.sum;
    res.lmax = Max(lmax, sum + oth.lmax), res.rmax = Max(oth.rmax, oth.sum + rmax);
    res.lmin = Min(lmin, sum + oth.lmin), res.rmin = Min(oth.rmin, oth.sum + rmin);
    res.maxl1 = max({maxl1, -sum + oth.maxl1, oth.lmax + rmax * 2 - sum});
    res.maxl2 = max({oth.maxl2, oth.sum + maxl2, -rmin + oth.sum - 2 * oth.lmin});
    res.dat = max({dat, oth.dat, maxl2 + oth.lmax, -rmin + oth.maxl1});
    return res;
  }
};
Element L = Element{1, 1, 1, 0, 0, 1, 1, 1}, R = Element{1, 0, 0, -1, -1, -1, 1, 1,};

CF631E

假设现在交换了 $i, j$ 两个位置，记一个前缀和 $s_i = a[1 \dots i]$，操作后变化的代价是 $a_i (j - i) - (s_j - s_i)$，拆一下变成 $(-a_ii + s_i) + a_ij - s_j$，可以直接李超线段树做了。

CF932F

写个式子先，定义 $dp_u$ 表示从 $u$ 跳出去的最小代价，那么有

$$ \begin{aligned} dp_u = dp_v + a_u \times b_v, (v \in \mathrm{subtree}(u)) \end{aligned} $$

直接李超树合并即可。

P2824

二分后 0/1 排序。

NOI 2022 众数

开 long long

服了，怎么这玩意这么阴，个数可以爆 int 。。。
过了才知道有个求绝对众数的方法叫做摩尔投票，但是并不影响过这道题。
有一个很好的性质，如果一个序列存在绝对众数，那么绝对众数一定是这个序列的中位数，发现可以用权值线段树很好地完成这个查询和合并，考虑怎么维护原序列，其实直接链表 $\mathcal{O(1)}$ 就能做。

GYM102979C

为什么这种传统题我都不会啊。😭😭😭😭
这种二维问题，首先固定一维，扫描它，这里固定 $x$，从 $1$ 往 $n$ 扫，对于矩形大小直接二分，把注意力放在当前手上 $[x, x + s]$ 这段区间的 $y$ 轴即可，因为对于 $x$ 轴，在挪动区间的时候可以撤销 $x - s - 1$ 的贡献，这不是重点。
用线段树维护 $y$ 轴上的信息，于是对于 $(x, y)$ 这个点对，考虑它如何做出贡献，显然不能直接对 $[y, y + s]$ 这个区间加一，因为该区间内有可能出现和他相同颜色的点，于是用 set 一类的数据结构维护横坐标在 $[x, x + 1]$ 中的某一类颜色的点的 $y$ 坐标集合，每次都查询前驱后缀，避开重复段然后算贡献即可。