扫描线学习记录

题单

P7560 [JOISC 2021 Day1] フードコート

容易发现操作分两种：

1. $c_i\leftarrow c_i+k$

2. $c_i\leftarrow\max(c_i-k,0)$

考虑对人进行扫描线并且维护一个关于时间的线段树，表示每个时刻做了什么操作。查询时找到最小的前缀和位置，容易发现这个位置一定被 chkmax 成 $0$ 了，同时后面的一定都没有 chkmax 成功，于是剩余的人的个数就求出来了。

时间复杂度：$O((N+M+Q)\log N)$。

#include <bits/stdc++.h>

#define int int64_t

const int kMaxN = 2.5e5 + 5;

int n, m, q;
int op[kMaxN], L[kMaxN], R[kMaxN], C[kMaxN], K[kMaxN], ans[kMaxN];
std::vector<std::pair<int, int>> vec[kMaxN];

struct SGT {
  int cnt[kMaxN * 4], sum[kMaxN * 4], mi[kMaxN * 4], pos[kMaxN * 4];

  void pushup(int x) {
    cnt[x] = cnt[x << 1] + cnt[x << 1 | 1];
    sum[x] = sum[x << 1] + sum[x << 1 | 1];
    if (mi[x << 1] < sum[x << 1] + mi[x << 1 | 1]) {
      mi[x] = mi[x << 1], pos[x] = pos[x << 1];
    } else {
      mi[x] = sum[x << 1] + mi[x << 1 | 1], pos[x] = pos[x << 1 | 1];
    }
  }

  void build(int x, int l, int r) {
    pos[x] = l;
    if (l == r) return;
    int mid = (l + r) >> 1;
    build(x << 1, l, mid), build(x << 1 | 1, mid + 1, r);
  }

  void update(int x, int l, int r, int ql, int v) {
    if (l == r) {
      if (v == 1) {
        if (op[l] == 1) cnt[x] = sum[x] = mi[x] = K[l];
        else cnt[x] = 0, sum[x] = mi[x] = -K[l];
      } else {
        cnt[x] = sum[x] = mi[x] = 0;
      }
      return;
    }
    int mid = (l + r) >> 1;
    if (ql <= mid) update(x << 1, l, mid, ql, v);
    else update(x << 1 | 1, mid + 1, r, ql, v);
    pushup(x);
  }

  std::tuple<int, int, int> querymin(int x, int l, int r, int ql, int qr) {
    if (l > qr || r < ql) return {0, 0, 0};
    else if (l >= ql && r <= qr) return {sum[x], mi[x], pos[x]};
    int mid = (l + r) >> 1;
    if (qr <= mid) return querymin(x << 1, l, mid, ql, qr);
    if (mid < ql) return querymin(x << 1 | 1, mid + 1, r, ql, qr);
    auto [suml, mil, posl] = querymin(x << 1, l, mid, ql, qr);
    auto [sumr, mir, posr] = querymin(x << 1 | 1, mid + 1, r, ql, qr);
    if (mil <= suml + mir) return {suml + sumr, mil, posl};
    else return {suml + sumr, suml + mir, posr};
  }

  int querysum(int x, int l, int r, int ql, int qr) {
    if (l > qr || r < ql) return 0;
    else if (l >= ql && r <= qr) return sum[x];
    int mid = (l + r) >> 1;
    return querysum(x << 1, l, mid, ql, qr) + querysum(x << 1 | 1, mid + 1, r, ql, qr);
  }

  int querycnt(int x, int l, int r, int ql, int qr) {
    if (l > qr || r < ql) return 0;
    else if (l >= ql && r <= qr) return cnt[x];
    int mid = (l + r) >> 1;
    return querycnt(x << 1, l, mid, ql, qr) + querycnt(x << 1 | 1, mid + 1, r, ql, qr);
  }

  int querykth(int x, int l, int r, int k) {
    assert(k <= cnt[x]);
    if (l == r) return C[l];
    int mid = (l + r) >> 1;
    if (k <= cnt[x << 1]) return querykth(x << 1, l, mid, k);
    else return querykth(x << 1 | 1, mid + 1, r, k - cnt[x << 1]);
  }
} sgt;

void dickdreamer() {
  std::cin >> n >> m >> q;
  for (int i = 1; i <= q; ++i) {
    std::cin >> op[i];
    if (op[i] == 1) {
      std::cin >> L[i] >> R[i] >> C[i] >> K[i];
      vec[L[i]].emplace_back(i, 1), vec[R[i] + 1].emplace_back(i, -1);
    } else if (op[i] == 2) {
      std::cin >> L[i] >> R[i] >> K[i];
      vec[L[i]].emplace_back(i, 1), vec[R[i] + 1].emplace_back(i, -1);
    } else  {
      std::cin >> C[i] >> K[i];
      vec[C[i]].emplace_back(i, K[i]);
    }
  }
  sgt.build(1, 0, q);
  for (int i = 1; i <= n; ++i) {
    for (auto [id, v] : vec[i]) {
      if (op[id] == 1 || op[id] == 2)
        sgt.update(1, 0, q, id, v);
    }
    for (auto [id, v] : vec[i]) {
      if (op[id] != 3) continue;
      int pos = std::get<2>(sgt.querymin(1, 0, q, 0, id));
      int cnt = sgt.querysum(1, 0, q, pos + 1, id), tot = sgt.querycnt(1, 0, q, 0, id);
      if (cnt >= K[id])
        ans[id] = sgt.querykth(1, 0, q, tot - cnt + K[id]);
    }
  }
  for (int i = 1; i <= q; ++i)
    if (op[i] == 3)
      std::cout << ans[i] << '\n';
}

