#include "seats.h"
#include <bits/stdc++.h>
#define vi vector<int>
#define vb vector<bool>
#define vvi vector<vi>
#define loop(i,s,e) for(int i=s;i<e;i++)
#define loopr(i,s,e) for(int i=e-1;i>=s;i--)
#define pb push_back
#define ii pair<int, int>
#define vii vector<ii>
#define x first
#define y second
#define all(a) a.begin(),a.end()
#define chkmax(a,b) a = max(a,b)
#define chkmin(a,b) a = min(a,b)
using namespace std;
const int INF = 1e9;
vi add(vi& a, vi& b){
vi res = a;
loop(i,0,a.size()) res[i]+=b[i];
return res;
}
void apply(vi& a, int x){
loopr(i,0,a.size()-x){
a[i+x] = a[i];
}
loop(i,0,x){
if (i==a.size()) break;
a[i] = 0;
}
}
const vi basic = {1,0,0};
const int N = 1<<21;
int prop[N] = {0};
vi vecs[N] = {basic}, before[N] = {basic};
void setv(int cur){
vecs[cur] = before[cur];
if (prop[cur]>0) apply(vecs[cur], prop[cur]);
}
void pull(int cur){
int dx = min(prop[2*cur], prop[2*cur+1]);
if (dx){
prop[2*cur]-=dx; prop[2*cur+1]-=dx; prop[cur]+=dx;
setv(2*cur); setv(2*cur+1);
}
before[cur] = add(vecs[2*cur], vecs[2*cur+1]);
setv(cur);
}
void build(int cur, int l, int r, vi& a){
if (l+1==r){
before[cur] = basic;
prop[cur] = a[l];
setv(cur);
return ;
}
int mid = (l+r)/2;
build(2*cur, l, mid, a);
build(2*cur+1, mid, r, a);
pull(cur);
}
void update(int cur, int l, int r, int a, int b, int v){
if (a>=r || b<=l) return ;
//cout<<"CUR: "<<cur<<" "<<l<<" "<<r<<endl;
if (a<=l && r<=b){
prop[cur]+=v;
if (l+1==r){
before[cur] = basic;
setv(cur);
}
else pull(cur);
return ;
}
int mid = (l+r)/2;
update(2*cur, l, mid, a,b,v);
update(2*cur+1, mid, r, a,b,v);
pull(cur);
}
int query(){
return vecs[1][2];
}
int n;
vi vals;
vi pos;
void update(int i, int v){
int a = vals[i], b = vals[i+1];
if (a>b) swap(a,b);
update(1,0,n,a,b,v);
}
struct Rec{
int lx, rx, ly, ry;
};
Rec uni(const Rec& a, const Rec& b){
return {min(a.lx, b.lx), max(a.rx, b.rx),
min(a.ly, b.ly), max(a.ry, b.ry)};
}
int val(const Rec& a){
return (a.rx-a.lx+1)*(a.ry-a.ly+1);
}
Rec get(int i, int j){
return {i,i,j,j};
}
int m;
vector<Rec> recs;
vb valss; int sum = 0;
vi r,c;
void update(int i){
sum-=valss[i+1];
recs[i+1] = uni(recs[i], get(r[i], c[i]));
valss[i+1] = (val(recs[i+1])==i+1);
sum+=valss[i+1];
}
bool state = 0;
void give_initial_chart(int H, int W, vi R, vi C) {
if (H>1){
n = H, m = W;
recs.resize(n*m+1, {INF, -INF, INF, -INF});
valss.resize(n*m+1,0);
r = R, c = C;
loop(i,0,n*m){
update(i);
}
}
else{
state = 1;
n = W;
vals.resize(n+2, n); pos = C;
loop(i,0,n) pos[i]++;
loop(i,0,n) vals[pos[i]] = i;
vi pref(n+1);
loop(i,0,n+1){
int a = vals[i], b = vals[i+1];
if (a>b) swap(a,b);
pref[a]++; pref[b]--;
//update(i, 1);
}
loop(i,1,n) pref[i]+=pref[i-1];
//loop(i,0,n) cout<<pref[i]<<" "; cout<<endl;
build(1, 0, n, pref);
}
}
set<int> working;
void Working(int a){
working.insert(a);
working.insert(a-1);
}
int swap_seats(int a, int b) {
if (state){
swap(pos[a], pos[b]);
a = pos[a], b = pos[b];
working.clear();
Working(a); Working(b);
for(auto x:working) update(x,-1);
swap(vals[a], vals[b]);
for(auto x:working) update(x,1);
return query();
}
if (a>b) swap(a,b);
swap(r[a], r[b]); swap(c[a], c[b]);
loop(i,a,b+1){
update(i);
}
return sum;
}
/*
clear
g++ seats.cpp grader.cpp -o a ; ./a
1 5 3
0 0
0 1
0 2
0 3
0 4
0 1
0 3
4 0
*/
