#include "seats.h"
#include <bits/stdc++.h>
using namespace std;
const int INF = 1e9;
struct Node {
int maxR, minR, maxC, minC;
int val() {
return (maxR-minR+1)*(maxC-minC+1);
}
Node merge(Node b) {
return {max(maxR,b.maxR), min(minR,b.minR), max(maxC,b.maxC) ,min(minC,b.minC)};
}
};
vector<int> R,C;
int H,W;
vector<bool> beautiful;
int beauty;
vector<Node> tr;
void build(int cur, int x, int y) {
if (x == y) {
tr[cur] = {R[x],R[x],C[x],C[x]};
return;
}
int mid = (x+y)/2;
build(cur*2,x,mid);
build(cur*2+1,mid+1,y);
tr[cur] = tr[cur*2].merge(tr[cur*2+1]);
}
void upd(int cur, int x, int y, int pos, int valR, int valC) {
if (y < pos || x > pos) return;
if (x == y) {
tr[cur] = {valR, valR, valC, valC};
return;
}
int mid = (x+y)/2;
upd(cur*2, x, mid, pos, valR, valC);
upd(cur*2+1, mid+1, y, pos, valR, valC);
tr[cur] = tr[cur*2].merge(tr[cur*2+1]);
}
pair<int,int> query(int cur, int x, int y, int t, Node joined) {
if (x == y) {
int val = joined.merge(tr[cur]).val();
if (val > t) return make_pair(x,val);
else return make_pair(H*W,val);
}
int mid = (x+y)/2;
if (joined.merge(tr[cur*2]).val() > t) {
return query(cur*2, x, mid, t, joined);
}
else {
joined = joined.merge(tr[cur*2]);
return query(cur*2 + 1, mid + 1, y, t, joined);
}
}
int findBeauty() {
int t = -1;
int z = -1;
int b = 0;
while (z < H*W) {
pair<int,int> nxt = query(1,0,H*W-1,t,{-INF,INF,-INF,INF});
if (z <= t-1 && t-1 < nxt.first) {
//cout << t << "\n";
b++;
}
tie(z,t) = nxt;
//cout << t << " " << z << "\n";
}
return b;
}
void give_initial_chart(int tempH, int tempW, std::vector<int> tempR, std::vector<int> tempC) {
H = tempH; W = tempW; R = tempR; C = tempC;
tr.resize(4*H*W);
build(1,0,H*W-1);
// cout << query(1,0,H*W-1, 4, {-INF,INF,-INF,INF}) << "\n";
//ftR.build(H*W); ftC.build(H*W);
}
int swap_seats(int a, int b) {
// ftR.upd(a,R[b]); ftR.upd(b,R[a]);
// ftC.upd(a,C[b]); ftC.upd(b,C[a]);
upd(1,0,H*W-1,a,R[b],C[b]);
upd(1,0,H*W-1,b,R[a],C[a]);
swap(R[a],R[b]);
swap(C[a],C[b]);
int res = findBeauty();
//cout << "ans: ";
return res;
}
