#include "seats.h"
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;
#define MAX_N 1000000
#define INF 1000000000
typedef long long ll;
struct S{
int x, y;
};
int h, w, N;
struct T{
int data, lazy;
int cnt, ans, mini;
int s, e;
int l, r;
};
vector<T> seg(1);
vector<S> v;
vector<int> r;
vector<S> s, e;
int ans;
vector<vector<int>> arr;
void init(int x){
if(seg[x].s==seg[x].e) return;
if(seg[x].l==-1){
seg[x].l=(int)seg.size();
seg.push_back(seg[0]);
seg.back().s = seg[x].s; seg.back().e = (seg[x].s+seg[x].e)/2;
seg.back().cnt = seg.back().e-seg.back().s+1; seg.back().ans = seg.back().cnt;
seg.back().l = -1; seg.back().r = -1;
init(seg[x].l);
}
if(seg[x].r==-1){
seg[x].r=(int)seg.size();
seg.push_back(seg[0]);
seg.back().s = (seg[x].s+seg[x].e)/2+1; seg.back().e = seg[x].e;
seg.back().cnt = seg.back().e-seg.back().s+1; seg.back().ans = seg.back().cnt;
seg.back().l = -1; seg.back().r = -1;
init(seg[x].r);
}
}
void update1(int idx){
if(idx==-1) return;
if(seg[idx].lazy!=0){
if(seg[idx].l!=-1){
seg[seg[idx].l].lazy += seg[idx].lazy;
seg[seg[idx].l].mini += seg[idx].lazy;
}
if(seg[idx].r!=-1){
seg[seg[idx].r].lazy += seg[idx].lazy;
seg[seg[idx].r].mini += seg[idx].lazy;
}
seg[idx].lazy = 0;
}
}
void update2(int idx){
if(idx==-1) return;
if(seg[idx].l==-1 && seg[idx].r==-1) return;
if(seg[idx].l==-1){
seg[idx].ans = seg[seg[idx].r].ans;
seg[idx].mini = seg[seg[idx].r].mini;
return;
}
if(seg[idx].r==-1){
seg[idx].ans = seg[seg[idx].l].ans;
seg[idx].mini = seg[seg[idx].l].mini;
return;
}
if(seg[seg[idx].r].mini<seg[seg[idx].l].mini){
seg[idx].ans = seg[seg[idx].r].ans;
seg[idx].mini = seg[seg[idx].r].mini;
return;
}
if(seg[seg[idx].r].mini>seg[seg[idx].l].mini){
seg[idx].ans = seg[seg[idx].l].ans;
seg[idx].mini = seg[seg[idx].l].mini;
return;
}
seg[idx].ans = seg[seg[idx].l].ans + seg[seg[idx].r].ans;
seg[idx].mini = seg[seg[idx].l].mini;
}
void lazy_u(int idx, int x, int y, int z){
if(idx==-1) return;
if(seg[idx].lazy!=0){
if(seg[idx].l!=-1){
seg[seg[idx].l].lazy += seg[idx].lazy;
seg[seg[idx].l].mini += seg[idx].lazy;
}
if(seg[idx].r!=-1){
seg[seg[idx].r].lazy += seg[idx].lazy;
seg[seg[idx].r].mini += seg[idx].lazy;
}
seg[idx].lazy = 0;
}
if(seg[idx].s>=x && seg[idx].e<=y){
seg[idx].mini+=z;
seg[idx].lazy+=z; return;
}
if(seg[idx].e<x || seg[idx].s>y) return;
lazy_u(seg[idx].l, x, y, z);
lazy_u(seg[idx].r, x, y, z);
if(seg[idx].l==-1 && seg[idx].r==-1) return;
if(seg[idx].l==-1){
seg[idx].ans = seg[seg[idx].r].ans;
seg[idx].mini = seg[seg[idx].r].mini;
return;
}
if(seg[idx].r==-1){
seg[idx].ans = seg[seg[idx].l].ans;
seg[idx].mini = seg[seg[idx].l].mini;
return;
}
if(seg[seg[idx].r].mini<seg[seg[idx].l].mini){
seg[idx].ans = seg[seg[idx].r].ans;
seg[idx].mini = seg[seg[idx].r].mini;
return;
}
if(seg[seg[idx].r].mini>seg[seg[idx].l].mini){
seg[idx].ans = seg[seg[idx].l].ans;
seg[idx].mini = seg[seg[idx].l].mini;
return;
}
seg[idx].ans = seg[seg[idx].l].ans + seg[seg[idx].r].ans;
seg[idx].mini = seg[seg[idx].l].mini;
}
vector<int> sq;
int dx[4]={-1, -1, 0, 0}, dy[4]={0, -1, 0, -1};
void give_initial_chart(int H, int W, vector<int> R, vector<int> C) {
seg[0]={0, 0, H*W, H*W, 0, 0, H*W-1, -1, -1};
init(0);
N=H*W;
h=H; w=W;
arr.resize(H);
for(int i=0; i<H; i++){
arr[i].resize(W);
}
for(int i=0; i<R.size(); i++){
v.push_back({R[i], C[i]});
arr[R[i]][C[i]]=i;
}
for(int i=0; i<=H; i++){
for(int j=0; j<=W; j++){
while(!sq.empty()) sq.pop_back();
for(int k=0; k<4; k++){
if(i+dx[k]>=0 && i+dx[k]<H && j+dy[k]>=0 && j+dy[k]<W){
sq.push_back(arr[i+dx[k]][j+dy[k]]);
}
}
sort(sq.begin(), sq.end());
for(int k=0; k<sq.size(); k++){
if(k==0 || k==2){
lazy_u(0, sq[k], N, 1);
}else{
lazy_u(0, sq[k], N, -1);
}
}
}
}
}
int swap_seats(int a, int b) {
for(int i=v[a].x; i<=v[a].x+1; i++){
for(int j=v[a].y; j<=v[a].y+1; j++){
while(!sq.empty()) sq.pop_back();
for(int k=0; k<4; k++){
if(i+dx[k]>=0 && i+dx[k]<h && j+dy[k]>=0 && j+dy[k]<w){
sq.push_back(arr[i+dx[k]][j+dy[k]]);
}
}
sort(sq.begin(), sq.end());
for(int k=0; k<sq.size(); k++){
if(k==0 || k==2){
lazy_u(0, sq[k], N, -1);
}else{
lazy_u(0, sq[k], N, 1);
}
}
}
}
for(int i=v[b].x; i<=v[b].x+1; i++){
for(int j=v[b].y; j<=v[b].y+1; j++){
while(!sq.empty()) sq.pop_back();
for(int k=0; k<4; k++){
if(i+dx[k]>=0 && i+dx[k]<h && j+dy[k]>=0 && j+dy[k]<w){
sq.push_back(arr[i+dx[k]][j+dy[k]]);
}
}
sort(sq.begin(), sq.end());
for(int k=0; k<sq.size(); k++){
if(k==0 || k==2){
lazy_u(0, sq[k], N, -1);
}else{
lazy_u(0, sq[k], N, 1);
}
}
}
}
S tmp = v[a]; v[a] = v[b]; v[b] = tmp;
arr[v[a].x][v[a].y]=a; arr[v[b].x][v[b].y]=b;
for(int i=v[a].x; i<=v[a].x+1; i++){
for(int j=v[a].y; j<=v[a].y+1; j++){
while(!sq.empty()) sq.pop_back();
for(int k=0; k<4; k++){
if(i+dx[k]>=0 && i+dx[k]<h && j+dy[k]>=0 && j+dy[k]<w){
sq.push_back(arr[i+dx[k]][j+dy[k]]);
}
}
sort(sq.begin(), sq.end());
for(int k=0; k<sq.size(); k++){
if(k==0 || k==2){
lazy_u(0, sq[k], N, 1);
}else{
lazy_u(0, sq[k], N, -1);
}
}
}
}
for(int i=v[b].x; i<=v[b].x+1; i++){
for(int j=v[b].y; j<=v[b].y+1; j++){
while(!sq.empty()) sq.pop_back();
for(int k=0; k<4; k++){
if(i+dx[k]>=0 && i+dx[k]<h && j+dy[k]>=0 && j+dy[k]<w){
sq.push_back(arr[i+dx[k]][j+dy[k]]);
}
}
sort(sq.begin(), sq.end());
for(int k=0; k<sq.size(); k++){
if(k==0 || k==2){
lazy_u(0, sq[k], N, 1);
}else{
lazy_u(0, sq[k], N, -1);
}
}
}
}
return seg[0].ans;
}
