[2020团体程序设计天梯赛-总决赛L3-2] 传送门

UPD. 2020.12.18 14:05

PTA 已经可以提交，我题目记错了，加的是 双向传送门 而不是 单向传送门 ，原来代码修改修改就可以过了。

题解

(N) 个机器人分别在 ((i, 0))，每次移动横坐标不变，纵坐标加一，纵坐标达到 (10^9) 时停止。 (M) 次修改，每次添加或删除一个 ((x_1, y) ightarrow(x_2, y)) 的传送门。求每次修改后，每个机器人起点和终点横坐标乘积之和。
(N, M le 10^5)

将传送门看作有向边，整张图可以看成一个森林，只要求叶子节点的横坐标之和乘上根节点的横坐标，直接用LCT维护子树信息。

（因为暂时没有地方提交，所以下面的代码不保证正确，据说正解只要平衡树，搞不清楚）

提交地址
下面是原来的单向传送门代码，修改后的代码在后面。

#include <bits/stdc++.h>

using LL = long long;
using PII = std::pair<int, int>;
constexpr int N(1e5 + 5);
// Link Cut Tree
struct Node {
  Node *c[2], *fa;
  int id;
  LL s, vir;
} t[N << 2], *null = t;
#define ls c[0]
#define rs c[1]
inline Node*newNode(int w, int id) {
  static Node *p = t + 1;
  p->ls = p->rs = p->fa = null;
  p->vir = p->s = w;
  p->id = id;
  return p++;
}
inline void pushup(Node *o) { o->s = o->ls->s + o->rs->s + o->vir; }
inline bool nrt(Node *o) { return o == o->fa->ls || o == o->fa->rs; }
inline void rot(Node *o) {
  Node *f = o->fa, *ff = f->fa;
  int k = o == f->rs;
  if (nrt(f)) ff->c[f == ff->rs] = o;
  o->fa = ff;
  f->c[k] = o->c[!k], o->c[!k]->fa = f;
  o->c[!k] = f, f->fa = o;
  pushup(f), pushup(o);
}
inline void splay(Node *o) {
  for (; nrt(o); rot(o)) {
    Node *f = o->fa, *ff = f->fa;
    if (nrt(f))
      rot((o == f->rs) == (f == ff->rs) ? f : o);
  }
}
inline void access(Node *o) {
  for (Node *x = null; o != null; x = o, o = o->fa) {
    splay(o);
    o->vir += o->rs->s - x->s;
    assert(o->vir >= 0);
    o->rs = x;
    pushup(o);
  }
}
int n, m, cnt;
std::map<int, Node*> id[N];
LL ans;
int main() {
  null->ls = null->rs = null->fa = null;
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
  std::cin >> n >> m;
  for (int i = 1; i <= n; i++) {
    auto x = id[i][-1] = newNode(i, i), y = id[i][1e9] = newNode(0, i);
    x->fa = y, y->s = y->vir = i;
    ans += 1LL * i * i;
  }
  auto link = [](Node *x, Node *y) {    
    access(x), splay(x), access(y);
    assert(x->ls == null);
    x->fa = y, y->vir += x->s;
    pushup(y);
  };
  auto cut = [](Node *x, Node *y) {
    access(x), splay(y);
    if (y->rs == x && x->ls == null && x->rs == null) {
      assert(x->fa == y);
      x->fa = y->rs = null;
      pushup(y);
      return true;
    }
    return false;
  };
  auto calc = [](Node *x) {
    auto findrt = [](Node *x) {
      while (x->ls != null) x = x ->ls;
      return splay(x), x;
    };
    access(x), splay(x);
    auto s = x->vir;
    return s * findrt(x)->id;
  };
  auto trans = [&](Node *o, Node *x, Node *y) {
    ans -= calc(o);
    cut(o, x), link(o, y);
    ans += calc(o);
  };
  while (m--) {
    char c; int x1, x2, y;
    std::cin >> &c >> x1 >> x2 >> y;
    auto &p = id[x1][y], &q = id[x2][y];
    if (!p) {
      p = newNode(0, x1); // dbg(x1, y, p - t);
      auto u = id[x1].find(y), v = u; u--, v++;
      auto l = u->second, r = v->second;
      if (cut(l, r)) link(l, p);
      link(p, r);
    }
    if (!q) {
      q = newNode(0, x2); // dbg(x2, y, q - t);
      auto u = id[x2].find(y), v = u; u--, v++;
      auto l = u->second, r = v->second;
      if (cut(l, r)) link(l, q);
      link(q, r);
    }
    auto pr = id[x1].upper_bound(y)->second;
    if (c == '+') {
      trans(p, pr, q);
    } else {
      trans(p, q, pr);
    }
    std::cout << ans << "
";
  }
  return 0;
}