int32_t main() {
#ifdef ORZXKR
  freopen("in.txt", "r", stdin);
  freopen("out.txt", "w", stdout);
#endif
  std::ios::sync_with_stdio(0), std::cin.tie(0), std::cout.tie(0);
  int T = 1;
  // std::cin >> T;
  while (T--) dickdreamer();
  // std::cerr << 1.0 * clock() / CLOCKS_PER_SEC << "s\n";
  return 0;
}

P9057 [Ynoi2004] rpfrdtzls

容易发现如果去掉 $1$ 的话答案不超过 $\log A$，所以同样建一个有关时间的线段树，修改时在某个位置加入一个数只会改变 $O(\log A)$ 个区间的答案，暴力求出答案并且用区间历史和线段树维护即可。

时间复杂度：$O((n+m)\log^2 A)$

CF793F Julia the snail

容易发现 $(x,y)$ 的答案是把所有在 $[x,y]$ 内的线段拿出来后第一个没被覆盖的数的位置。

考虑扫描线，设 $f_i$ 表示 $i$ 到当前 $r$ 的答案，现在加入一个线段 $[l,r+1]$，如果 $f_i<l$ 就没影响，否则 $f_i\leftarrow r+1$。

所以相当于是维护一个类似区间 chkmax 的东西，用吉司机线段树维护即可。

时间复杂度：$O((n+m+q)\log n)$。

P7907 [Ynoi2005] rmscne

设 $pre_i$ 表示 $a$ 数组中上一个与 $a_i$ 相等的位置。

容易发现 $[l,r]$ 中满足条件的线段中左端点为 $l$ 的最小右端点一定是 $[l,r]$ 中 $pre_j<l$ 的最大的 $j$。

不妨设 $[l,r]$ 中以 $r$ 为右端点的线段的最大左端点为 $p$，那么 $[l,p]$ 中的任意位置 $i$ 作为左端点的答案一定是 $i$ 在 $[i,r]$ 中的答案，因为 $[i,r]$ 包含的颜色种类一定和 $[l,r]$ 相同。

先预处理每个 $[l,r]$ 的 $p$，然后就可以进行扫描线了，在从小到大扫 $r$ 的过程中让 $[pre_r+1,r]$ 的右端点设成 $r$，查询相当于是求区间最小值，线段树维护即可。

时间复杂度：$O((n+q)\log n)$。

P9999 [Ynoi2000] tmostnrq

同样是扫描线，对于每组询问 $(l,r,x)$ 就在 $l$ 时刻将 $x$ 插入，在 $r$ 时刻查询这个点位置。

每次操作就是让当前树上挂的每个点向当前 $a_i$ 移动一步，考虑怎么处理这个移动。

不妨设 $x=a_i$，那么 $x$ 到根的链上的点一定是往儿子移动一步，而其它点是向父亲移动。

对于 $x$ 到根的链上的点可以重链剖分，对于链底的点就暴力挪到下面的链上，其余点打个标记。

对于不在 $x$ 到根的链上的点，容易发现这些点只会构成 $O(\log n)$ 个 dfs 序区间，可以维护 $f_i$ 表示 $i$ 到 $i$ 所在重链链顶的距离。

由于每个点跳到根只会经过 $O(\log n)$ 条不同重链，所以先暴力找到所有 $f_i=0$ 的点直接跳，其它点打标记即可。

时间复杂度：$O((n+q)\log^2 n)$。

CF1172F Nauuo and Bug

容易发现对于固定区间所对应的函数值是个折线函数，且只有区间长度段。

考虑在线段树上做这个东西，不妨设 $c_i$ 表示当前线段树区间要至少减 $i$ 次 $p$ 的最小初始值。

合并两个区间的 $c$ 数组时，假设左区间为 $c_x$，右区间为 $c_y$，显然需要满足 $c_{x+1}-1+sum_{ls}-xp\geq c_y$，满足这个条件就可以得到转移：$c_{x+y}\leftarrow\max(c_x,c_y-sum_{ls}+xp)$。

设 $f(x,y)$ 是 $c_x,c_y$ 合并出来的值，下面证明一下 $f(x,y)\leq f(x+1,y-1)$。

• 证明

  由于 $c_{x+1}-1+sum_{ls}-xp\geq c_y$，所以 $c_y-sum_{ls}+xp<c_{x+1}$。

  又因为 $c_x\leq c_{x+1}$，所以 $f(x,y)=\max(c_x,c_y-sum_{ls}+xp)\leq c_{x+1}\leq f(x+1,y-1)$。

那么对于某个结果 $c_x$，一定是选择左端点的次数最小的方案合并。由于有个结论是 $c_{x+1}-c_x\geq p$，所以左端点较大的一定能匹配较小的能匹配的所有方案。

于是在拓展的过程中能拓展 $y$ 就拓展 $y$，否则拓展才 $x$。

查询时二分出每个线段树区间对应减的次数并更新当前值即可。

时间复杂度：$O(n\log n+q\log^2 n)$。