#include "seats.h"
#include <bits/stdc++.h>
using namespace std;
array<int,3> merge(array<int,3> a,array<int,3> b){
array<int,3> c={0,0,0};
c[0]=a[0]+b[0];
c[1]=min(a[1],b[1]+a[0]);
if(c[1]==a[1]) c[2]+=a[2];
if(c[1]==b[1]+a[0]) c[2]+=b[2];
return c;
}
array<int,3> e(){
return {0,1000000000,0};
}
struct segtree{
vector<array<int,3>> nod;
int n;
segtree(){
}
segtree(int n_){
n=1;
while(n<n_) n*=2;
nod.resize(2*n);
for(int i=0;i<2*n;i++) nod[i]={0,0,1};
for(int i=n-1;i>=0;i--){
nod[i]=merge(nod[2*i],nod[2*i+1]);
}
}
void set(int x,array<int,3> v){
x+=n;
nod[x]=v;
while(x>1){
x/=2;
nod[x]=merge(nod[2*x],nod[2*x+1]);
}
}
array<int,3> prod(int l,int r,int a,int b,int k){
if(r<=a||b<=l) return e();
if(l<=a&&b<=r) return nod[k];
return merge(prod(l,r,a,(a+b)/2,2*k),prod(l,r,(a+b)/2,b,2*k+1));
}
array<int,3> prod(int l,int r){
return prod(l,r,0,n,1);
}
};
segtree sg;
int n,m;
vector<int> c,r;
vector<int> rv;
int ans=0;
set<int> rs[1010],cs[1010];
void addv(int x,int v){
auto r=sg.prod(x,x+1);
r[0]+=v;
r[1]+=v;
//cout<<x<<" "<<v<<endl;
sg.set(x,r);
}
void give_initial_chart(int H, int W, std::vector<int> R, std::vector<int> C) {
n=H,m=W;
rv.resize(m);
for(int i=0;i<m;i++) rv[C[i]]=i;
r=C;
C=rv;
C.push_back(m);
reverse(C.begin(),C.end());
C.push_back(m);
reverse(C.begin(),C.end());
c=C;
segtree seg(m+10);
sg=seg;
//0/1 1/2 ... m-1/m
for(int i=0;i+1<c.size();i++){
int x=min(c[i],c[i+1]),y=max(c[i],c[i+1]);
addv(x,1);
addv(y,-1);
}
//for(auto e:c) cout<<e<<" ";
//cout<<endl;
}
int swap_seats(int a, int b) {
int ans=0;
//r[a] と r[b] にいるのを swap する
set<int> s;
s.insert(r[a]+2);
s.insert(r[a]);
s.insert(r[a]+1);
s.insert(r[b]+2);
s.insert(r[b]);
s.insert(r[b]+1);
//cout<<"A"<<" "<<a<<" "<<b<<endl;
//for(auto e:s) cout<<e<<" ";
// cout<<endl;
for(auto i:s){
if(i<0||i+1>=c.size()) continue;
int x=min(c[i],c[i+1]),y=max(c[i],c[i+1]);
addv(x,-1);
addv(y,1);
}
swap(c[r[a]+1],c[r[b]+1]);
swap(r[a],r[b]);
// for(auto e:c) cout<<e<<" ";
// cout<<endl;
for(auto i:s){
if(i<0||i+1>=c.size()) continue;
int x=min(c[i],c[i+1]),y=max(c[i],c[i+1]);
addv(x,1);
addv(y,-1);
}
for(int i=0;i<=m;i++){
auto v=sg.prod(i,i+1);
//cout<<v.sum<<" "<<v.mn<<" "<<v.cnt<<endl;
}
return sg.prod(0,m)[2];
}
