#include "seats.h"
#include <iostream>
#include <iomanip>
#include <string>
#include <math.h>
#include <algorithm>
#include <cstring>
#include <numeric>
#include <vector>
#include <bitset>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <unordered_map>
#include <unordered_set>
#include <cassert>
using namespace std;
#define dbg(x) cerr<<#x<<": "<<x<<"\n";
using T=pair<pair<long long, long long>, pair<long long, long long>>;
vector<int> r;
struct segtree{
int n;
vector<int>st;
segtree (int n):n(n), st(2*n){}
void update(int posi, int val){
for(st[posi+=n]=val ; posi>1 ; posi/=2) st[posi/2]=st[posi]+st[posi^1];
}
int querie(int l, int r){
r++;
int res=0;
for(l+=n, r+=n ; l<r ; l/=2, r/=2){
if(l&1) res+=st[l++];
if(r&1) res+=st[--r];
}
return res;
}
}st(1000006);
vector<vector<long long>>pref;
vector<pair<int, int>>position;
vector<T>dp;
int maximo, h, w;
void updateY(int x, int y, long long val){
while(y<=w){
pref[x][y]+=val;
y+=y&-y;
}
}
void update(int x, int y, long long val){
while(x<=h){
updateY(x, y, val);
x+=x&-x;
}
}
long long querieY(int x, int y){
long long res=0;
while(y>0){
res+=pref[x][y];
y-=y&-y;
}
return res;
}
long long querie(int x, int y){
long long res=0;
while(x>0){
res+=querieY(x, y);
x-=x&-x;
}
return res;
}
void give_initial_chart(int H, int W, vector<int> R, vector<int> C) {
maximo=H*W;
h=H;
w=W;
position.push_back({0, 0});
pref.resize(H+5, vector<long long>(W+5));
dp.resize(H*W + 10);
for(int i=0 ; i<H*W ; i++){
// pref[R[i]+1][C[i]+1]=i+1;
update(R[i]+1, C[i]+1, i+1);
position.push_back({R[i]+1, C[i]+1});
}
// for(int i=1 ; i<=H ; i++){
// for(int j=1 ; j<=W ; j++) pref[i][j]+=pref[i-1][j]+pref[i][j-1]-pref[i-1][j-1];
// }
for(int i=1 ; i<=H*W ; i++){
if(i==1){
T uwu;
uwu.first={position[i].first, position[i].second};
uwu.second=uwu.first;
dp[i]=uwu;
}else{
T uwu;
uwu=dp[i-1];
uwu.first.first=min(uwu.first.first, (long long)position[i].first);
uwu.first.second=min(uwu.first.second, (long long)position[i].second);
uwu.second.first=max(uwu.second.first, (long long)position[i].first);
uwu.second.second=max(uwu.second.second, (long long)position[i].second);
dp[i]=uwu;
}
long long vale=dp[i].second.first-dp[i].first.first+1, notta=dp[i].second.second-dp[i].first.second+1;
long long vn=vale*notta;
if(vn==i){
st.update(i, 1);
// dbg(i)
}else{
st.update(i, 0);
// dbg(i);
}
}
}
int swap_seats(int a, int b) {
a++; b++;
if(a>b) swap(a, b);
update(position[a].first, position[a].second, b-a);
update(position[b].first, position[b].second, a-b);
swap(position[a], position[b]);
for(int i=a ; i<=b ; i++){
if(i==1){
T uwu;
uwu.first={position[i].first, position[i].second};
uwu.second=uwu.first;
dp[i]=uwu;
}else{
T uwu;
uwu=dp[i-1];
uwu.first.first=min(uwu.first.first, (long long)position[i].first);
uwu.first.second=min(uwu.first.second, (long long)position[i].second);
uwu.second.first=max(uwu.second.first, (long long)position[i].first);
uwu.second.second=max(uwu.second.second, (long long)position[i].second);
dp[i]=uwu;
}
long long vale=dp[i].second.first-dp[i].first.first+1, notta=dp[i].second.second-dp[i].first.second+1;
long long vn=vale*notta;
// vn=(vn*(vn+1))/2;
if(i==4){
// dbg(vn)
}
if(vn==i){
st.update(i, 1);
// dbg(i)
}else{
st.update(i, 0);
// dbg(i);
}
}
// dbg(maximo)
return st.querie(1, maximo);
return 0;
}
