【splay】【P9358】 Bridge

· · 题解

【splay】【P9358】 Bridge

Analysis

以下是赛时的思考过程。

我们把从某个城市的 1 号结点出发按照规则最终到达某个城市的 (m + 1) 号结点所经过的结点集合称为一条路径。

一个观察是，起点和终点总是一一对应的。换句话说，一个起点对应唯一一个终点，而一个终点也唯一对应一个起点。进一步画图可以发现，添加一座桥其实相当于交换两个路径的起点对应的的终点。如图：

图中标有相同字母的两个结点对应一组配对的起终点。

不妨假定这个结论是对的，我们将在下面给出维护方法后自然地发现这个结论的正确性。这个观察直接启示我们尝试把每条路径都维护出来。显然每条路径都是一条由结点构成的链，添加一座桥“大致”就相当于交换两条路径的后半部分。这个东西大致可以用 splay 做。之所以是“大致”，是因为添加一座桥以后，桥连接的两个结点将同时存在于两条路径上。这个结构不是很能方便地用 splay 维护出来，我们更希望每个点唯一地对应一条路径。

观察添加一座桥连接 x 和 y 会发生什么：假设 x 的前驱结点是 u，y 的前驱节点是 v。那么加了桥后，u 将沿 x 走到 y；v 将沿 y 走到 u。也就是说，一座桥的本质是交换 x 和 y 的前驱所连接的结点。如图： 不考虑结点个数，我们可以很轻松地按用 splay 维护上右图中的每条链：给每条链开一个 splay，其中序遍历对应从起点到终点的路径。对于一个连接 x,y 的桥，我们把 x 和 y 分别 splay 到对应的树根，然后交换两棵 splay 的右子树即可。

对于一次从 (a,1) 出发的查询，只需要找到这个结点所属的 splay，然后找到这棵 splay 最后一个点，查询它所属的国家即可。

最后一个问题是，一共有 O(nm) 个结点，把它们一开始都建出来是不可接受的。但是注意到大部分连续的节点本质相同且自始至终不会被操作到，可以把一段连续相同的区间缩成 splay 上一个点。每次用到区间内一个点时，把这个区间拆成两个区间（两个点）就可以了。具体来说，一开始每棵 splay 都只有一个点 [1,m+1]，第 a 棵树的这个点对应 (a,1) 到 (a,m + 1) 共 m + 1 个结点。当某次需要用到 (a,b) 这个结点时，找到 (a,b) 所在的区间 [l,r]，然后把区间分成 [l, b - 1] 和 [b, r] 两个点，再插入 splay 即可。此时只需要把 [l,b - 1] 转到根再访问其右子树，就是我们需要交换的部分。

初始时，splay 只有 O(n) 个结点。每次操作至多增加两个结点，一共增加 O(q) 个结点，所以 splay 结点总数是 O(n + q)。

最后是经典结论，多个总节点数为 O(n) 的 splay 互相修改结构（把某棵 splay 的一部分插入到另一棵 splay 上），其 splay 操作的均摊复杂度依然是 O(\log n)。证明思路上可以考虑一次交换子树的操作只会影响两棵树根节点的势能，然后得到总势能的改变量一定是个常数。因为比较繁琐且不是做法的核心，在此略去。

Code

#include <map>
#include <iostream>

const int maxn = 100005;

struct Node {
  Node *fa, *ch[2];
  int bel;

  Node():fa(nullptr), bel(0) {
    ch[0] = ch[1] = nullptr;
  }

  inline int getRela(Node *u) {
    return fa->ch[1] == u;
  }

  void rotate(int x) {
    auto nt = ch[x];
    ch[x] = nt->ch[x ^ 1];
    nt->ch[x ^ 1] = this;
    if (fa) fa->ch[getRela(this)] = nt;
    nt->fa = fa;
    fa = nt;
    if (ch[x]) ch[x]->fa = this;
  }

  void splay() {
    while (fa != nullptr) {
      auto pa = fa->fa;
      if (pa == nullptr) {
        fa->rotate(getRela(this));
      } else {
        int x1 = getRela(this), x2 = fa->getRela(fa);
        if (x1 == x2) {
          pa->rotate(x1);
          fa->rotate(x2);
        } else {
          fa->rotate(x1);
        }
      }
    }
  }
};

int n, m, q;
std::map<int, Node*> node[maxn];

int main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
  std::cin >> n >> m >> q;
  for (int i = 1; i <= n; ++i) {
    auto p = new Node();
    p->bel = i;
    node[i][m + 1] = p;
  }
  for (int op, a, b; q; --q) {
    std::cin >> op >> a;
    if (op == 1) {
      std::cin >> b;
      auto p1 = node[a].lower_bound(b), p2 = node[a + 1].lower_bound(b);
      auto A = p1->second, B = p2->second;
      A->splay(); B->splay();
      auto p3 = new Node, p4 = new Node;
      p3->bel = A->bel;
      p4->bel = B->bel;
      if ((p3->ch[1] = A->ch[1])) {
        p3->ch[1]->fa = p3;
      }
      if ((p4->ch[1] = B->ch[1])) {
        p4->ch[1]->fa = p4;
      }
      A->ch[1] = p4;
      B->ch[1] = p3;
      p3->fa = B; p4->fa = A;
      node[a][p1->first] = p3;
      node[a + 1][p2->first] = p4;
      node[a][b] = A;
      node[a + 1][b] = B;
    } else {
      auto u = node[a].begin()->second;
      u->splay();
      while (u->ch[1]) u = u->ch[1];
      std::cout << u->bel << '\n';
      u->splay();
    }
  }
}