【P5397 [Ynoi2018] 天降之物】题解

MoYuFang · 2022-04-02 09:44:19 · 题解

对每种颜色维护有多少位置以及这些位置在哪，然后根号分治。对于颜色 x，若 sz(x)<\sqrt{n} 则用 vector 存位置（有序）称作小团，否则 sz(x)>\sqrt{n}，用 bool 数组存哪些位置上有元素，称作大团。

查询操作涉及小小、大小、大大的查询。

• 对于小小，直接归并两个有序列。
• 对于小大，枚举小块里的元素 i，在大块中查询与 i 最近的元素，因为小团大小为 O(\sqrt{n})，则需要对大团中的 bool 数组分块，使得单次查询 i 的最近值为 O(1)。

记 bid(x) 为 x 所在的块的编号，br(b) 与 bl(b) 分别表示块 b 的右端点和左端点。

为了实现这个操作，只有 bool 数组是不够的，还需要维护数组 bpre,bpst,pre,pst，其中 bpre(b) 表示块 b 前面最近的有元素的块的编号，bpst(b) 表示块 b 后面最近的有元素的块的编号，pre(x) 表示在块 bid(x)中在 x 前最近的元素位置，pst(x) 表示在块 bid(x) 中在 x 后最近的元素位置。

若 bpre(b),pre(x) 不存在则定义为 0，若 bpst(b),pst(x) 不存在则定义为 inf。若 bpre(b)=b 或 bpst(b)=b 则说明块 b 内有元素，若 pre(x)=x 或 pst(x)=x 则说明位置 x 上有元素，于是 bool 数组也可以不要了。

查询位置 x 的答案时，分别找到在 x 前最近的数和在 x 后最近的数，以前者为例，先判断 pre(x) 是否为 0，若是则说明在这个块中没有比 x 前的元素了，找到上一个有元素的块，也就是 bpre(b-1)，再通过 pre(br(bpre(b-1))) 得到在 x 前离 x 最近的元素。

这个过程是 O(1) 的。

• 对于大大，则需要在每个大团中多维护一个数组，记录这个大团与其它大团之间的答案，然后 O(1) 查表回答。

具体的，令 vl(i,j) 表示编号为 i 与 j 的团之间的答案。

合并操作也涉及小小、大小、大大。

• 对于小小，直接合并两个有序列，合并后若大小超过了 \sqrt{n} 则将它变成一个新的大团 i，变成大团时需要求出大团 i 与其它大团 j 之间的答案 vl(i,j) 及 vl(j,i)。
• 对于小大，将小团里的元素插入到大团 i 里，插入时 O(\sqrt{n}) 修改分块数组 bpre,bpst,pre,pst，同时更新 vl(i,j) 和 vl(j,i)。
• 对于大大，则直接合并两个大团的 bpre,bpst,pre,pst,vl 数组。

再来分析一下时间复杂度，小团的大小不超过 \sqrt{n}，大团的个数不超过 \sqrt{n}。

查询小小时用归并，单次 O(\sqrt{n})，查询小大时枚举了小块里的元素，单次 O(\sqrt{n})，查询大大时直接查表，单次 O(1)。

合并小小时用归并，单次 O(\sqrt{n})。但可能还要将小团变成大团 i，此时需要枚举小团里的元素 x 并在每个大团 j 里查询 x 的答案并更新 vl(i,j),vl(j,i)，最多有 \sqrt{n} 次小团变大团，总时间复杂度为 O(n\sqrt{n})。

合并小大涉及到往某个大团里插入某个元素，这个插入的总次数不超过 n，每次插入时需要 O(\sqrt{n}) 维护分块数组和 vl 表。

合并大大时需要合并长度为 n 的数组 pre,pst，单次时间复杂度为 O(n)，总合并次数不超过 \sqrt{n}。

综上，总时间复杂度为 O(n\sqrt{n})，空间复杂度也为 O(n\sqrt{n})。

在实现程序时，为了方便合并操作，可以对每种颜色 x 维护其对应的团编号 team(x)，不存在则置为 -1。这样在将颜色 x 变成颜色 y 时，若 team(x)=-1 说明颜色 x 没有元素，合并操作可以忽略。当 x 对应的是大团，而 y 对应的是小团时，先交换 team(x) 和 team(y)，再将小团合并到大团上去。

