2022 年牛客多校第八场 G 题题解

G Lexicographic Comparison

题意：给定两个长度均为 $nn$ 的排列 $A,PA,P$。有以下 $qq$ 次三类操作：

1. 交换 $A_{x}A\_x$ 与 $A_{y}A\_y$；
2. 交换 $P_{x}P\_x$ 与 $P_{y}P\_y$；
3. 查询 $A{P}^{x}AP^x$ 与 $A{P}^{y}AP^y$ 的大小。其中 $A{P}^{i}AP^i$ 表示排列 $AA$ 在 $PP$ 置换操作下迭代 $ii$ 轮得到的置换。$x,y\le 1\times 10^{18}x,y\; \backslash leq\; 1\backslash times\; 10^\{18\}$。

$n,q\le 1\times 10^{5}n,q\; \backslash leq\; 1\backslash times\; 10^5$。

解法：考虑维护 $PP$ 置换构成的若干个环。显然根据环大小，同时存在的只有 $\mathcal{O}(\sqrt{n})\backslash mathcal\; O(\backslash sqrt\; n)$ 个环。而同一环大小在同一置换次数下一定都处于同一环状态，因而只需要保留环上出现位置最早的那一个环即可。真正在查询操作的时候，枚举每一个环大小，找到出现最早的不同的置换环（若环大小为 $ii$，只要满足 $x\mathrm{m}\mathrm{o}\mathrm{d}i\mathrm{\ne }y\mathrm{m}\mathrm{o}\mathrm{d}ix\; \backslash bmod\; i\; \backslash neq\; y\; \backslash bmod\; i$ 则必然是不同状态），单独考虑它即可。

因而问题转化为，如何快速的维护这些环，需要支持环的拆分和合并，以及快速查询环上第 $kk$ 个元素。可以考虑使用平衡树维护。将所有的环依照下标最小元素作为第一个元素展开成链，形成一个平衡树森林。

首先利用平衡树实现 moveFront 操作：将链 $[l_1,l_2,\cdots ,l_x,\cdots ,l_y,\cdots ,l_k][l\_1,l\_2,\backslash cdots,l\_x,\backslash cdots,l\_y,\backslash cdots,l\_k]$ 中的 $[x,y][x,y]$ 平移到最前。这一步操作可以通过将 $xx$ splay 到根，将 $xx$ 现在的左儿子（$[l_1,l_2,\cdots ,l_{x-1}][l\_1,l\_2,\backslash cdots,l\_\{x-1\}]$ 链部分）摘除，接到整条链的最后面，即 $l_{k}l\_k$ 的右儿子处。

对于合并环操作，仅考虑 $p_x\to xp\_x\; \backslash to\; x$ 与 $p_y\to yp\_y\; \backslash to\; y$ 两条边的影响，即是 $[x,\cdots ,p_x][x,\backslash cdots,p\_x]$ 与 $[y,\cdots ,p_y][y,\backslash cdots,p\_y]$ 链转化为 $[x,\cdots ,p_x,y,\cdots ,p_y][x,\backslash cdots,p\_x,y,\backslash cdots,p\_y]$，因而将 $yy$ 的子树接到 $p_{x}p\_x$（$xx$ 链上最后一个节点）。

对于拆分环操作，仅考虑同一环上的 $p_x\to xp\_x\; \backslash to\; x$ 与 $p_y\to yp\_y\; \backslash to\; y$，首先将 $xx$ 通过 moveFront 移动到链的最前端，此时链上关系为 $[x,\cdots ,p_y,y,\cdots ,p_x][x,\backslash cdots,p\_y,y,\backslash cdots,p\_x]$，需要转化为 $[x,\cdots ,p_y][x,\backslash cdots,p\_y]$ 与 $[y,\cdots ,p_x][y,\backslash cdots,p\_x]$。将 $p_{y}p\_y$ 旋转到根，将 $yy$ 旋转到 $p_{y}p\_y$ 的右儿子，直接摘除 $p_{y}p\_y$ 的右子树即可。

因而查询复杂度 $\mathcal{O}(\sqrt{n})\backslash mathcal\; O(\backslash sqrt\; n)$，修改操作 $\mathcal{O}(\log n)\backslash mathcal\; O(\backslash log\; n)$。

