#include "seats.h"
#include <bits/stdc++.h>
using namespace std;
#define nd node
struct node{
int sum,mn,cnt;
node(){
sum=0,mn=1000000000,cnt=0;
}
node(int a,int b,int c){
sum=a,mn=b,cnt=c;
}
};
node merge(node a,node b){
node c;
c.sum=a.sum+b.sum;
c.mn=min(a.mn,b.mn+a.sum);
if(c.mn==a.mn) c.cnt+=a.cnt;
if(c.mn==b.mn+a.sum) c.cnt+=b.cnt;
return c;
}
struct segtree{
vector<nd> 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]=nd(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,nd v){
x+=n;
nod[x]=v;
while(x>1){
x/=2;
nod[x]=merge(nod[2*x],nod[2*x+1]);
}
}
nd prod(int l,int r,int a,int b,int k){
if(r<=a||b<=l) return nd();
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));
}
nd 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.sum+=v;
r.mn+=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).cnt;
}
