#include "seats.h"
#include<bits/stdc++.h>
using namespace std;
const int N = 1e6 + 5;
struct node{
int s, k, ob;
node(){
s = 1e9;
k = ob = 0;
}
node (node a, node b){
s = min(a.s, b.s);
k = ob = 0;
if (a.s == s)k += a.k;
if (b.s == s)k += b.k;
}
};
vector < vector < int > > aa;
int n, m, t, sz;
pair < int, int > p[N];
node tree[N * 4];
inline node mrg(node a, node b){
node c;
c.s = min(a.s, b.s);
c.k = c.ob = 0;
if (a.s == c.s)c.k += a.k;
if (b.s == c.s)c.k += b.k;
return c;
}
inline void push(int v, int l, int r){
if (tree[v].ob == 0)return;
tree[v].s += tree[v].ob;
if (l != r){
tree[v + v].ob += tree[v].ob;
tree[v + v + 1].ob += tree[v].ob;
}
tree[v].ob = 0;
}
inline void add(int v, int l, int r, int ll, int rr, int x){
push(v, l, r);
if (l > r || ll > rr || l > rr || r < ll)return;
if (l >= ll && r <= rr){
tree[v].ob = x;
push(v, l, r);
return;
}
int mid = (l + r) / 2;
add(v + v, l, mid, ll, rr, x);
add(v + v + 1, mid + 1, r, ll, rr, x);
tree[v] = mrg(tree[v + v], tree[v + v + 1]);
}
inline node get(int v, int l, int r, int ll, int rr){
push(v, l, r);
if (l > r || ll > rr || l > rr || r < ll)return node();
if (l >= ll && r <= rr)return tree[v];
int mid = (l + r) / 2;
node x = get(v + v, l, mid, ll, rr), y = get(v + v + 1, mid + 1, r, ll, rr);
tree[v] = mrg(tree[v + v], tree[v + v + 1]);
return mrg(x, y);
}
void give_initial_chart(int H, int W, std::vector<int> R, std::vector<int> C) {
n = H, m = W;
t = n * m;
sz = 1;
while (sz < t){
sz *= 2;
}
for (int i = sz; i <= sz + t - 1; ++i){
tree[i].k = 1;
tree[i].s = 0;
}
for (int i = sz - 1; i > 0; --i){
tree[i].s = 0;
tree[i].k = tree[i + i].k + tree[i + i + 1].k;
}
aa.resize(n + 2);
aa[0].resize(m + 2, t);
for (int i = 1; i <= n; ++i){
aa[i].resize(m + 2);
aa[i][0] = t;
aa[i][m + 1] = t;
}
aa[n + 1].resize(m + 2, t);
for (int i = 0; i < t; ++i){
aa[R[i] + 1][C[i] + 1] = i;
p[i + 1] = make_pair(R[i] + 1, C[i] + 1);
}
vector < int > b;
b.resize(4);
for (int i = 1; i <= n + 1; ++i){
for (int j = 1; j <= m + 1; ++j){
b[0] = aa[i - 1][j - 1], b[1] = aa[i][j - 1], b[2] = aa[i - 1][j], b[3] = aa[i][j];
sort(b.begin(), b.end());
add(1, sz, sz + sz - 1, sz + b[0], sz + b[1] - 1, 1);
add(1, sz, sz + sz - 1, sz + b[2], sz + b[3] - 1, 1);
}
}
}
int swap_seats(int a, int b) {
a++;
b++;
//cout <<a<<" "<<b<<" "<<" "<<p[a].first<<" "<<p[a].second<<" "<<p[b].first<<" "<<p[b].second<<endl;
vector < pair < int, int > > c;
c.push_back(make_pair(p[a].first, p[a].second));
c.push_back(make_pair(p[a].first + 1, p[a].second));
c.push_back(make_pair(p[a].first, p[a].second + 1));
c.push_back(make_pair(p[a].first + 1, p[a].second + 1));
c.push_back(make_pair(p[b].first, p[b].second));
c.push_back(make_pair(p[b].first + 1, p[b].second));
c.push_back(make_pair(p[b].first, p[b].second + 1));
c.push_back(make_pair(p[b].first + 1, p[b].second + 1));
sort(c.begin(), c.end());
c.erase(unique(c.begin(), c.end()), c.end());
vector < int > bb;
bb.resize(4);
for (int e = 0; e < c.size(); ++e){
int i = c[e].first, j = c[e].second;
bb[0] = aa[i - 1][j - 1], bb[1] = aa[i][j - 1], bb[2] = aa[i - 1][j], bb[3] = aa[i][j];
sort(bb.begin(), bb.end());
add(1, sz, sz + sz - 1, sz + bb[0], sz + bb[1] - 1, -1);
add(1, sz, sz + sz - 1, sz + bb[2], sz + bb[3] - 1, -1);
}
//return 0;
swap(aa[p[a].first][p[a].second], aa[p[b].first][p[b].second]);
swap(p[a], p[b]);
for (int e = 0; e < c.size(); ++e){
int i = c[e].first, j = c[e].second;
bb[0] = aa[i - 1][j - 1], bb[1] = aa[i][j - 1], bb[2] = aa[i - 1][j], bb[3] = aa[i][j];
sort(bb.begin(), bb.end());
add(1, sz, sz + sz - 1, sz + bb[0], sz + bb[1] - 1, 1);
add(1, sz, sz + sz - 1, sz + bb[2], sz + bb[3] - 1, 1);
}
node v = get(1, sz, sz + sz - 1, sz, sz + t - 1);
//cout <<v.s<<" "<<v.k<<endl;
if (v.s == 4)return v.k;else return 0;
}
