IOI '18 - Seats (37pts)

#include "seats.h"
#include <algorithm>
#include <cassert>
#include <iostream>
#include <set>

using namespace std;

const int INF = 1e8;
const int MX = 4e6 + 10; // maximum hw
int h, w, n;
vector<int> row, col;

int subtask = 6;

// SUBTASK 2

// SUBTASK 3
struct Segtree {
  int N, m;
  int b[MX], t[MX], l[MX], r[MX];
  void setSize(int sz) {
    N = sz, m = 1;
    while (m < N) m <<= 1;
  }
  Segtree(int sz) {setSize(sz);}
  Segtree() {}
  void build() {
    for (int i = 0; i < m; ++i) {
      if (i >= N) b[i] = l[i] = INF, t[i] = r[i] = -INF;
      else {
        b[m+i] = t[m+i] = row[i];
        l[m+i] = r[m+i] = col[i];
      }
    }
    for (int i = m-1; i > 0; --i) {
      b[i] = min(b[2*i], b[2*i+1]);
      t[i] = max(t[2*i], t[2*i+1]);
      l[i] = min(l[2*i], l[2*i+1]);
      r[i] = max(r[2*i], r[2*i+1]);
    }
  }
  void update(int i) {
    i += m;
    b[i] = t[i] = row[i-m];
    l[i] = r[i] = col[i-m];
    while (i > 1) {
      b[i>>1] = min(b[i], b[i^1]);
      t[i>>1] = max(t[i], t[i^1]);
      l[i>>1] = min(l[i], l[i^1]);
      r[i>>1] = max(r[i], r[i^1]);
      i >>= 1;
    }
  }
  pair<pair<int, int>, pair<int, int>> query(int left, int right) {
    int B = INF, T = -INF, L = INF, R = -INF;
    for (left += m, right += m; left < right; left >>= 1, right >>= 1) {
      if (left&1) {
        B = min(B, b[left]);
        T = max(T, t[left]);
        L = min(L, l[left]);
        R = max(R, r[left]);
        left++;
      }
      if (right&1) {
        --right;
        B = min(B, b[right]);
        T = max(T, t[right]);
        L = min(L, l[right]);
        R = max(R, r[right]);
      }
    }
    return {{B, T}, {L, R}};
  }
  int queryGreater(int type, int limit) { // first index with value past some limit
    if (type == 0 && b[1] >= limit) return N;
    if (type == 1 && t[1] <= limit) return N;
    if (type == 2 && l[1] >= limit) return N;
    if (type == 3 && r[1] <= limit) return N;

    int i = 1;
    while (i < m) {
      int left = false;
      if (type == 0 && b[2*i] < limit) left = true;
      else if (type == 1 && t[2*i] > limit) left = true;
      else if (type == 2 && l[2*i] < limit) left = true;
      else if (type == 3 && r[2*i] > limit) left = true;
      i <<= 1;
      if (!left) ++i;
    }
    return i-m;
  }
};
Segtree seg;

// SUBTASK 4
int totalGood = 0;
bool good[MX];
void findGood(int l, int r) { // range [l, r)
  for (int i = l; i < r; ++i) {
    // find the sidelengths of the segment
    auto [p1, p2] = seg.query(0, i+1);
    auto [B, T] = p1; auto [L, R] = p2;

    totalGood -= good[i];
    good[i] = (T-B+1)*(R-L+1)-1 == i;
    totalGood += good[i];
  }
}

void give_initial_chart(int H, int W, vector<int> R, vector<int> C) {
  h = H, w = W, n = H*W, row = R, col = C;
  if (n <= 10000) subtask = 2;
  else if (h <= 1000 && w <= 1000) {
    subtask = 3;
    seg.setSize(n);
    seg.build();
  } else {
    subtask = 4;
    seg.setSize(n);
    seg.build();
    findGood(0, n);
  }
}

int swap_seats(int A, int B) {
  if (subtask == 2) {
    swap(row[A], row[B]);
    swap(col[A], col[B]);
    int beauty = 1;
    int b = row[0], t = row[0], l = col[0], r = col[0];
    for (int i = 1; i < n; ++i) {
      b = min(b, row[i]);
      t = max(t, row[i]);
      l = min(l, col[i]);
      r = max(r, col[i]);
      if ((t-b+1)*(r-l+1) == (i+1)) ++beauty;
    }
    return beauty;
  } else if (subtask == 3) {
    swap(row[A], row[B]);
    swap(col[A], col[B]);
    seg.update(A);
    seg.update(B);

    // main idea: sum of side lengths of good rectangles <= 2000 and strictly increasing
    int beauty = 0;
    int i = 0;
    while (i < n) {
      // i is the start of a new segment with equal sidelength sum
      // first find the sidelengths of the segment
      auto [p1, p2] = seg.query(0, i+1);
      auto [B, T] = p1; auto [L, R] = p2;

      // now let us find the end of the segment
      // i.e. find the first index after i with larger sidelength sum
      int nextB = seg.queryGreater(0, B);
      int nextT = seg.queryGreater(1, T);
      int nextL = seg.queryGreater(2, L);
      int nextR = seg.queryGreater(3, R);
      int j = min({nextB, nextT, nextL, nextR}); // start of next segment

      assert((T-B+1)*(R-L+1)-1 >= j-1);
      if ((T-B+1)*(R-L+1)-1 < j) ++beauty;
      i = j;
    }
    return beauty;
  } else { // Subtask 4
    swap(row[A], row[B]);
    swap(col[A], col[B]);
    seg.update(A);
    seg.update(B);
    if (A > B) swap(A, B);
    findGood(A, B);
    return totalGood;
  }
}