列表

详情


NC17192. 简单数据结构2

描述

你需要实现m个操作,操作有两种:

1.把序列中所有值为x的数的值变成y

2.找出一个位置i满足ai==x,找出一个位置j满足aj==y,使得|i-j|最小,并输出|i-j|

输入描述

第一行两个数n,m

之后一行n个数,表示序列a

之后m行,每行三个数opt x y

如果opt为1,代表把序列中所有值为x位置的值变成y

如果opt为2,代表找出一个位置i满足ai==x,找出一个位置j满足aj==y,使得|i-j|最小,并输出|i-j|

本题强制在线,输入的x和y需要xor上一次询问的答案

对于第一次询问,上一次答案为0

如果上一次输出`Chtholly`,xor时认为上一次的答案为0

输出描述

对于每个2操作,输出一行一个数表示答案

如果无法找出满足题意的i,j,则输出`Chtholly`

示例1

输入:

5 5
1 2 2 4 4
2 3 3
2 2 4
1 3 2
1 5 5
2 2 5

输出:

Chtholly
1
1

原站题解

上次编辑到这里,代码来自缓存 点击恢复默认模板

C++14(g++5.4) 解法, 执行用时: 488ms, 内存消耗: 49612K, 提交时间: 2020-08-19 20:10:37

#include<bits/stdc++.h>
using namespace std;
#define inf 2100000000
const int maxx=100007;
int n,m,t,a[maxx],b[maxx],num[maxx],bigk[maxx],cnt,ans2[107][maxx],lsq[maxx],typ,x,y;
vector<int>vec[maxx];
void get(int *ans,int x){
    int atp=-inf;
    for(int i=0;i<n;i++){
        if(b[i]==x)atp=i;
        ans[b[i]]=min(ans[b[i]],i-atp);
    }
    atp=inf;
    for(int i=n-1;i>=0;i--){
        if(b[i]==x)atp=i;
        ans[b[i]]=min(ans[b[i]],atp-i);
    }
}
void gb(const vector<int> &szx,const vector<int>&szy){
    int a=szx.size(),b=szy.size();t=0;
    for(int i=0,j=0;i<a||j<b;){
        if(i==a||(j!=b&&szx[i]>szy[j]))lsq[t++]=szy[j++];
        else lsq[t++]=szx[i++];
    }
}
int bl(const vector<int> &szx,const vector<int> &szy){
    int a=szx.size(),b=szy.size(),atp=0x3f3f3f3f;
    for(int i=0,j=0;i<a;i++){
        while(j!=b&&szy[j]<szx[i])j++;
        if(j!=b)atp=min(atp,szy[j]-szx[i]);
        if(j!=0)atp=min(atp,szx[i]-szy[j-1]);
    }return atp;
}
inline void cl2(int x){
    int y=bigk[x],atp=-1;
    for(int i=0;i<n;i++)a[i]=-1;
    for(int i=0;i<=100000;i++)for(int j=vec[i].size()-1;j>=0;j--)a[vec[i][j]]=i;
    for(int i=0;i<=100000;i++)if(bigk[i])ans2[bigk[x]][i]=min(ans2[bigk[x]][i],ans2[bigk[i]][x]);
    for(int i=0;i<n;i++)if(a[i]!=-1){
        if(a[i]==x)atp=i;
        if(atp!=-1)ans2[y][a[i]]=min(ans2[y][a[i]],i-atp);
    }atp=-1;
    for(int i=n-1;i>=0;i--){
        if(a[i]!=-1){
            if(a[i]==x)atp=i;
            if(atp!=-1)ans2[y][a[i]]=min(ans2[y][a[i]],atp-i);
        }
    }vector<int>().swap(vec[x]);
}
int main(){
    memset(ans2,0x3f3f3f3f,sizeof ans2);
    scanf("%d%d",&n,&m);
    int ksize=950;int ans=0;
    for(int i=0;i<n;i++){
        scanf("%d",&b[i]);
        vec[b[i]].push_back(i),num[b[i]]++;
    }
    for(int i=0;i<=100000;i++)if(num[i]>=ksize)get(ans2[bigk[i]=++cnt],i),vector<int>().swap(vec[i]);
    while(m--){
        scanf("%d%d%d",&typ,&x,&y);
        x^=ans,y^=ans;
        if(typ==1){
            if(x==y||num[x]==0)continue;
            gb(vec[x],vec[y]);
            if(num[x]>=ksize&&num[y]>=ksize)for(int i=0;i<=100000;i++)ans2[bigk[y]][i]=min(ans2[bigk[y]][i],ans2[bigk[x]][i]);
            else if((num[x]>=ksize||num[y]>=ksize)&&num[x]>num[y])bigk[y]=bigk[x],bigk[x]=0;
            num[y]+=num[x],num[x]=0,bigk[x]=0,vector<int>().swap(vec[x]),vec[y]=vector<int>(lsq,lsq+t);
            for(int i=1;i<=cnt;i++)ans2[i][y]=min(ans2[i][y],ans2[i][x]),ans2[i][x]=0x3f3f3f3f;
            if((int)vec[y].size()>=ksize){
                if(!bigk[y])bigk[y]=++cnt;
                cl2(y);
            }
        }
        else{
            ans=bl(vec[x],vec[y]);
            if(num[x]>=ksize&&num[y]>=ksize){
                ans=min(ans,ans2[bigk[x]][y]);
                ans=min(ans,ans2[bigk[y]][x]);
            }
            else if(num[x]>=ksize||num[y]>=ksize){
                if(num[y]>=ksize)swap(x,y);
                ans=min(ans,ans2[bigk[x]][y]);
            }
            if(ans==0x3f3f3f3f){puts("Chtholly");ans=0;}
            else printf("%d\n",ans);
        }
    }return 0;
}

上一题