LOJ #3273. 「JOISC 2020 Day1」扫除 题解

Description

平面直角坐标系上一个等腰直角三角形，维护 $4$ 种操作：

1. 加入 $(x,y)$。
2. 把 $y\leq l$ 的点横坐标变成 $\max⁡(x,n-l)$。
3. 把 $x\leq l$ 的点纵坐标变成 $\max(y,n-l)$。
4. 查询第 $i$ 个点现在的位置。

$1\leq n\leq 10^9,1\leq m\leq 5\times 10^5,1\leq Q\leq 10^6$。

Solution

考虑没有一操作怎么做。

容易发现对于任意时刻都存在一条左上到右下的轮廓线，满足所有点要么在轮廓线上，要么位置没有发生改变。

所以先求出每个点第一次被移动的时刻 $p_i$，同时维护一个平衡树表示轮廓线上的点，在 $p_i$ 时刻将 $i$ 号点加入平衡树，修改时直接将需要修改的区间 split 出来打标记即可。

如果有一操作，会让某个点在加入的时候在轮廓线下面，导致上面的做法不正确。考虑规避掉一操作。

---

假设要求出某个点 $p$ 经过 $[l,r]$ 操作后的结果，那么在线段树上找到 $[l,r]$ 对应的 $O(\log n)$ 个区间，并将这个点依次插入这些区间。

求答案时进行类似线段树分治的做法，每次将当前线段树节点 $[l,r]$ 上的点一起做 $[l,r]$ 操作，然后将这些点操作完的坐标挂到对应的线段树上的下一个区间即可。

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

Code

#include <bits/stdc++.h>

// #define int int64_t

const int kMaxM = 1.5e6 + 5, kMaxQ = 1e6 + 5;

int n, m, q;
int x[kMaxM], y[kMaxM], t[kMaxM], pos[kMaxM], ansx[kMaxQ], ansy[kMaxQ];
std::mt19937 rnd(114514);
std::vector<int> vec[kMaxQ * 4], unq;

struct Query {
  int op, x, y;
  Query(int _op = 0, int _x = 0, int _y = 0) : op(_op), x(_x), y(_y) {}
} qq[kMaxQ];

struct Node {
  int ls, rs, val, x, y, tagx, tagy;
  Node(int _ls = 0, int _rs = 0, int _val = 0, int _x = 0, int _y = 0, int _tagx = 0, int _tagy = 0) :
    ls(_ls), rs(_rs), val(_val), x(_x), y(_y), tagx(_tagx), tagy(_tagy) {}
};

struct FHQTreap {
  int rt, tot;
  Node t[kMaxM];

  void clear() {
    for (int i = 1; i <= tot; ++i) t[i] = Node();
    rt = tot = 0;
  }
  int newnode(int x, int y) {
    t[++tot] = {0, 0, rnd(), x, y, 0, 0};
    return tot;
  }
  void addtag(int x, int tagx, int tagy) {
    if (~tagx) t[x].x = t[x].tagx = tagx;
    if (~tagy) t[x].y = t[x].tagy = tagy;
  }
  void pushdown(int x) {
    if (t[x].ls) addtag(t[x].ls, t[x].tagx, t[x].tagy);
    if (t[x].rs) addtag(t[x].rs, t[x].tagx, t[x].tagy);
    t[x].tagx = t[x].tagy = -1;
  }
  int merge(int x, int y) {
    if (!x || !y) return x + y;
    pushdown(x), pushdown(y);
    if (t[x].val < t[y].val) {
      t[x].rs = merge(t[x].rs, y);
      return x;
    } else {
      t[y].ls = merge(x, t[y].ls);
      return y;
    }
  }
  void splitx(int x, int vx, int &a, int &b) {
    // a 的 x <= vx
    if (!x) return void(a = b = 0);
    pushdown(x);
    if (t[x].x <= vx) {
      a = x, splitx(t[x].rs, vx, t[x].rs, b);
    } else {
      b = x, splitx(t[x].ls, vx, a, t[x].ls);
    }
  }
  void splity(int x, int vy, int &a, int &b) {
    // a 的 y >= vy
    if (!x) return void(a = b = 0);
    pushdown(x);
    if (t[x].y >= vy) {
      a = x, splity(t[x].rs, vy, t[x].rs, b);
    } else {
      b = x, splity(t[x].ls, vy, a, t[x].ls);
    }
  }
  int ins(int x, int y) {
    int a, b, c, id;
    id = newnode(x, y);
    splitx(rt, x, a, c);
    splity(a, y, a, b);
    rt = merge(merge(a, id), merge(b, c));
    return id;
  }
  void pushall(int x) {
    if (!x) return;
    pushdown(x);
    if (t[x].ls) pushall(t[x].ls);
    if (t[x].rs) pushall(t[x].rs);
  }
} ft;