下面是AC代码：

#include <bits/stdc++.h>

using LL = long long;
using PII = std::pair<int, int>;
constexpr int N(1e5 + 5);
// Link Cut Tree
struct Node {
  Node *c[2], *fa;
  int id;
  LL s, vir;
} t[N << 3], *null = t;
#define ls c[0]
#define rs c[1]
inline Node*newNode(int w, int id) {
  static Node *p = t + 1;
  p->ls = p->rs = p->fa = null;
  p->vir = p->s = w;
  p->id = id;
  return p++;
}
inline void pushup(Node *o) { o->s = o->ls->s + o->rs->s + o->vir; }
inline bool nrt(Node *o) { return o == o->fa->ls || o == o->fa->rs; }
inline void rot(Node *o) {
  Node *f = o->fa, *ff = f->fa;
  int k = o == f->rs;
  if (nrt(f)) ff->c[f == ff->rs] = o;
  o->fa = ff;
  f->c[k] = o->c[!k], o->c[!k]->fa = f;
  o->c[!k] = f, f->fa = o;
  pushup(f), pushup(o);
}
inline void splay(Node *o) {
  for (; nrt(o); rot(o)) {
    Node *f = o->fa, *ff = f->fa;
    if (nrt(f))
      rot((o == f->rs) == (f == ff->rs) ? f : o);
  }
}
inline void access(Node *o) {
  for (Node *x = null; o != null; x = o, o = o->fa) {
    splay(o);
    o->vir += o->rs->s - x->s;
    assert(o->vir >= 0);
    o->rs = x;
    pushup(o);
  }
}
int n, m, cnt;
std::map<int, Node*> id[N];
LL ans;
int main() {
  null->ls = null->rs = null->fa = null;
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
  std::cin >> n >> m;
  for (int i = 1; i <= n; i++) {
    auto x = id[i][-1] = newNode(i, i), y = id[i][1e9] = newNode(0, i);
    x->fa = y, y->s = y->vir = i;
    ans += 1LL * i * i;
  }
  auto link = [](Node *x, Node *y) {    
    access(x), splay(x), access(y);
    assert(x->ls == null);
    x->fa = y, y->vir += x->s;
    pushup(y);
  };
  auto cut = [](Node *x, Node *y) {
    access(x), splay(y);
    if (y->rs == x && x->ls == null && x->rs == null) {
      assert(x->fa == y);
      x->fa = y->rs = null;
      pushup(y);
      return true;
    }
    return false;
  };
  auto calc = [](Node *x) {
    auto findrt = [](Node *x) {
      while (x->ls != null) x = x ->ls;
      return splay(x), x;
    };
    access(x), splay(x);
    auto s = x->vir;
    return s * findrt(x)->id;
  };
  auto trans = [&](Node *o, Node *x, Node *y) {
    ans -= calc(o);
    cut(o, x), link(o, y);
    ans += calc(o);
  };
  auto addPoint = [&](int x, int y) {
    auto &p = id[x][y];
    if (p) return p;
    p = newNode(0, x);
    auto u = id[x].find(y), v = u; u--, v++;
    auto l = u->second, r = v->second;
    if (cut(l, r)) link(l, p);
    link(p, r);
    return p;
  };
  while (m--) {
    char c; int x1, x2, y;
    std::cin >> &c >> x1 >> x2 >> y;
    auto p = addPoint(x1, y), pr = addPoint(x1, y + 1);
    auto q = addPoint(x2, y), qr = addPoint(x2, y + 1);
    if (c == '+') {
      trans(p, pr, qr);
      trans(q, qr, pr);
    } else {
      trans(p, qr, pr);
      trans(q, pr, qr);
    }
    std::cout << ans << "
";
  }
  return 0;
}