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; }