大团的操作常数远大于小团的操作常数，增大小团变大团的阀值可以减少大团数量，减少时间常数与空间常数，实现时用的是 3\sqrt{n} 做为阀值。

#include <stdio.h>
#include <algorithm>
#include <string.h>
#include <iostream>
#include <assert.h>
#include <vector> 
#include <cmath>
using namespace std;

#define re register
#define sf scanf
#define pf printf
#define nl() putchar('\n')
#define _for(i, a, b) for(re int i = (a); i < (b); ++i)
#define _rfor(i, a, b) for(re int i = (a); i <= (b); ++i)
#define _dfor(i, b, a) for(re int i = (b); i >= (a); --i)
#define inf 0x7fffffff
#define maxn 100005
#define maxb 1000

int rdnt(){
    re int x = 0, sign = 1;
    re char c = getchar();
    while (c < '0' || c > '9') { if (c == '-') sign = -1; c = getchar(); }
    while (c >= '0' && c <= '9') x = (x<<3) + (x<<1) + (c ^ 48), c = getchar();
    return x * sign;
}

template<class T>
inline void umx(T &x, const T &y){ if (y > x) x = y; }
template<class T>
inline void umi(T &x, const T &y){ if (y < x) x = y; }

int n, m, sqr, mxb, bcnt = 0, col_mp[maxn], big[maxn];
vector<int> vec[maxn];
bool yes[maxb];

#define bid(x) ((x-1)/sqr+1)
#define bl(b) (((b)-1)*sqr+1)
#define br(b) (min(n, (b)*sqr))
struct Block{
    int sz, pre[maxn], pst[maxn], bpre[maxb], bpst[maxb], vl[maxb];
    void init(){
        sz = 0;
        _rfor(i, 0, n+1) pre[i] = 0, pst[i] = inf;
        _rfor(i, 0, mxb+1) bpre[i] = 0, bpst[i] = inf, vl[i] = inf;
    }
    void ins(int x){
        int b = bid(x); ++sz;
        assert(pre[x] < x && pst[x] > x);
        _rfor(i, x, br(b)) if (pre[i] < x) pre[i] = x; else break;
        _dfor(i, x, bl(b)) if (pst[i] > x) pst[i] = x; else break;
        _rfor(i, b, mxb) if (bpre[i] < b) bpre[i] = b; else break;
        _dfor(i, b, 1) if (bpst[i] > b) bpst[i] = b; else break;
    }
    int qry(int x){
        int b = bid(x), ans = inf;
        if (pre[x] > 0) umi(ans, x-pre[x]);
        else if (b > 1 && bpre[b-1] > 0) umi(ans, x-pre[br(bpre[b-1])]);
        if (pst[x] < inf) umi(ans, pst[x]-x);
        else if (b < mxb && bpst[b+1] < inf) umi(ans, pst[bl(bpst[b+1])]-x);
        assert(ans > 0);
        return ans;
    }
} blk[205];

void ins(int b, int x){
    assert(yes[b]);
    blk[b].ins(x);
    _rfor(i, 1, bcnt){
        if (i == b || !yes[i]) continue;
        int tmp = blk[i].qry(x);
        umi(blk[i].vl[b], tmp);
        umi(blk[b].vl[i], tmp);
    }
}

void build(int x){
    int y = ++bcnt; yes[y] = true; blk[y].init();
    for(auto i : vec[x]) assert(i), ins(y, i);
    vector<int> ttt; vec[x].swap(ttt);
}

void merge_ss(int x, int y){
    assert(x != y);
    static int tmp[maxn];
    int sx = vec[x].size(), sy = vec[y].size(), i = 0, j = 0, k = 0;
    while(i < sx || j < sy){
        if (j == sy || (i < sx && vec[x][i] < vec[y][j])) assert(vec[x][i]), tmp[k++] = vec[x][i++];
        else assert(vec[y][j]), tmp[k++] = vec[y][j++];
    }
    vec[x].clear();
    _for(_, 0, k) vec[x].push_back(tmp[_]);
    vector<int> ttt; vec[y].swap(ttt);
}

int qry_ss(int x, int y){
    assert(x != y);
    int sx = vec[x].size(), sy = vec[y].size(), i = 0, j = 0, ans = inf;
    while(i < sx && j < sy){
        assert(vec[x][i] != vec[y][j]);
        if (vec[x][i] < vec[y][j]) umi(ans, vec[y][j]-vec[x][i]), ++i;
        else umi(ans, vec[x][i]-vec[y][j]), ++j;
    }
    assert(ans > 0);
    return ans;
}

