#include <bits/stdc++.h>
#include "seats.h"
#define pb push_back
using namespace std;
const int maxn = 1100;
pair<int,int>cords[maxn*maxn];
int h, w;
int result[maxn * maxn];
int cnt;
struct node {
public:
pair<int,int>minv, maxv;
} pref[maxn*maxn];
node query(int i) {
return pref[i];
}
node mergef(node a, node b) {
node c;
c.minv.first = min(a.minv.first, b.minv.first);
c.minv.second = min(a.minv.second, b.minv.second);
c.maxv.first = max(a.maxv.first, b.maxv.first);
c.maxv.second = max(a.maxv.second, b.maxv.second);
return c;
}
/*void update(int x, pair<int,int> uval, int li=0, int ri=h*w-1, int index=1) {
if(li == ri) {
tree[index].minv.first = tree[index].maxv.first = uval.first;
tree[index].minv.second = tree[index].maxv.second = uval.second;
}
else {
int mid = (li+ri)/2;
if(x<=mid) update(x, uval, li, mid, 2*index);
else update(x, uval, mid+1, ri, 2*index+1);
tree[index] = mergef(tree[2*index], tree[2*index+1]);
}
}
node query(int ql, int qr, int li=0, int ri=h*w-1, int index=1) {
if(li > qr || ri < ql) return {{INT_MAX, INT_MAX}, {INT_MIN, INT_MIN}};
else if(li >= ql && ri <= qr) return tree[index];
else {
int mid = (li+ri)/2;
return mergef(query(ql,qr,li,mid,2*index), query(ql,qr,mid+1,ri,2*index+1));
}
}*/
void give_initial_chart(int H, int W, vector<int> R, vector<int> C) {
h = H; w = W;
for(int i=0;i<H*W;i++) {
cords[i].first = R[i];
cords[i].second = C[i];
node curr = {cords[i], cords[i]};
if(i > 0) pref[i] = mergef(curr, pref[i-1]);
else pref[i] = curr;
}
for(int i=0;i<H*W;i++) {
node x = query(i);
int min_x = x.minv.first;
int min_y = x.minv.second;
int max_x = x.maxv.first;
int max_y = x.maxv.second;
if(i + 1 == (max_x-min_x+1)*(max_y-min_y+1)) {
result[i] = 1;
cnt++;
}
}
}
int swap_seats(int a, int b) {
swap(cords[a], cords[b]);
if(a > b) swap(a, b);
for(int i=a;i<=b;i++) {
node curr = {cords[i], cords[i]};
if(i > 0) pref[i] = mergef(curr, pref[i-1]);
else pref[i] = curr;
node x = pref[i];
int min_x = x.minv.first;
int min_y = x.minv.second;
int max_x = x.maxv.first;
int max_y = x.maxv.second;
if(i + 1 == (max_x-min_x+1)*(max_y-min_y+1)) {
if(result[i] == 1) continue;
else {
result[i] = 1;
cnt++;
}
}
else {
if(result[i] == 1) {
result[i] = 0;
cnt--;
}
}
}
return cnt;
}
