#include "seats.h"
#include<bits/stdc++.h>
using namespace std;
namespace {
int read_int() {
int x;
if (scanf("%d", &x) != 1) {
fprintf(stderr, "Error while reading input\n");
exit(1);
}
return x;
}
} // namespace
const int nmax=1e6+42;
int n,m;
pair<int,int> where[nmax];
vector< vector<int> > inp;
pair<int,int> cnt[nmax];
struct info
{
pair<int,int> mini;
pair<int,int> sum;
int cnt_mini;
};
void print(string s,info a)
{
cout<<s<<" -> ";cout<<a.mini.first<<" "<<a.mini.second<<" , "<<a.sum.first<<" "<<a.sum.second<<" , "<<a.cnt_mini<<endl;
}
info tree[4*nmax];
info my_merge(info a,info b)
{
b.mini={b.mini.first+a.sum.first,b.mini.second+a.sum.second};
if(a.mini==b.mini)
{
a.sum={a.sum.first+b.sum.first,a.sum.second+b.sum.second};
a.cnt_mini+=b.cnt_mini;
return a;
}
if(a.mini>b.mini)swap(a,b);
a.sum={a.sum.first+b.sum.first,a.sum.second+b.sum.second};
return a;
}
void update(int node,int l,int r,int pos,pair<int,int> val)
{
if(l==r)
{
tree[node].mini=val;
tree[node].sum=val;
tree[node].cnt_mini=1;
//cout<<"pos= "<<pos<<" node= "<<node;print(" tree",tree[node]);
return;
}
int av=(l+r)/2;
if(pos<=av)update(node*2,l,av,pos,val);
else update(node*2+1,av+1,r,pos,val);
tree[node]=my_merge(tree[node*2],tree[node*2+1]);
/*
cout<<"node= "<<node<<" l= "<<l<<" r= "<<r<<endl;
print("tree[node*2]",tree[node*2]);
print("tree[node*2+1]",tree[node*2+1]);
print("tree[node]",tree[node]);
cout<<"---"<<endl;
*/
}
int ask(int x,int y)
{
if(0>x||x>=n||0>y||y>=m)return 1e9;
return inp[x][y];
}
void eval(int x,int y)
{
if(0>x||x>=n||0>y||y>=m)return;
int cur[5]={0,0,0,0,0};
int help;
help=1+(ask(x-1,y-1)<inp[x][y])+(ask(x-1,y)<inp[x][y])+(ask(x,y-1)<inp[x][y]);
cur[help]++;
help=1+(ask(x-1,y)<inp[x][y])+(ask(x-1,y+1)<inp[x][y])+(ask(x,y+1)<inp[x][y]);
cur[help]++;
help=1+(ask(x,y-1)<inp[x][y])+(ask(x+1,y-1)<inp[x][y])+(ask(x+1,y)<inp[x][y]);
cur[help]++;
help=1+(ask(x,y+1)<inp[x][y])+(ask(x+1,y+1)<inp[x][y])+(ask(x+1,y)<inp[x][y]);
cur[help]++;
cnt[inp[x][y]]={cur[1]-cur[2],cur[3]-cur[4]};
update(1,0,n*m-1,inp[x][y],cnt[inp[x][y]]);
}
void give_initial_chart(int H, int W, std::vector<int> R, std::vector<int> C)
{
for(int i=0;i<4*nmax;i++)
{
tree[i].mini={10,10};
tree[i].sum={10,10};
}
n=H;
m=W;
for(int t=0;t<n*m;t++)
{
int i=R[t];
int j=C[t];
while(inp.size()<=i)inp.push_back({});
while(inp[i].size()<=j)inp[i].push_back(j);
where[t]={i,j};
inp[i][j]=t;
}
for(int i=0;i<n;i++)
for(int j=0;j<m;j++)
eval(i,j);
}
int swap_seats(int a, int b)
{
swap(inp[where[a].first][where[a].second],inp[where[b].first][where[b].second]);
swap(where[a],where[b]);
for(int x=-1;x<=1;x++)
for(int y=-1;y<=1;y++)
{
eval(where[a].first+x,where[a].second+y);
eval(where[b].first+x,where[b].second+y);
}
//print("tree[1]",tree[1]);
return tree[1].cnt_mini;
}
/*
int main() {
int H = read_int();
int W = read_int();
int Q = read_int();
std::vector<int> R(H * W), C(H * W);
for (int i = 0; i < H * W; ++i) {
R[i] = read_int();
C[i] = read_int();
}
std::vector<int> A(Q), B(Q);
for (int j = 0; j < Q; ++j) {
A[j] = read_int();
B[j] = read_int();
}
give_initial_chart(H, W, R, C);
for (int j = 0; j < Q; ++j) {
int answer = swap_seats(A[j], B[j]);
printf("%d\n", answer);
}
return 0;
}
*/