void merge_bs(int x, int y){
    for(auto i : vec[y]) ins(x, i);
    vector<int> ttt; vec[y].swap(ttt);
}

int qry_bs(int x, int y){
    assert(yes[x]);
    int ans = inf;
    for(auto i : vec[y]) assert(i), umi(ans, blk[x].qry(i));
    assert(ans > 0);
    return ans;
}

void merge_bb(int x, int y){
    assert(x >= 1 && x <= bcnt);
    assert(y >= 1 && y <= bcnt);
    assert(x != y);
    blk[x].sz += blk[y].sz;
    _rfor(i, 1, n){
        umx(blk[x].pre[i], blk[y].pre[i]);
        umi(blk[x].pst[i], blk[y].pst[i]);
    }
    _rfor(i, 1, mxb){
        umx(blk[x].bpre[i], blk[y].bpre[i]);
        umi(blk[x].bpst[i], blk[y].bpst[i]);
    }
    _rfor(i, 1, bcnt){
        if (i == x || i == y || !yes[i]) continue;
        umi(blk[x].vl[i], blk[y].vl[i]);
        blk[i].vl[x] = blk[x].vl[i];
        blk[i].vl[y] = inf;
    }
    yes[y] = false;
}

int qry_bb(int x, int y){
    assert(x != y);
    assert(blk[x].vl[y] == blk[y].vl[x]);
    assert(blk[x].vl[y] > 0 && blk[x].vl[y] < inf);
    return blk[x].vl[y];
}

int main(){
    #ifndef ONLINE_JUDGE
    freopen("sample.in", "r", stdin);
    freopen("sample.out", "w", stdout);
    #endif

    //ll szof = sizeof(blk) + 8*sizeof(int)*maxn;
    //pf("szof:%lld\n", szof>>20);
    //return 0;
    n = rdnt(); m = rdnt(); sqr = sqrt(n+0.5)*3; mxb = bid(n);
    //pf("n:%d m:%d sqr:%d mxb:%d\n", n, m, sqr, mxb);
    //return 0;
    static int a[maxn];
    _rfor(i, 0, n+1) col_mp[i] = -1, vec[i].clear();
    _rfor(i, 1, n){
        a[i] = rdnt(); assert(a[i] >= 1 && a[i] <= n);
        col_mp[a[i]] = a[i];
        vec[a[i]].push_back(i);
    }
    _rfor(i, 1, n) if (~col_mp[i] && vec[i].size() > sqr) build(i), big[i] = bcnt;

    int lst_ans = 0;
    _rfor(_, 1, m){
        //lst_ans = 0;
        int opt = rdnt(),
            ox = rdnt()^lst_ans, oy = rdnt()^lst_ans,
            x = col_mp[ox], y = col_mp[oy];
        if (opt == 1){
            if (x == -1 || y == -1){ if (~x) swap(col_mp[ox], col_mp[oy]); }
            else{
                if (x == y) continue;
                if (!big[x] && !big[y]){
                    merge_ss(y, x);
                    if (vec[y].size() > sqr) build(y), big[y] = bcnt;
                    col_mp[ox] = -1;
                }
                else if (!big[x] || !big[y]){
                    if (big[x]) swap(col_mp[ox], col_mp[oy]), swap(x, y);
                    merge_bs(big[y], x);
                    col_mp[ox] = -1;
                }
                else{
                    assert(yes[big[x]] && yes[big[y]]);
                    merge_bb(big[y], big[x]);
                    yes[big[x]] = false;
                    col_mp[ox] = -1;
                }
            }
        }
        else if (opt == 2){
            if (x == -1 || y == -1) pf("Ikaros\n"), lst_ans = 0;
            else if (x == y) pf("0\n"), lst_ans = 0;
            else{
                if (!big[x] && !big[y]){
                    lst_ans = qry_ss(x, y);
                }
                else if (!big[x] || !big[y]){
                    if (big[y]) swap(x, y);
                    assert(yes[big[x]]);
                    lst_ans = qry_bs(big[x], y);
                }
                else{
                    assert(yes[big[x]] && yes[big[y]]);
                    lst_ans = qry_bb(big[x], big[y]);
                }
                pf("%d\n", lst_ans);
            }
        }
    }

    return 0;
}