#include "seats.h"
#include <bits/stdc++.h>
using namespace std;
#define int long long
vector<int> r;
map< int, pair<int, int> > indices;
vector< vector< int > > fenwick;
int h, w;
void add(vector< int > &v, int a, int index){
for(int i = index; i <= w; i+=i&-i){
v[i] += a;
}
}
int query(vector< int> &v, int a, int b){
int tot = 0;
for(int i = b; i >= a; i+=i&-i){
tot += v[i];
}
return tot;
}
#undef int
void give_initial_chart(int H, int W, vector<int> R, vector<int> C) {
#define int long long
fenwick.resize(H+1, vector< int > (W+1));
h = H;
w = W;
for(int i = 0; i < H*W; i++){
indices[i] = make_pair(R[i]+1, C[i]+1);
add(fenwick[R[i]+1], i, C[i]+1);
}
#undef int
}
int swap_seats(int a, int b) {
#define int long long
add(fenwick[indices[a].first], b-a, indices[b].second);
add(fenwick[indices[b].first], a-b, indices[a].second);
int xMin = INT_MAX, yMin = INT_MAX, xMax = INT_MIN, yMax = INT_MIN;
int ans = 0;
for(int i = 0; i < h*w; i++){
xMin = min(xMin, (indices[i].second));
yMin = min(yMin, indices[i].first);
xMax = max(xMax, indices[i].second);
yMax = max(yMax, indices[i].first);
int n = (xMax - xMin) * (yMax - yMin);
int obj = (n)*(n-1)/2;
int tot = 0;
for(int j = yMin; j <= yMax; j++){
tot += query(fenwick[j], xMin, xMax);
}
if(tot == obj) ans++;
}
return ans;
}
