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

whiteqwq · 2020-10-29 12:08:08 · 题解

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){//暴力1
    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){//暴力2
    for(int i=1;i<=n;i++)
        if(a[i]==x)
            a[i]=y;
    build(y);
}
void update1(int x,int y){//修改-分类讨论1
    if(size[x]+size[y]<=lim)
        updateA(x,y);
    else updateB(x,y);
}
void update2(int x,int y){//修改-分类讨论2
    if(size[x]+v[y].size()<=lim)
        updateA(x,y);
    else updateB(x,y);
}
void update3(int x,int y){//修改-分类讨论3
    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){//查询-分类讨论1
    return calc(x,y);
}
int query2(int x,int y){//查询-分类讨论2
    return min(ans[id[y]][x],calc(x,y));
}
int query3(int x,int y){//查询-分类讨论3
    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;
}