#include "seats.h"
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
int h, w;
int x[1000005], y[1000005];
int* grid[1000005];
int delta[1000005];
int dx[] = {-1, 0, 1, 0};
int dy[] = {0, -1, 0, 1};
struct Segtree {
int l, r;
Segtree* lchild;
Segtree* rchild;
int minv, freq, lazy;
};
Segtree* build(int l, int r)
{
Segtree* st = new Segtree;
st->l = l; st->r = r;
st->minv = 0; st->freq = 1; st->lazy = 0;
if (l == r) {
st->lchild = st->rchild = NULL;
} else {
st->lchild = build(l, (l + r) / 2);
st->rchild = build((l + r) / 2 + 1, r);
}
return st;
}
void pushdown(Segtree* st)
{
int val = st->lazy;
st->minv += val;
st->lazy = 0;
if (st->l == st->r) return;
st->lchild->lazy += val;
st->rchild->lazy += val;
}
void modify(Segtree* st, int l, int r, int change)
{
pushdown(st);
if (st->r < l || r < st->l) return;
if (l <= st->l && st->r <= r) {
st->lazy += change;
pushdown(st);
} else {
modify(st->lchild, l, r, change);
modify(st->rchild, l, r, change);
st->minv = min(st->lchild->minv, st->rchild->minv);
if (st->lchild->minv == st->rchild->minv) {
st->freq = st->lchild->freq + st->rchild->freq;
} else if (st->lchild->minv < st->rchild->minv) {
st->freq = st->lchild->freq;
} else {
st->freq = st->rchild->freq;
}
}
}
Segtree* root;
int get_time_weight(int r, int c, int t)
{
//fprintf(stderr, "! %d %d %d\n", r, c, t);
if (grid[r][c] > t) {
int hcnt = 0;
for (int d = 0; d < 4; d++) {
if (r + dx[d] >= 0 && c + dy[d] >= 0 && grid[r + dx[d]][c + dy[d]] <= t) hcnt++;
}
return hcnt >= 2 ? 1 : 0;
} else {
int ccnt = 0;
for (int d = 0; d < 4; d++) {
//printf("! %d %d %d\n", r + dx[d], c + dy[d], (r + dx[d] < 0 || c + dy[d] < 0 || grid[r + dx[d]][c + dy[d]] > t));
if (r + dx[d] < 0 || c + dy[d] < 0 || grid[r + dx[d]][c + dy[d]] > t) {
int d2 = (d + 1) % 4;
if (r + dx[d2] < 0 || c + dy[d2] < 0 || grid[r + dx[d2]][c + dy[d2]] > t) ccnt++;
}
}
//printf("!! %d\n", lcnt);
return ccnt;
}
}
int get_delta(int r, int c)
{
int diff = get_time_weight(r, c, grid[r][c]) - get_time_weight(r, c, grid[r][c] - 1);
for (int d = 0; d < 4; d++) {
int r2 = r + dx[d];
int c2 = c + dy[d];
if (r2 < 0 || r2 >= h || c2 < 0 || c2 >= w) continue;
diff += get_time_weight(r2, c2, grid[r][c]);
diff -= get_time_weight(r2, c2, grid[r][c] - 1);
}
return diff;
}
void update_delta(int r, int c)
{
//fprintf(stderr, "! %d %d\n", r, c);
if (r < 0 || r >= h || c < 0 || c >= w) return;
int id = grid[r][c];
int old_delta = delta[id];
delta[id] = get_delta(r, c);
//fprintf(stderr, "! %d %d\n", r, c);
modify(root, id, h * w - 1, delta[id] - old_delta);
}
void give_initial_chart(int H, int W, vector<int> R, vector<int> C) {
h = H; w = W;
root = build(0, h * w - 1);
for (int i = 0; i <= h; i++) {
grid[i] = new int[w + 1];
}
for (int i = 0; i <= h; i++) {
for (int j = 0; j <= w; j++) {
grid[i][j] = h * w;
}
}
for (int i = 0; i < h * w; i++) {
x[i] = R[i]; y[i] = C[i];
grid[x[i]][y[i]] = i;
//printf("! %d %d %d\n", x[i], y[i], i);
}
//fprintf(stderr, "! %d %d %d\n", grid[0][0], get_time_weight(1, 0, 0), get_time_weight(1, 0, 1));
for (int i = 0; i < h * w; i++) {
update_delta(x[i], y[i]);
//fprintf(stderr, "%d ", delta[i]);
}
//fprintf(stderr, "\n");
}
int swap_seats(int a, int b) {
int x1 = x[a];
int y1 = y[a];
int x2 = x[b];
int y2 = y[b];
swap(grid[x1][y1], grid[x2][y2]);
x[a] = x2; y[a] = y2;
x[b] = x1; y[b] = y1;
for (int d1 = -2; d1 <= 2; d1++) {
for (int d2 = -2; d2 <= 2; d2++) {
if (max(d1, -d1) + max(d2, -d2) > 2) continue;
update_delta(x1 + d1, y1 + d2);
update_delta(x2 + d1, y2 + d2);
}
}
//fprintf(stderr, "! %d %d\n", get_time_weight(1, 1, 1), get_time_weight(1, 1, 2));
/*for (int i = 0; i < h * w; i++) {
fprintf(stderr, "%d ", delta[i]);
}*/
//fprintf(stderr, "\n");
return root->freq;
}