#include <bits/stdc++.h>
using namespace std;
const int N = 100000;
int n, B, A[N + 5], P[N + 5], Qsiz[N + 5];
set<int> S1[320], S2;
class Splay
{
    struct node
    {
        int ch[2];
        int father;
        int minid;
        int siz;
        node()
        {
            ch[0] = ch[1] = 0;
            father = minid = siz = 0;
        }
    } NIL;
    vector<node> t;
    int tot;
    void new_node(int &place, int father)
    {
        place = ++tot;
        node temp = NIL;
        temp.father = father;
        temp.siz = 1;
        temp.minid = place;
        t.push_back(temp);
    }
	void update(int place)
    {
        t[place].minid = place;
        t[place].siz = 1;
        for (int i = 0; i <= 1;i++)
            if (t[place].ch[i])
            {
                t[place].minid = min(t[place].minid, t[t[place].ch[i]].minid);
                t[place].siz += t[t[place].ch[i]].siz;
            }
    }
    void rotate(int now)
    {
        int pre = t[now].father;
        int p = t[pre].father;
        int dir = (t[pre].ch[0] == now);
        t[now].father = p;
        t[pre].father = now;
        t[t[now].ch[dir]].father = pre;
        if (p)
            t[p].ch[t[p].ch[1] == pre] = now;
        t[pre].ch[dir ^ 1] = t[now].ch[dir];
        t[now].ch[dir] = pre;
        update(pre);
    }
    void splay(int place, int tar = 0)
    {
        while (t[place].father != tar)
        {
            int pre = t[place].father;
            if (t[pre].father != tar)
            {
                if ((t[t[pre].father].ch[0] == pre) ^ (t[pre].ch[0] == place))
                    rotate(place);
                else
                    rotate(pre);
            }
            rotate(place);
        }
        update(place);
    }
    int get_root(int x)
    {
        splay(x);
		return t[x].minid;
    }
    void add(int x)//只是在 set 中添加，不会在平衡树上真的添加
    {
        splay(x);
        Qsiz[t[x].minid] = t[x].siz;
        if (t[x].siz <= B)
            S1[t[x].siz].insert(t[x].minid);
        else
            S2.insert(t[x].minid);
    }
    void del(int x)//只是在 set 中删除，不会在平衡树上真的删除
    {
        splay(x);
        if (t[x].siz <= B)
            S1[t[x].siz].erase(t[x].minid);
		else
			S2.erase(t[x].minid);
    }
    int get(int place, int dir)//找到place链的第一个元素（dir=0）和最后一个元素（dir=1）
    {
        splay(place);
        int now = place;
        while (t[now].ch[dir])
            now = t[now].ch[dir];
        splay(now);
        return now;
    }
    int get_rank(int now, long long p)
    {
        splay(now);
        p = (p - 1) % t[now].siz + 1;
        p = (1 + t[now].siz - p) % t[now].siz + 1;
        while (1)
        {
            if (t[t[now].ch[0]].siz + 1 == p)
                break;
            else if (t[t[now].ch[0]].siz >= p)
                now = t[now].ch[0];
            else
            {
                p -= t[t[now].ch[0]].siz + 1;
                now = t[now].ch[1];
            }
        }
        splay(now);
        return now;
    }
    void moveFront(int x)
    {
        splay(x);
        int y = t[x].ch[0];
        if (!y)
            return;
        t[x].ch[0] = 0;
        update(x);
        int r = get(x, 1);
        t[r].ch[1] = y;
        update(r);
        t[y].father = r;
        splay(x);
    }
    void split(int x, int y)//分割环
    {
        del(x);
        moveFront(x);
        int z = P[y];//从P[y]进行切割，即将摘除[y,z]
        splay(z), splay(y, z);//将y的子树（y产生的新环）移动到z
        t[z].ch[1] = 0;//拆分
        update(z);
        t[y].father = 0;
        add(x), add(y);
    }
    void merge(int x, int y)//合并环
    {
        del(x), del(y);
        moveFront(x), moveFront(y);//将x和y分别移动到对应树的最前面
        int z = get(x, 1);
        t[z].ch[1] = y;//将y接到x所在树上
        update(z);
        t[y].father = z;
        add(x);
    }

public:
    Splay(int n)
    {
        t.push_back(NIL);
        tot = 0;
        for (int i = 1; i <= n; i++)
        {
            new_node(i, 0);
            add(i);
        }
    }
    void update_cyc(int x, int y)
    {
        if (x == y)
            return;
        int p = get_root(x), q = get_root(y);
        if (p == q)
            split(x, y);
        else
            merge(x, y);
        swap(P[x], P[y]);
    }
    int query(long long x, long long y, int t)
    {
        moveFront(t);
        int px = get_rank(t, x), py = get_rank(t, y);
        if (A[px] > A[py])
            return 1;
        else if (A[px] < A[py])
            return -1;
        else
            return 0;
    }
};
char buf[10];
int main()
{
	int caset, q;
    long long x, y;
    scanf("%d",&caset);
	while (caset--)
    {
        scanf("%d%d", &n, &q);
        B = sqrt(n) + 1;
        for (int i = 1; i <= n; i++)
            A[i] = P[i] = i;
        Splay solve(n);
        auto query = [&](long long x, long long y)
        {
            if (x == y)
                return 0;
            int t = n + 1;
            for (int i = 1; i <= B; i++)
            {
                if (S1[i].empty() || x % i == y % i)
                    continue;
                t = min(t, *S1[i].begin());
            }
            for (int i : S2)
            {
                int s = Qsiz[i];
                if (x % s == y % s)
                    continue;
                t = min(t, i);
            }
            if (t > n)
                return 0;
            return solve.query(x, y, t);
        };
        while (q--)
        {
            scanf("%s%lld%lld", buf, &x, &y);
            if (buf[0] == 'c')
            {
                int t = query(x, y);
                if (t == -1)
                    printf("<\n");
                else if (t == 1)
                    printf(">\n");
				else
					printf("=\n");
            }
            else if (buf[5] == 'a')
                swap(A[x], A[y]);
            else
                solve.update_cyc(x, y);
        }
        for (int i = 1; i <= B; i++)
            S1[i].clear();
        S2.clear();
	}
	return 0;
}