#include "seats.h"
#include <bits/stdc++.h>
using namespace std;
const int Nmax = 1e6 + 5;
int N, M, n;
pair<int,int> where[Nmax];
int ans = 0, r1, c1, r2, c2, cnt, val;
int last_ans = -1;
#define left_son (node<<1)
#define right_son ((node<<1)|1)
#define mid ((st+dr)>>1)
class SegTree
{
int mxR[Nmax<<2], mxC[Nmax<<2], mnR[Nmax<<2], mnC[Nmax<<2];
void comb(int node, int x, int y)
{
mxR[node] = max(mxR[x], mxR[y]);
mxC[node] = max(mxC[x], mxC[y]);
mnR[node] = min(mnR[x], mnR[y]);
mnC[node] = min(mnC[x], mnC[y]);
}
public:
void init(int node, int st, int dr)
{
if(st == dr)
{
mxR[node] = mnR[node] = where[st].first;
mxC[node] = mnC[node] = where[st].second;
return;
}
init(left_son, st, mid);
init(right_son, mid+1, dr);
comb(node, left_son, right_son);
}
void update(int node, int st, int dr, int pos)
{
if(st == dr)
{
mxR[node] = mnR[node] = where[st].first;
mxC[node] = mnC[node] = where[st].second;
return;
}
if(pos <= mid) update(left_son, st, mid, pos);
else update(right_son, mid+1, dr, pos);
comb(node, left_son, right_son);
}
void query(int node, int st, int dr, int L, int R, int &r1, int &r2, int &c1, int &c2)
{
if(L <= st && dr <= R)
{
r1 = min(r1, mnR[node]);
r2 = max(r2, mxR[node]);
c1 = min(c1, mnC[node]);
c2 = max(c2, mxC[node]);
return;
}
if(L <= mid) query(left_son, st, mid, L, R, r1, r2, c1, c2);
if(mid < R) query(right_son, mid+1, dr, L, R, r1, r2, c1, c2);
}
} aint;
void enlarge(int x, int y)
{
aint.query(1, 0, n-1, x, y, r1, r2, c1, c2);
}
int solve0(int x, int y)
{
int i;
int ans = last_ans;
r1 = c1 = n;
r2 = c2 = 0;
aint.query(1, 0, n-1, 0, x, r1, r2, c1, c2);
for(i=x; i<y; ++i)
{
if(i + 1 == (r2 - r1 + 1) * (c2 - c1 + 1)) --ans;
r1 = min(r1, where[i+1].first);
r2 = max(r2, where[i+1].first);
c1 = min(c1, where[i+1].second);
c2 = max(c2, where[i+1].second);
}
swap(where[x], where[y]);
aint.update(1, 0, n-1, x);
aint.update(1, 0, n-1, y);
r1 = c1 = n;
r2 = c2 = 0;
aint.query(1, 0, n-1, 0, x, r1, r2, c1, c2);
for(i=x; i<y; ++i)
{
if(i + 1 == (r2 - r1 + 1) * (c2 - c1 + 1)) ++ans;
r1 = min(r1, where[i+1].first);
r2 = max(r2, where[i+1].first);
c1 = min(c1, where[i+1].second);
c2 = max(c2, where[i+1].second);
}
last_ans = ans;
return ans;
}
int swap_seats(int x, int y)
{
if(x > y) swap(x, y);
if(y - x <= 10000 && last_ans != -1) return solve0(x, y);
swap(where[x], where[y]);
aint.update(1, 0, n-1, x);
aint.update(1, 0, n-1, y);
ans = 0;
val = 0;
r1 = r2 = where[0].first;
c1 = c2 = where[0].second;
while(1)
{
if(val + 1 == (r2 - r1 + 1) * (c2 - c1 + 1))
{
++ans;
++val;
if(val == n)
{
last_ans = ans;
return ans;
}
enlarge(val, val);
}
else
{
int cnt = (r2 - r1 + 1) * (c2 - c1 + 1);
enlarge(val + 1, cnt - 1);
val = cnt - 1;
}
}
assert(0);
}
void give_initial_chart(int H, int W, vector<int> R, vector<int> C)
{
int i;
n = H * W;
N = H; M = W;
for(i=0; i < N * M; ++i)
where[i] = {R[i], C[i]};
aint.init(1, 0, n-1);
}
