#include <bits/stdc++.h>
#include "books.h"
#warning That's not FB, that's my FB
using namespace std;
using ll = long long;
int inf = 1e9;
int n, s;
int p[1000005], pos[1000005];
vector<vector<int>> cyc;
vector<int> cur;
bool viz[1000005];
void dfs(int nod)
{
viz[nod] = true;
cur.push_back(nod);
if (!viz[p[nod]])
dfs(p[nod]);
}
int vmin[1000005], vmax[1000005];
int rmq_min[21][1000005], rmq_max[21][1000005];
int lg[1000005];
void build()
{
for (int i = 2; i <= n; i++)
lg[i] = 1 + lg[i / 2];
for (int i = 1; i <= n; i++)
{
rmq_min[0][i] = vmin[i];
rmq_max[0][i] = vmax[i];
}
for (int j = 1; j <= lg[n]; j++)
{
for (int i = 1; i <= n - (1 << j) + 1; i++)
{
rmq_min[j][i] = min(rmq_min[j - 1][i], rmq_min[j - 1][i + (1 << (j - 1))]);
rmq_max[j][i] = max(rmq_max[j - 1][i], rmq_max[j - 1][i + (1 << (j - 1))]);
}
}
}
int qmin(int l, int r)
{
int lgg = lg[r - l + 1];
return min(rmq_min[lgg][l], rmq_min[lgg][r - (1 << lgg) + 1]);
}
int qmax(int l, int r)
{
int lgg = lg[r - l + 1];
return max(rmq_max[lgg][l], rmq_max[lgg][r - (1 << lgg) + 1]);
}
pair<int,int> query(int l, int r)
{
pair<int,int> uf = {qmin(l,r),qmax(l,r)};
return uf;
}
pair<int,int> f(pair<int,int> pos)
{
while (true)
{
pair<int,int> repos = query(pos.first,pos.second);
if (repos.first == pos.first and repos.second == pos.second)
break;
pos = repos;
}
return pos;
}
int get_cl(pair<int,int> pos)
{
int cst = 0;
int inip = pos.second;
while (pos.second == inip and pos.first != 1)
{
cst++;
pos.first--;
pos = f(pos);
}
if (pos.second == inip)
return inf;
return cst;
}
int get_cr(pair<int,int> pos)
{
int cst = 0;
int inip = pos.first;
while (pos.first == inip and pos.second != n)
{
cst++;
pos.second++;
pos = f(pos);
}
if (pos.first == inip)
return inf;
return cst;
}
ll minimum_walk(vector<int> PERM, int STR)
{
cyc.clear();
memset(viz,0,sizeof(viz));
n = PERM.size();
for (int i = 1; i <= n; i++)
p[i] = PERM[i - 1] + 1, pos[p[i]] = i;
s = STR + 1;
for (int i = 1; i <= n; i++)
{
if (!viz[i])
{
cur.clear();
dfs(i);
cyc.push_back(cur);
}
}
for (auto it : cyc)
{
sort(it.begin(), it.end());
for (auto itt : it)
vmin[itt] = it[0], vmax[itt] = it.back();
}
build();
ll ans = 0;
for (int i = 1; i <= n; i++)
ans += abs(i - p[i]);
int pzz = 1;
while (pzz < s and p[pzz] == pzz)
ans -= 2, pzz++;
pzz = n;
while (pzz > s and p[pzz] == pzz)
ans -= 2, pzz--;
pair<int,int> pos = f({s,s});
while (pos.first != 1 or pos.second != n)
{
int cl = get_cl(pos), cr = get_cr(pos);
if (cl == inf)
{
while (pos.first != 1)
{
ans += 2;
pos.first--;
pos = f(pos);
}
while (pos.second != n)
{
ans += 2;
pos.second++;
pos = f(pos);
}
}
else
{
if (cl <= cr)
{
for (int i = 1; i <= cl; i++)
{
ans += 2;
pos.first--;
pos = f(pos);
}
}
else
{
for (int i = 1; i <= cr; i++)
{
ans += 2;
pos.second++;
pos = f(pos);
}
}
}
}
return ans;
}
/**
doamne cate try-uri pana sa ajung la greedy-ul corect
daca faceam asta la cf era atat de over
In fine, eu mereu domin un interval [L R] cu prop ca f(L, R) = (L, R)
f(L, R) = (L, R) daca nu exista vreun i in (L R) care sa faca parte dintr-un ciclu care contine un j inn afara (L R)
Altfel f(L, R) = f(intv reunit cu intervalul ciclului aluia kind of stuff), idk doar un aint de minime si maxime
Acum, din (L, R) tu poti plati 2 bani ca sa faci artificial L-- sau R++
Fie cL = nr minim de mutari pe stanga astfel incat daca le faci, te extinzi pana la urma si in dreapta
cR = nr minim de mutari in dreapta astfel incat pana la urma te extinzi in stanga
Proof penal => e optim sa faci mutari in directia cu costul minim (adica faci min(cL, cR) mutari intr-o directie si vezi unde dai)
Ma rog, daca cL = cR = inf (nu poate fi doar una inf si una nu, ofc), spamezi mutari in ambele parti pana ajungi la capat
In fine, la final scazi 2 * (marimea sufixului de p[i] = i + marimea prefixului de p[i] = i)
Kinda se reduce la a gasi cL si cR eficient... chestia funny e ca nu trebuie vreo structura complicata
Gen, daca doar simulezi, oricum mereu te extinzi cu 1 intr-o parte, deci daca faci O(k) query-uri de aint, se va extinde (L, R) la final O(k)
Deci tot O(NlogN) iese sau cv de genul
Ce boti oamenii ca au bagat asa putini 50 -> 100
**/
