#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define pb push_back
#define st first
#define nd second
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()
int inf=1000000007;
ll infl=1000000000000000007;
const int N=1000007,pot=1<<20;
bool odw[N];
pair<int,int>seg[2*pot+7];
pair<int,int>seg1[2*pot+7];
int L,R;
vector<pair<int,int>>V;
void del(int v)
{
v+=pot-1;
seg[v].st=-inf;
while(v>1)
{
v/=2;
seg[v]=max(seg[2*v],seg[2*v+1]);
}
}
void del1(int v)
{
v+=pot-1;
seg1[v].st=inf;
while(v>1)
{
v/=2;
seg1[v]=min(seg1[2*v],seg1[2*v+1]);
}
}
pair<int,int>que(int v,int a,int b,int l,int r)
{
if(a<=l&&b>=r) return seg[v];
if(r<a||l>b) return {-inf,0};
return max(que(2*v,a,b,l,(l+r)/2),que(2*v+1,a,b,(l+r)/2+1,r));
}
pair<int,int>que1(int v,int a,int b,int l,int r)
{
if(a<=l&&b>=r) return seg1[v];
if(r<a||l>b) return {inf,0};
return min(que1(2*v,a,b,l,(l+r)/2),que1(2*v+1,a,b,(l+r)/2+1,r));
}
void dfs(int v)
{
del(V[v].st+1);
del1(V[v].nd+1);
odw[v]=1;
L=min(L,V[v].st);
R=max(R,V[v].nd);
while(true)
{
pair<int,int>p=que(1,V[v].st+1,V[v].nd+1,1,pot);
if(p.st<=V[v].nd) break;
if(!odw[p.nd]) dfs(p.nd);
}
while(true)
{
pair<int,int>p=que1(1,V[v].st+1,V[v].nd+1,1,pot);
if(p.st>=V[v].st) break;
if(!odw[p.nd]) dfs(p.nd);
}
}
vector<pair<int,int>>X;
int W[N];
vector<int>G[N];
int s,n;
ll ans=0;
void dfs1(int v)
{
//cout<<v<<endl;
int cL=0,cR=0,S=0;
bool is=0;
for(auto u:G[v])
{
//cout<<v<<" "<<u<<" "<<sz(X)<<endl;
if(X[u-1].st<=s&&X[u-1].nd>=s)
{
dfs1(u);
is=1;
cL+=X[u-1].st-X[v-1].st;
cR+=X[v-1].nd-X[u-1].nd;
}
else if(X[u-1].nd<s) cL-=X[u-1].nd-X[u-1].st;
else cR-=X[u-1].nd-X[u-1].st;
//cout<<v<<" "<<u<<endl;
S+=X[u-1].nd-X[u-1].st;
}
//cout<<v<<" "<<S<<" "<<min(cL,cR)<<endl;
if(v==1) ans-=2*S;
else if(is) ans+=2*min(cL,cR);
}
ll minimum_walk(vector<int>p,int ss)
{
s=ss;
n=sz(p);
for(int i=0;i<n;i++) ans+=abs(i-p[i]);
for(int i=1;i<=2*pot;i++) seg[i].st=-inf;
for(int i=1;i<=2*pot;i++) seg1[i].st=inf;
int c=0;
int A=0,B=n-1;
while(A<s&&p[A]==A) A++;
while(s<B&&p[B]==B) B--;
ans+=2*(B-A);
for(int i=0;i<n;i++)
{
if(odw[i]) continue;
int l=inf,r=-inf,x=i;
while(!odw[x])
{
odw[x]=1;
l=min(l,x);
r=max(r,x);
x=p[x];
}
//cout<<l<<" "<<r<<endl;
if(l==r&&(l<A||l>B)) continue;
seg[l+1+pot-1]={r,c};
seg1[r+1+pot-1]={l,c};
V.pb({l,r});
c++;
}
for(int i=pot-1;i>0;i--)
{
seg[i]=max(seg[2*i],seg[2*i+1]);
if(seg[i].st==inf) cout<<i<<endl;
}
for(int i=pot-1;i>0;i--) seg1[i]=min(seg1[2*i],seg1[2*i+1]);
memset(odw,0,sizeof odw);
int it=2;
X.pb({-1,n});
W[n]=1;
for(int i=0;i<c;i++)
{
if(odw[i]) continue;
L=inf,R=-inf;
dfs(i);
X.pb({L,R});
W[R]=it;
it++;
}
vector<int>Q;
for(int i=0;i<=n;i++)
{
if(W[i]==0) continue;
while(sz(Q)>0&&X[Q.back()-1].st>X[W[i]-1].st)
{
G[W[i]].pb(Q.back());
Q.pop_back();
}
Q.pb(W[i]);
}
dfs1(1);
return ans;
}
int main()
{
int nn,s;
cin>>nn>>s;
vector<int>V(nn);
for(int i=0;i<nn;i++) V[i]=i;
random_shuffle(all(V));
//for(int i=0;i<nn;i++) cout<<V[i]<<" ";
//cout<<endl;
cout<<minimum_walk(V,s);
return 0;
}
Compilation message
/usr/bin/ld: /tmp/ccSCHCVe.o: in function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccCpfdVh.o:books.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status
