正睿 2023 noip 10 连 Day2 T2 题解

Description

对于一个个体，定义以下四种操作：

1. 睡觉：此时会进入深一层的梦境

2. 起床：此时会从深一层的梦境中醒过来，也就是进入浅一层的梦境

3. 打标记：当前层梦境会留下一个标记，这个标记会在第一次进入更浅层或者进行操作4的时候消失(这里的更浅层是相对标记来说)

4. 回归：回到最浅的有标记的层数，并且删除这层的标记，如果没有标记，忽略这次操作

5. 查询：查询当前的梦境层数

现在有 $n$ 个个体，编号从 $1$ 到 $n$，要执行 $q$ 次区间操作，查询仍然是单点的。

为了保证不会存在进入负层梦境的问题，所有个体在开始前都会进行 $5\times 10^5$ 次1操作。

$n,q\leq 5\times 10^5$，数据随机。

Solution

容易发现对于每个个体只要维护他到当前最浅标记的距离，如果没有标记设为 $-1$。

那么操作 $1$ 和操作 $2$ 就对于所有距离不是 $-1$ 的直接加减。

操作 $3$ 如果没有标记那么就把距离设为 $0$，操作 $4$ 如果有标记就把位置减去距离最浅标记的距离，然后把距离最浅标记的距离设为 $-1$。

考虑用珂朵莉树维护所有距离最浅标记距离相同的区间。

设询问区间为 $[l,r]$，然后对于 $[l,r]$ 的距离做上面的操作，对于操作 $1,2,3$ 的区间加减可以用树状数组维护。

如果是操作 $4$ 由于 $[l,r]$ 全是 $-1$ 就直接删掉所有原来构成 $[l,r]$ 的区间，然后重构一个 $[l,r,-1]$，即可保证复杂度。

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

注意对于没有 $3,4$ 操作时特判，因为这样每次都有可能遍历所有区间，然后就 T 了。

Code

#pragma GCC optimize(2)
#include <bits/stdc++.h>

// #define int int64_t

const int kMaxN = 5e5 + 5;

struct Node {
  int l;
  mutable int r, v;

  Node(int _l, int _r, int _v) : l(_l), r(_r), v(_v) {}

  friend bool operator <(const Node &n1, const Node &n2) {
    return n1.l < n2.l;
  }
};

int n, q;
int c[kMaxN], op[kMaxN], l[kMaxN], r[kMaxN];
std::set<Node> s;

namespace BIT {
void upd(int x, int v) {
  for (; x <= n; x += x & -x)
    c[x] += v;
}
void upd(int l, int r, int v) { upd(l, v), upd(r + 1, -v); }

int qry(int x) {
  int ret = 5e5;
  for (; x; x -= x & -x)
    ret += c[x];
  return ret;
}
} // namespace BIT

auto split(int x) {
  if (x > n) return s.end();
  auto it = std::prev(s.upper_bound({x, 0, 0}));
  if (it->l == x) return it;
  int r = it->r;
  it->r = x - 1;
  return s.emplace(x, r, it->v).first;
}

void inc(int l, int r) {
  BIT::upd(l, r, 1);
  auto itl = split(l), itr = split(r + 1);
  for (auto it = itl; it != itr; ++it)
    if (~it->v)
      ++it->v;
}

void dec(int l, int r) {
  BIT::upd(l, r, -1);
  auto itl = split(l), itr = split(r + 1);
  for (auto it = itl; it != itr; ++it)
    if (~it->v)
      --it->v;
}

void addtag(int l, int r) {
  auto itl = split(l), itr = split(r + 1);
  for (auto it = itl; it != itr; ++it)
    if (!~it->v)
      it->v = 0;
}

void goback(int l, int r) {
  auto itl = split(l), itr = split(r + 1);
  for (auto it = itl; it != itr; ++it)
    if (~it->v)
      BIT::upd(it->l, it->r, -it->v);
  s.erase(itl, itr), s.emplace(l, r, -1);
}

bool check() {
  for (int i = 1; i <= q; ++i)
    if (op[i] == 3 || op[i] == 4)
      return 0;
  for (int i = 1; i <= q; ++i) {
    if (op[i] == 1) {
      BIT::upd(l[i], r[i], 1);
    } else if (op[i] == 2) {
      BIT::upd(l[i], r[i], -1);
    } else {
      std::cout << BIT::qry(l[i]) << '\n';
    }
  }
  return 1;
}

void dickdreamer() {
  std::cin >> n >> q;
  for (int i = 1; i <= q; ++i)
    std::cin >> op[i] >> l[i] >> r[i];
  if (check()) return;
  s.emplace(1, n, -1);
  for (int i = 1; i <= q; ++i) {
    if (op[i] == 1) {
      inc(l[i], r[i]);
    } else if (op[i] == 2) {
      dec(l[i], r[i]);
    } else if (op[i] == 3) {
      addtag(l[i], r[i]);
    } else if (op[i] == 4) {
      goback(l[i], r[i]);
    } else {
      std::cout << BIT::qry(l[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;
}