P5397 天降之物
题面
题解
警告
本题严重卡常，我交了 \(141\) 发才过！
本题严重卡常，我交了 \(141\) 发才过！
本题严重卡常，我交了 \(141\) 发才过！
有一种根号分治的做法，但我不会，我只会序列分块，记块长为 \(B\)。
对于每个块，我们对其进行离散化，开离散化对应数组。
由于离散化后值域只有 \(B\)，这里可以开 \(\mathrm{short}\)，省下一半空间。
然后整块修改就是，考虑是只有 \(x\) 还是只有 \(y\) 还是都有还是都没有，处理一下就好。
块内存下块内答案，然后块间查询是容易的。
总的来说复杂度 \(O(n\sqrt n)\)，严重卡常。
卡常时有一点比较重要的，就是尽可能减少 Cache miss。
Code
#include<bits/stdc++.h>
#pragma optimize(3)
#pragma target("avx")
#pragma optimize("Ofast")
#pragma optimize("inline")
#pragma optimize("-fgcse")
#pragma optimize("-fgcse-lm")
#pragma optimize("-fipa-sra")
#pragma optimize("-ftree-pre")
#pragma optimize("-ftree-vrp")
#pragma optimize("-fpeephole2")
#pragma optimize("-ffast-math")
#pragma optimize("-fsched-spec")
#pragma optimize("unroll-loops")
#pragma optimize("-falign-jumps")
#pragma optimize("-falign-loops")
#pragma optimize("-falign-labels")
#pragma optimize("-fdevirtualize")
#pragma optimize("-fcaller-saves")
#pragma optimize("-fcrossjumping")
#pragma optimize("-fthread-jumps")
#pragma optimize("-funroll-loops")
#pragma optimize("-fwhole-program")
#pragma optimize("-freorder-blocks")
#pragma optimize("-fschedule-insns")
#pragma optimize("inline-functions")
#pragma optimize("-ftree-tail-merge")
#pragma optimize("-fschedule-insns2")
#pragma optimize("-fstrict-aliasing")
#pragma optimize("-fstrict-overflow")
#pragma optimize("-falign-functions")
#pragma optimize("-fcse-skip-blocks")
#pragma optimize("-fcse-follow-jumps")
#pragma optimize("-fsched-interblock")
#pragma optimize("-fpartial-inlining")
#pragma optimize("no-stack-protector")
#pragma optimize("-freorder-functions")
#pragma optimize("-findirect-inlining")
#pragma optimize("-fhoist-adjacent-loads")
#pragma optimize("-frerun-cse-after-loop")
#pragma optimize("inline-small-functions")
#pragma optimize("-finline-small-functions")
#pragma optimize("-ftree-switch-conversion")
#pragma optimize("-foptimize-sibling-calls")
#pragma optimize("-fexpensive-optimizations")
#pragma optimize("-funsafe-loop-optimizations")
#pragma optimize("inline-functions-called-once")
#pragma optimize("-fdelete-null-pointer-checks")
#pragma optimize(2)
using namespace std;
const int T=199;
inline int read(){
int ans=0;
char c=getchar_unlocked();
while(c<'0'||c>'9'){
c=getchar_unlocked();
}
while(c>='0'&&c<='9'){
ans=(ans<<3)+(ans<<1)+c-48;
c=getchar_unlocked();
}
return ans;
}
void write(int x){
if(x<10) putchar(x+48);
else{
write(x/10);
putchar(x%10+48);
}
}
short a[515][T+5][T+5];//第i块内，离散化后j,k的最近距离
short b[100005][515]; //i在第j块内的离散化值
int c[515][T+5];//第i块内第1个j（j为离散化值）真实位置
int d[515][T+5];//第i块内最后1个j（j为离散化值）真实位置
int e[100005];//第i个数所在块
int f[515][T+5];//第i块离散化后为j的数的真实值
int len[515];//各块长
int r[100005];
bool vis[100005];
int n,q,lastans;
int mp[100005];
typedef pair<int,int>P;
priority_queue<int>pq;
signed main(){
memset(a,0x3f,sizeof(a));
n=read(); q=read();
for(register int i=1;i<=n;i++){
r[i]=read();
vis[r[i]]=1;
}
int cnt=0;
clock_t st=clock();
for(register int i=1;i<=n;i++){
if(i<=T) e[i]=1;
else e[i]=e[i-T]+1;
if(e[i]!=e[i-1]){
if(i!=1){
while(!pq.empty()){
int u=pq.top(); pq.pop();
b[u][e[i-1]]=mp[u];
}
for(int j=i-1;e[j]==e[i-1];j--){
mp[f[e[j]][r[j]]]=0;
}
}
cnt=0;
}
len[e[i]]++;
if(mp[r[i]]==0){
mp[r[i]]=++cnt;
f[e[i]][cnt]=r[i];
c[e[i]][cnt]=i;
}
d[e[i]][mp[r[i]]]=i;
pq.push(r[i]);
r[i]=mp[r[i]];
}
while(!pq.empty()){
int u=pq.top(); pq.pop();
b[u][e[n]]=mp[u];
}
clock_t ed=clock();
// exit((ed-st)*1000/CLOCKS_PER_SEC);
for(register short i=1;i<=e[n];i++){
int u=T*(i-1);
for(register int j=1;j<=len[i];j++){
int v=r[j+u];
for(register int k=1;k<=j;k++){
if(a[i][v][r[k+u]]>j-k)
a[i][v][r[k+u]]=a[i][r[k+u]][v]=j-k;
}
}
}
while(q--){
int op=read(),x=read(),y=read();
x^=lastans; y^=lastans;
if(op==1){
if(!vis[x]) continue;
vis[x]=0;
vis[y]=1;
for(register int i=1;i<=e[n];i++){
if(b[x][i]==0) continue;//x不存在
if(b[y][i]==0){//y不存在
f[i][b[y][i]=b[x][i]]=y;
b[x][i]=0;
continue;
}
if(x==y) continue;
//x,y均存在，以下允许O(T)的复杂度
int u=(i-1)*T;
int h=b[y][i];//x,y统一换成离散化值h
int o=b[x][i];//x之前的离散化值
int kkk=len[i];
for(register int j=1;j<=kkk;j++){
if(r[j+u]==o) r[j+u]=h;
if(f[i][j]==0) continue;
if(a[i][j][o]<a[i][j][h])a[i][h][j]=a[i][j][h]=a[i][j][o];
a[i][j][o]=a[i][o][j]=0x3f3f;
}
a[i][o][o]=a[i][o][h]=a[i][h][o]=0x3f3f;
c[i][h]=min(c[i][h],c[i][o]);
d[i][h]=max(d[i][h],d[i][o]);
f[i][o]=b[x][i]=0;
}
}else{
int ans=0x3f3f3f3f;
if(vis[x]&&vis[y]&&x!=y){
for(register int i=1;i<=e[n];i++){
if(a[i][b[x][i]][b[y][i]]<ans){
ans=a[i][b[x][i]][b[y][i]];
if(ans==1) break;
}
}
if(ans==0x3f3f) ans=0x3f3f3f3f;
int beg=-0x3f3f3f3f;
bool flag=0;
if(ans>1)
for(register int i=2;i<=e[n];i++){
if(b[x][i-1]){
beg=d[i-1][b[x][i-1]];
flag=1;
}
if(!flag) continue;
if(b[y][i]){
flag=0;
// ans=min(ans,c[i][b[y][i]]-beg);
if(ans>c[i][b[y][i]]-beg){
ans=c[i][b[y][i]]-beg;
}
}
}
beg=-0x3f3f3f3f;
flag=0;
if(ans>1)
for(register int i=2;i<=e[n];i++){
if(b[y][i-1]){
beg=d[i-1][b[y][i-1]];
flag=1;
}
if(!flag) continue;
if(b[x][i]){
flag=0;
// ans=min(ans,c[i][b[x][i]]-beg);
if(ans>c[i][b[x][i]]-beg){
ans=c[i][b[x][i]]-beg;
}
}
}
}else if(vis[x]&&x==y){
ans=0;
}
if(ans==0x3f3f3f3f) puts("Ikaros");
else{
write(ans); putchar(10);
}
lastans=ans==0x3f3f3f3f?0:ans;
}
}
return 0;
}