P5397 [Ynoi2018]天降之物解题报告

解题报告

P5397 [Ynoi2018]天降之物

更好的阅读体验

题意

• 给定一个长为$n$的序列$a$，一共$m$个操作：
• 操作$1$：把序列里所有值为$x$的数改为$y$；
• 操作$2$：求序列中值为$x$的位置和值为$y$的位置距离的最小值，如果找不到这样的位置输出Ikaros。
• 强制在线，每次输入的$x$和$y$需要异或上一次的答案，如果这是第一次输出或上一次输出Ikaros，则不需要异或。
• 数据范围：$1\leqslant n=m\leqslant 10^5$，其他所有数在$[1,n]$内。

分析

lxl的毒瘤大分块系列，弑尽破净的第四分块（好中二呀）。

先转换题意：对于每个值都有一个位置集合，支持合并集合（观察题意很容易看出来操作$1$等价于合并集合），查询两个集合中差值最小的值。

我们先考虑两个暴力做法

• 维护每一个值的所有位置，修改就把整个位置集合合并，查询就暴力枚举位置。
• 预处理每一个值离所有其他值的最短距离（这里的预处理可以通过从前到后扫一遍，从后到前扫一遍，做到$O(n)$的实现），修改时$O(n)$暴力重构，查询$O(1)$查询。

但很显然这会时空双爆炸，考虑根号分治来平衡两种暴力的复杂度。

我们先对第一个暴力进行优化，来降低一下复杂度：

我们用$\text{vector}$维护所有的位置，并在其中从小到大排列，合并时可以归并做到$O(n)$，暴力枚举位置可以用两个指针不断推进，利用这个位置的单调性找出每次最近的两个位置更新答案，也可以做到$O(n)$。

设$size_x$为$x$这个值在序列里出现的次数，并规定一个阈值$lim$，进行根号分治。

对于每个$x$，我们保存一个类似缓存的$v_x$（$\text{vector}$型），$\text{lxl}$博客里叫它附属集合，$v$集合需要保存在上一次重构后所有修改操作中加入的新位置，并通过维护保证它的大小不大于$lim$，空间复杂度$O(n\cdot lim)$。

对于所有位置集合大于$lim$的$x$，我们在每一次重构都预处理它里面每个值离其他值的最短距离，设为$ans_{x,y}$（位置集合$x$离值$y$的最短距离），可以发现这样的$x$不超过$\frac{n}{lim}$个，因此我们的空间复杂度为$O(n\cdot lim)$。

现在讲一讲具体操作：

对于修改（注意，这里我们可以进行一定的操作将$x$与$y$交换，因此不妨设$size_x\leqslant size_y$）

• 当$size_x\leqslant lim,size_y\leqslant lim$时
• • 若$size_x+size_y\leqslant lim$，我们就暴力合并$x$和$y$的$v$集合，每一次复杂度为$O(lim)$，总复杂度为$O(m\cdot lim)$。
• • 若$size_x+size_y>lim$，那么我们预处理$ans$，并清空$v$集合，很容易发现这样的操作不超过$\frac{n}{lim}$次，而每一次预处理$ans$是$O(n)$，因此总复杂度是$O(\frac{n^2}{lim})$。
• 当$size_x\leqslant lim,size_y>lim$时
• • 若$size_x+v[y].size()\leqslant lim$，我们暴力把$x$加入到$y$的$v$集合中，总复杂度$O(m\cdot lim)$。
• • 若$size_x+v[y].size()>lim$，重构$y$的$ans$集合，加入$x$和$v[y]$的贡献，并清空$y$的$v$集合，操作数显然不超过$\frac{n}{lim}$，复杂度为$O(\frac{n^2}{lim})$。
• 当$size_x>lim,size_y>lim$时，直接暴力将$x$的所有位置合并到$y$上面，单次复杂度$O(n)$，总复杂度$O(\frac{n^2}{lim})$，理由同上。

对于查询（查询的$x$和$y$顺序不影响答案，因此设$size_x\leqslant size_y$）

• 当$size_x\leqslant lim,size_y\leqslant lim$时，我们采用上述暴力$1$来计算答案，复杂度为$O(lim)$，总复杂度$O(m\cdot lim)$。
• 当$size_x\leqslant lim,size_y>lim$时，采用上述暴力计算$x$的位置集合和$y$的$v$集合的答案，同时别忘了加上$ans[y]$的贡献，总复杂度$O(m\cdot lim)$。
• 当$size_x>lim,size_y>lim$时，采用上述暴力计算$x$和$y$的$v$集合的答案，加上$ans[x]$和$ans[y]$的贡献，总复杂度$O(m\cdot lim)$。

故程序的时间复杂度为$O(\frac{n^2}{lim}+m\cdot lim)$，空间复杂度为$O(n\cdot lim)$，因为$n=m$，所以$lim=\sqrt{n}$的复杂度最优，时间复杂度$O(n\sqrt{n})$，空间复杂度$O(n\sqrt{n})$。

