#include <bits/stdc++.h>
#define all(v) v.begin(), v.end()
#define pb push_back
#define lb lower_bound
#define gibon ios::sync_with_stdio(false); cin.tie(0);
#define fi first
#define se second
#define pii pair<int, int>
#define pll pair<ll, ll>
typedef long long ll;
using namespace std;
const int mxN=1001000;
const int mxM=200100;
const int mxK=61;
const int MOD=1e9;
const ll INF=1e18;
int dx[4]={0, 1, 0, -1}, dy[4]={1, 0, -1, 0};
typedef struct lazyseg{
pii seg[4*mxN]={};
int lazy[4*mxN]={};
pii mrg(pii a, pii b){
if(a.fi!=b.fi) return max(a, b);
return pii(a.fi, a.se+b.se);
}
void init(int idx, int s, int e){
seg[idx]=pii(0, e-s+1);
if(s==e) return;
int mid=(s+e)/2;
init(2*idx, s, mid);
init(2*idx+1, mid+1, e);
}
void propagate(int idx){
seg[2*idx].fi+=lazy[idx];
seg[2*idx+1].fi+=lazy[idx];
lazy[2*idx]+=lazy[idx];
lazy[2*idx+1]+=lazy[idx];
lazy[idx]=0;
}
void upd(int idx, int s1, int e1, int s2, int e2, int x){
if(s2>e1 || s1>e2) return;
if(s2<=s1 && e1<=e2){
seg[idx].fi+=x, lazy[idx]+=x;
return;
}
propagate(idx);
int mid=(s1+e1)/2;
upd(2*idx, s1, mid, s2, e2, x);
upd(2*idx+1, mid+1, e1, s2, e2, x);
seg[idx]=mrg(seg[2*idx], seg[2*idx+1]);
}
}lazyseg;
int H, W, Q;
vector <vector <int>> v;
bool Chk[mxN];
pii pos[mxN];
pii qry[mxN];
lazyseg T1;
void input(){
cin >> H >> W >> Q;
v.resize(H);
for(int i=0;i<H;i++) v[i].resize(W);
for(int i=0;i<H*W;i++){
int a, b;
cin >> a >> b;
v[a][b]=i;
pos[i]=pii(a, b);
}
for(int i=1;i<=Q;i++) cin >> qry[i].fi >> qry[i].se;
}
bool not_ok(int a, int b){
return (a<0 || a>=H || b<0 || b>=W);
}
void add(int a, int rev, bool init){
auto [ax, ay]=pos[a];
for(int i=0;i<4;i++){
int nx1=ax+dx[i], ny1=ay+dy[i], nx2=ax+dx[(i+1)%4], ny2=ay+dy[(i+1)%4];
int val1, val2;
if(not_ok(nx1, ny1)) val1=H*W;
else val1=v[nx1][ny1];
if(not_ok(nx2, ny2)) val2=H*W;
else val2=v[nx2][ny2];
if(a<val1 && a<val2){
if(!init) T1.upd(1, 0, H*W-1, a, min(val1, val2)-1, -rev);
else S[a]-=rev, S[min(val1, val2)]+=rev;
}
if(a>val1 && a>val2) {
if(!init) T1.upd(1, 0, H*W-1, max(val1, val2), a-1, -rev);
else S[max(val1, val2)]-=rev, S[a]+=rev;
}
}
}
void add_area(int a, bool rev){ //rev가 true면 제거하는 것
int flag=(rev ? -1 : 1);
auto [ax, ay]=pos[a];
if(Chk[a]==rev) Chk[a]=(!rev), add(a, flag, false);
for(int i=0;i<4;i++){
if(not_ok(ax+dx[i], ay+dy[i])) continue;
int av=v[ax+dx[i]][ay+dy[i]];
if(Chk[av]==rev) Chk[av]=(!rev), add(av, flag, false);
}
}
void init(){
T1.init(1, 0, H*W-1);
for(int i=0;i<H*W;i++){
add(i, 1, true);
Chk[i]=true;
}
for(int i=0;i<H*W;i++){
if(i!=0) S[i]+=S[i-1];
T1.upd(1, 0, H*W-1, i, i, S[i]);
}
}
int swap_seats(int a, int b){
add_area(a, true), add_area(b, true);
auto [ax, ay]=pos[a];
auto [bx, by]=pos[b];
swap(v[ax][ay], v[bx][by]);
swap(pos[a], pos[b]);
add_area(a, false), add_area(b, false);
return (T1.seg[1].fi==-4 ? T1.seg[1].se : 0);
}
void give_initial_chart(int h, int w, vector <int> r, vector <int> c){
H=h, W=w;
v.resize(H);
for(int i=0;i<H;i++) v[i].resize(W);
for(int i=0;i<H*W;i++){
v[r[i]][c[i]]=i;
pos[i]=pii(r[i], c[i]);
}
init();
}
/*
int main()
{
gibon
input();
init();
for(int i=1;i<=Q;i++) cout << swap_seats(qry[i].fi, qry[i].se) << '\n';
}
*/
Compilation message
seats.cpp: In function 'void add(int, int, bool)':
seats.cpp:85:18: error: 'S' was not declared in this scope
85 | else S[a]-=rev, S[min(val1, val2)]+=rev;
| ^
seats.cpp:89:18: error: 'S' was not declared in this scope
89 | else S[max(val1, val2)]-=rev, S[a]+=rev;
| ^
seats.cpp: In function 'void init()':
seats.cpp:110:18: error: 'S' was not declared in this scope
110 | if(i!=0) S[i]+=S[i-1];
| ^
seats.cpp:111:35: error: 'S' was not declared in this scope
111 | T1.upd(1, 0, H*W-1, i, i, S[i]);
| ^