struct SGT {
  int N, val[kMaxM * 4];
  void build(int n) {
    for (N = 1; N <= n + 1; N <<= 1) {}
    std::fill_n(val, 2 * N, 1e9);
  }
  void update(int x, int v) {
    for (x += N; x; x >>= 1) val[x] = v;
  }
  int query(int l, int r) {
    if (l > r) return 1e9;
    int ret = 1e9;
    for (l += N - 1, r += N + 1; l ^ r ^ 1; l >>= 1, r >>= 1) {
      if (~l & 1) ret = std::min(ret, val[l ^ 1]);
      if (r & 1) ret = std::min(ret, val[r ^ 1]);
    }
    return ret;
  }
} sgt[2];

void update(int x, int l, int r, int ql, int qr, int id) {
  if (l > qr || r < ql) return;
  else if (l >= ql && r <= qr) return void(vec[x].emplace_back(id));
  int mid = (l + r) >> 1;
  update(x << 1, l, mid, ql, qr, id), update(x << 1 | 1, mid + 1, r, ql, qr, id);
}

void discrete(int l, int r) {
  unq.clear();
  for (int i = l; i <= r; ++i) {
    if (qq[i].op == 2 || qq[i].op == 3) unq.emplace_back(qq[i].x);
  }
  std::sort(unq.begin(), unq.end());
  unq.erase(std::unique(unq.begin(), unq.end()), unq.end());
}

int getid(int x) { return std::lower_bound(unq.begin(), unq.end(), x) - unq.begin() + 1; }

void solve(int x, int l, int r) {
  static std::vector<int> vv[kMaxM];
  ft.clear();
  discrete(l, r);
  sgt[0].build(unq.size()), sgt[1].build(unq.size());
  for (int i = r; i >= l; --i) {
    if (qq[i].op == 2) sgt[0].update(getid(qq[i].x), i);
    else if (qq[i].op == 3) sgt[1].update(getid(qq[i].x), i);
  }
  for (auto i : vec[x]) {
    int p = std::min(sgt[0].query(getid(ansy[i]), getid(n - ansx[i] + 1) - 1),
                     sgt[1].query(getid(ansx[i]), getid(n - ansy[i] + 1) - 1));
    if (p <= r) vv[p].emplace_back(i);
  }
  for (int i = l; i <= r; ++i) {
    int x, y, z;
    if (qq[i].op == 2) {
      ft.splitx(ft.rt, n - qq[i].x, x, z);
      ft.splity(x, qq[i].x + 1, x, y);
      if (y) ft.addtag(y, n - qq[i].x, -1);
      ft.rt = ft.merge(ft.merge(x, y), z);
    } else if (qq[i].op == 3) {
      ft.splitx(ft.rt, qq[i].x, x, z);
      ft.splity(x, n - qq[i].x + 1, x, y);
      if (y) ft.addtag(y, -1, n - qq[i].x);
      ft.rt = ft.merge(ft.merge(x, y), z);
    }
    for (auto id : vv[i]) {
      if (qq[i].op == 2) ansx[id] = std::max(ansx[id], n - qq[i].x), assert(ansy[id] <= qq[i].x);
      else ansy[id] = std::max(ansy[id], n - qq[i].x), assert(ansx[id] <= qq[i].x);
      pos[id] = ft.ins(ansx[id], ansy[id]);
    }
  }
  ft.pushall(ft.rt);
  for (int i = l; i <= r; ++i) {
    for (auto id : vv[i]) {
      ansx[id] = ft.t[pos[id]].x;
      ansy[id] = ft.t[pos[id]].y;
    }
  }
  for (int i = l; i <= r; ++i) vv[i].clear();
  for (auto i : vec[x]) pos[i] = 0;
  if (l != r) {
    int mid = (l + r) >> 1;
    solve(x << 1, l, mid), solve(x << 1 | 1, mid + 1, r);
  }
}

void dickdreamer() {
  std::cin >> n >> m >> q;
  for (int i = 1; i <= m; ++i) {
    std::cin >> x[i] >> y[i];
    t[i] = 1;
  }
  for (int i = 1; i <= q; ++i) {
    std::cin >> qq[i].op;
    if (qq[i].op == 1) {
      std::cin >> qq[i].x;
      ansx[i] = x[qq[i].x], ansy[i] = y[qq[i].x];
      update(1, 1, q, t[qq[i].x], i, i);
    } else if (qq[i].op == 2) {
      std::cin >> qq[i].x;
    } else if (qq[i].op == 3) {
      std::cin >> qq[i].x;
    } else {
      std::cin >> qq[i].x >> qq[i].y;
      t[++m] = i, x[m] = qq[i].x, y[m] = qq[i].y;
    }
  }
  solve(1, 1, q);
  for (int i = 1; i <= q; ++i)
    if (qq[i].op == 1)
      std::cout << ansx[i] << ' ' << ansy[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;
}