代码

#include<stdio.h>
#include<vector>
#include<string.h>
#include<math.h>
#define inf 0x3f3f3f3f
using namespace std;
const int maxn=1000005,maxt=505;
int n,m,lastans,lim,tot;
int a[maxn],val[maxn],size[maxn],id[maxn],ans[maxt][maxn];
vector<int>v[maxn];
inline int abs(int x){
    return x<0? -x:x;
}
void build(int x){
    int dis;
    if(id[x]==0)
        id[x]=++tot;
    memset(ans[id[x]],0x3f,sizeof(ans[id[x]]));
    v[x].clear();
    dis=inf;
    for(int i=1;i<=n;i++){
        if(a[i]==x)
            dis=0;
        else dis++;
        ans[id[x]][a[i]]=min(ans[id[x]][a[i]],dis);
    }
    dis=inf;
    for(int i=n;i>=1;i--){
        if(a[i]==x)
            dis=0;
        else dis++;
        ans[id[x]][a[i]]=min(ans[id[x]][a[i]],dis);
    }
}
void init(){
    lim=sqrt(n);
    for(int i=1;i<=n;i++)
        val[i]=n+1;
    for(int i=1;i<=n;i++)
        size[a[i]]++,v[a[i]].push_back(i),val[a[i]]=a[i];
    for(int i=1;i<=n;i++)
        if(size[i]>lim)
            build(i);
}
void merge(int x,int y){
    vector<int>res;
    for(int i=0,j=0;i<v[x].size()||j<v[y].size();){
        if(j>=v[y].size()||(i<v[x].size()&&v[x][i]<v[y][j]))
            res.push_back(v[x][i]),i++;
        else res.push_back(v[y][j]),j++;
    }
    v[y]=res;
}
void updateA(int x,int y){
    for(int i=0;i<v[x].size();i++)
        a[v[x][i]]=y;
    for(int i=1;i<=tot;i++)
        ans[i][y]=min(ans[i][y],ans[i][x]);
    merge(x,y);
}
void updateB(int x,int y){
    for(int i=1;i<=n;i++)
        if(a[i]==x)
            a[i]=y;
    build(y);
}
void update1(int x,int y){
    if(size[x]+size[y]<=lim)
        updateA(x,y);
    else updateB(x,y);
}
void update2(int x,int y){
    if(size[x]+v[y].size()<=lim)
        updateA(x,y);
    else updateB(x,y);
}
void update3(int x,int y){
    updateB(x,y);
}
void update(int x,int y){
    if(size[val[x]]==0||val[x]==val[y])
        return ;
    int px=val[x],py=val[y];
    if(size[val[x]]>size[val[y]])
        val[y]=val[x],swap(px,py);
    val[x]=n+1,x=px,y=py;
    if(x==n+1||y==n+1)
        return ;
    if(size[x]<=lim&&size[y]<=lim)
        update1(x,y);
    if(size[x]<=lim&&size[y]>lim)
        update2(x,y);
    if(size[x]>lim&&size[y]>lim)
        update3(x,y);
    size[y]+=size[x],size[x]=0;
    v[x].clear();
}
int calc(int x,int y){
    int i=0,j=0,res=inf;
    if(size[x]==0||size[y]==0)
        return inf;
    while(i<v[x].size()&&j<v[y].size()){
        if(v[x][i]<v[y][j])
            res=min(res,v[y][j]-v[x][i]),i++;
        else res=min(res,v[x][i]-v[y][j]),j++;
    }
    return res;
}
int query1(int x,int y){
    return calc(x,y);
}
int query2(int x,int y){
    return min(ans[id[y]][x],calc(x,y));
}
int query3(int x,int y){
    return min(min(ans[id[x]][y],ans[id[y]][x]),calc(x,y));
}
int query(int x,int y){
    x=val[x],y=val[y];
    if(x==n+1||y==n+1||size[x]==0||size[y]==0)
        return -1;
    if(x==y)
        return 0;
    if(size[x]>size[y])
        swap(x,y);
    if(size[x]<=lim&&size[y]<=lim)
        return query1(x,y);
    if(size[x]<=lim&&size[y]>lim)
        return query2(x,y);
    if(size[x]>lim&&size[y]>lim)
        return query3(x,y);
    return -1;
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    init();
    for(int i=1;i<=m;i++){
        int t,x,y;
        scanf("%d%d%d",&t,&x,&y);
        x^=lastans,y^=lastans;
        if(t==1)
            update(x,y);
        if(t==2){
            int res=query(x,y);
            if(res==-1)
                lastans=0,puts("Ikaros");
            else lastans=res,printf("%d\n",res);
        }
    }
    return 0;
}