Problem: zero_crossings_ch2 (2022 round3)

**Note: The only difference between this and [Chapter 1](https://www.facebook.com/codingcompetitions/hacker-cup/2022/round-3/problems/E1) is that here, marble locations depend on previous answers.**

There are \(N\) rubber bands on an infinite 2D peg board. The \(i\)th rubber band is initially shaped as a [convex polygon](https://en.wikipedia.org/wiki/Convex_polygon) of \(M_i\) integer vertices, \((X_{i,1}, Y_{i,1}),\) \(\ldots,\) \((X_{i,M_i}, Y_{i,M_i})\) in clockwise order. No two rubber bands touch or cross each other, though each rubber band may be fully enclosed in another. Other than their initial layout, all rubber bands look identical.

You are given \(Q\) queries, the \(i\)th of which involves a red and blue marble shaped as a circle with radius \(1\), centered at points \((A_i, B_i)\) and \((C_i, D_i)\) respectively. The marbles do not touch each other, or any rubber bands. Formally, \((A_i, B_i)\) and \((C_i, D_i)\) are more than \(2\) units away from each other, and each more than \(1\) unit away from any rubber band. 

Query \(i\) asks whether you can roll the marbles and continuously move/deform rubber bands so:
- the red marble ends up at \((C_i, D_i)\),
- the blue marble ends up at \((A_i, B_i)\),
- the final state of all rubber bands looks identical to the initial state (one rubber band may end up in place of another, but must end up having the exact same vertices), and
- rubber bands never touch/cross, and the marbles never touch each other or any rubber band.

For example, the first sample case and the fifth query of the second case can be solved as follows:

{{PHOTO_ID:781832356415299|WIDTH:700}}

Let \(R_i = 1\) if the answer to the \(i\)th query is "yes", else \(R_i = 0\). Please find the sum of \(R_1, ..., R_Q\).

**You'll only be given \(A_1\), \(B_1\), \(C_1\), \(D_1\) directly, and must compute the remaining query points given values \(A_i'\), \(B_i'\), \(C_i'\), \(D_i'\) for \(i \gt 1\) along with an array \(E_{1..Q}\), as follows:**

\[A_i\ := A_i'\ \oplus \ (R_1*E_1)\ \oplus \,\cdots\, \oplus\ (R_{i-1}*E_{1-1})\]

**where \(\oplus\) is the bitwise XOR operator, with \(B_i\), \(C_i\), and \(D_i\) computed similarly. In other words, if the answer to the \(i\)th query is "yes", XOR all future query coordinates by \(E_i\).**


# Constraints

\(1 \le T \le 95\)
\(1 \le N \le 200{,}000\)
\(3 \le M_i \le 250{,}000\)
\(3 \le \sum_{i=1}^{N} M_i \le 800{,}000\)
\(1 \le Q \le 500{,}000\)
\(0 \le X_{ij}, Y_{ij} \le 10^9\)
\(0 \le A_i, B_i, C_i, D_i \le 10^9\)
\(0 \le A_i', B_i', C_i', D_i', E_i \le 10^9\)

The sum of \(M_i\) across all test cases is at most \(3{,}000{,}000\).
The sum of \(Q\) across all test cases is at most \(2{,}000{,}000\).


# Input Format

Input begins with an integer \(T\), the number of test cases. For the \(i\)th test case, there is first a line containing a single integer \(N\). Then, \(N\) descriptions of polygons follow, the \(i\)th of which consists of two lines: the first containing a single integer \(M_i\) and the second containing \(2*M_i\) space-separated integers \(X_{i,1}\), \(Y_{i,1}\), \(\ldots\), \(X_{i,M_i}\), \(Y_{i,M_i}\). Then, there is a line containing a single integer \(Q\). Then, \(Q\) lines follow, the \(i\)th of which contains five space-separated integers, either \(A_1\), \(B_1\), \(C_1\), \(D_1\), \(E_1\) (if \(i = 1\)), or \(A_i'\), \(B_i'\), \(C_i'\), \(D_i'\), \(E_i\) (if \(i \gt 1\)).


# Output Format

For the \(i\)th test case, print `"Case #i: "` followed by a single integer, the sum \(R_1 + ... + R_Q\).


# Sample Explanation

*Note: The samples below are the same as those in chapter 1, only encoded with the scheme above.*

In the first case, the only query is possible, as depicted above on the left.

In the second case, \(R = [1, 1, 0, 0, 1, 1, 0]\).

In the third case, the only query is not possible as one marble is inside the rubber band, while the other is outside. If the marbles swap places, then the rubber band will be surrounding the wrong marble.


Sample input:
4
4
3
17 13 18 11 16 11
4
1 1 1 2 2 2 2 1
8
15 8 15 4 12 1 5 1 2 4 2 8 5 11 12 11
4
5 4 5 8 12 8 12 4
1
7 6 10 6 999
7
6
10 90 20 90 30 80 20 70 10 70 0 80
5
10 0 0 50 10 60 100 100 100 0
4
30 40 30 60 90 90 90 40
4
90 20 90 10 40 10 30 30
3
20 10 10 50 30 20
3
40 50 40 60 50 50
3
60 50 80 70 80 50
7
10 80 20 80 1024
1054 1114 1064 1114 2048
3112 3162 3092 3152 1024
3132 3142 3142 3127 9999999
3092 3092 3112 3092 9999999
10000993 10001013 10000933 10000993 9999999
3162 3102 3102 3162 0
1
3
0 4 7 7 3 0
1
3 4 2 6 0
1
4
0 4 0 1000000000 7 7 3 0
1
3 4 2 6 0


Sample output:
Case #1: 1
Case #2: 4
Case #3: 0
Case #4: 1


Solution: As in the previous chapter, we can determine the tree structure of all the polygons. However, we can no longer process all query points as part of the first sweep, as this chapter requires them to be solved online.

We can use a [persistent binary search tree](http://courses.csail.mit.edu/6.854/06/scribe/s2-persistent.pdf) such as a persistent treap or persistent AVL-tree, which is a BST that's versioned over changes. Inserting and deleting new entries still take \(\mathcal{O}(\log N)\) time, but doing so in a new copy will only take \(\mathcal{O}(\log N)\) additional memory per operation instead of having to copy the whole tree. We can access any version of the tree in \(\mathcal{O}(1)\) as long as we have a pointer to its root.

Specifically, we will keep a version of our persistent BST for each \(x\) coordinate. We can store all the versions in a array, sorted by the \(x\)-coordinate they correspond to. Given a query point \((x, y)\), we can binary search for the right version. After obtaining the version, we can search for the line segment immediately below us, again the upper/lower convex-hull checks to determine the polygon ID containing that point. The rest of the solution is the same as in chapter 1.

Let \(V = \sum_i M_i\) be the total number of vertices. The time and space complexity to build and store all versions of the persistent BST is \(\mathcal{O}(V \log V)\). The time to find the polygon of a query point is \(\mathcal{O}(\log V)\) to first binary search for \(x\), plus another \(\mathcal{O}(\log V)\) to binary search at \(x\) for the segment immediately below \(y\). The overall hashes of nodes can again be checked in \(\mathcal{O}(1)\). Thus the overall time complexity across \(Q\) queries is \(\mathcal{O}((V + Q) \log V)\).


Code: #include <algorithm>
#include <chrono>
#include <iostream>
#include <random>
#include <unordered_map>
#include <vector>
using namespace std;

using LL = long long;

struct Point {
  LL x, y;

  Point() : x(0), y(0) {}
  Point(LL _x, LL _y) : x(_x), y(_y) {}

  bool operator==(const Point &p) const { return x == p.x && y == p.y; }
  bool operator!=(const Point &p) const { return x != p.x || y != p.y; }
  bool operator<(const Point &p) const { return x != p.x ? x < p.x : y < p.y; }
};

struct Line {
  Point left, right;

  Line() : left() {}
  Line(const Point &p1, const Point &p2) : left(p1), right(p2) {
    if (left.x > right.x) {
      swap(left, right);
    }
  }

  bool operator==(const Line &l) const {
    return left == l.left && right == l.right;
  }
  bool is_horizontal() const { return left.y == right.y; }
  bool is_vertical() const { return left.x == right.x; }
};

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

struct Treap {
  Line *key;
  Treap *left, *right;
  int weight;

  Treap() : key(nullptr), left(nullptr), right(nullptr), weight(rng()) {}
  Treap(Line *l) : key(l), left(nullptr), right(nullptr), weight(rng()) {}
};

static Treap *rotate_left(Treap *x) {
  // assert(x && x->left);
  Treap *y = x->left;
  x->left = y->right;
  y->right = x;
  return y;
}

static Treap *rotate_right(Treap *x) {
  // assert(x && x->right);
  Treap *y = x->right;
  x->right = y->left;
  y->left = x;
  return y;
}

template <typename TCompare>
static Treap *persistent_insert(Treap *h, Line *key, const TCompare &cmp) {
  if (!h) {
    return new Treap(key);
  }
  Treap *x = new Treap(*h);
  if (cmp(key, x->key)) {
    x->left = persistent_insert(x->left, key, cmp);
    if (x->left->weight < x->weight) {
      return rotate_left(x);
    }
  } else if (cmp(x->key, key)) {
    x->right = persistent_insert(x->right, key, cmp);
    if (x->right->weight < x->weight) {
      return rotate_right(x);
    }
  } else {
    // assert(false); // Already inserted.
  }
  // assert(x != nullptr);
  return x;
}

static Treap *persistent_remove(Treap *h) {
  if (h->left != nullptr && h->right != nullptr) {
    Treap *y;
    if (h->left->weight < h->right->weight) {
      h->left = new Treap(*h->left);
      y = rotate_left(h);
      y->right = persistent_remove(h);
    } else {
      h->right = new Treap(*h->right);
      y = rotate_right(h);
      y->left = persistent_remove(h);
    }
    return y;
  }
  Treap *next = h->left;
  if (h->right != nullptr) {
    next = h->right;
  }
  // delete h;
  return next;
}

template <typename TCompare>
static Treap *persistent_remove(Treap *h, Line *key, const TCompare &cmp) {
  // assert(h != nullptr);
  Treap *x = new Treap(*h);
  if (cmp(key, x->key)) {
    x->left = persistent_remove(x->left, key, cmp);
  } else if (cmp(x->key, key)) {
    x->right = persistent_remove(x->right, key, cmp);
  } else {
    return persistent_remove(x);
  }
  return x;
}

using TreapPair = pair<Treap *, Treap *>;

template <typename TCompare>
TreapPair floor_and_ceil(Treap *h, const Point &p, const TCompare &cmp) {
  Treap *x = h;
  TreapPair result(nullptr, nullptr);
  while (x) {
    if (cmp(p, x->key)) {
      result.second = x;
      x = x->left;
    } else {
      result.first = x;
      x = x->right;
    }
  }
  return result;
}

template <class It>
pair<vector<Line *>, vector<Line *>> get_lower_and_upper_hull(It lo, It hi) {
  auto cross = [&](const Point &a, const Point &b, const Point &o) {
    return (a.x - o.x)*(b.y - o.y) - (a.y - o.y)*(b.x - o.x);
  };
  int len = distance(lo, hi), k = 0;
  // assert(len >= 3);
  vector<Point> hull(2 * len);
  sort(lo, hi);
  for (It it = lo; it != hi; ++it) {
    while (k >= 2 && cross(hull[k - 1], *it, hull[k - 2]) >= 0) {
      k--;
    }
    hull[k++] = *it;
  }
  int t = k;
  for (It it = hi - 2; it != lo - 1; --it) {
    while (k > t && cross(hull[k - 1], *it, hull[k - 2]) >= 0) {
      k--;
    }
    hull[k++] = *it;
  }
  hull.resize(k);
  vector<Line *> lower, upper;
  for (int i = 1; i < t; i++) {
    upper.push_back(new Line(hull[i - 1], hull[i]));
  }
  for (int i = t; i < k; i++) {
    lower.push_back(new Line(hull[i - 1], hull[i]));
  }
  return make_pair(lower, upper);
}

enum class EventType : int {
  Open = 1,
  Close = 2,
};

struct Event {
  Line *line;
  EventType type;

  Event() : line(nullptr) {}
  Event(Line *_line, const EventType _type) : line(_line), type(_type) {}
};

struct EnclosedPolygons {
  vector<Line *> edges;
  unordered_map<Line *, int> poly_id;
  unordered_map<Line *, bool> is_upper;
  unordered_map<int, int> parent;

  vector<LL> xvals;
  vector<Event> events;
  Treap *tlatest;
  vector<Treap *> tversions;

  static double eval_line(const Line *l, LL x) {
    // assert(!l->is_vertical());
    double m = (double)(l->right.y - l->left.y) / (l->right.x - l->left.x);
    double b = l->left.y - m * l->left.x;
    return m * x + b;
  }

  static bool cmp_point(const Point &p, const Line *l) {
    if (p == l->left || p == l->right) {
      return false;
    }
    return p.y < eval_line(l, p.x);
  }

  EnclosedPolygons(vector<vector<Point>> &_polygons) : tlatest(nullptr) {
    for (size_t i = 0; i < _polygons.size(); ++i) {
      auto &points = _polygons[i];
      for (const Point &p : points) {
        xvals.push_back(p.x);
      }
      auto hulls = get_lower_and_upper_hull(points.begin(), points.end());
      auto add_edge = [&](Line *l) {
        edges.push_back(l);
        events.push_back(Event(l, EventType::Open));
        events.push_back(Event(l, EventType::Close));
        poly_id[l] = i;
      };
      for (Line *l : hulls.first) {
        add_edge(l);
      }
      for (Line *l : hulls.second) {
        add_edge(l);
        is_upper[l] = true;
      }
    }
    sort(xvals.begin(), xvals.end());
    xvals.resize(distance(xvals.begin(), unique(xvals.begin(), xvals.end())));
    auto cmp_events = [&](const Event &a, const Event &b) {
      LL ax = a.type == EventType::Open ? a.line->left.x : a.line->right.x;
      LL ay = a.type == EventType::Open ? a.line->left.y : a.line->right.y;
      LL bx = b.type == EventType::Open ? b.line->left.x : b.line->right.x;
      LL by = b.type == EventType::Open ? b.line->left.y : b.line->right.y;
      if (ax != bx) {
        return ax < bx;
      }
      if (ay != by) {
        return ay < by;
      }
      // We sort Close events first, so we delete from the treap first, thus
      // avoiding comparing equal points.
      if (a.type != b.type) {
        return a.type == EventType::Close;
      }
      // When 2 open events to have the same point, it must be the vertex that
      // joins the upper and lower hull of the same polygon. We will sort the
      // one on the lower hull before.
      // assert(poly_id[a.line] == poly_id[b.line]);
      return ay < max(b.line->left.y, b.line->right.y);
    };
    stable_sort(events.begin(), events.end(), cmp_events);
    parent[0] = -1;
    auto xit = xvals.begin();
    auto eit = events.begin();
    while (xit != xvals.end() && eit != events.end()) {
      LL curr_x = *xit;
      tversions.push_back(tlatest);
      // Returns whether l1 is below l2, assuming they don't intersect.
      auto cmp = [curr_x](const Line *l1, const Line *l2) {
        // First check if equal endpoints as we need a strict BST ordering.
        if (l1->left == l2->left) {
          int x = min(l1->right.x, l2->right.x);
          return eval_line(l1, x) < eval_line(l2, x);  // edges meet at <
        }
        if (l1->right == l2->right) {
          int x = max(l1->left.x, l2->left.x);
          return eval_line(l1, x) < eval_line(l2, x);  // edges meet at >
        }
        if (l1->right == l2->left) {  // edges meet like --l1--x--l2--
          return l1->left.y < l2->right.y;
        }
        if (l1->left == l2->right) {
          // else l1->left == l2->right and edges meet like --l2--x--l1--
          return l1->right.y < l2->left.y;
        }
        return eval_line(l1, curr_x) < eval_line(l2, curr_x);
      };
      // Process all events at this x, starting from the bottom.
      while (eit != events.end()) {
        if (eit->line->is_vertical()) {  // Vertical edges are of no use.
          ++eit;
          continue;
        }
        if (curr_x != (eit->type == EventType::Open ? eit->line->left.x
                                                    : eit->line->right.x)) {
          break;
        }
        int id = poly_id[eit->line];
        if (parent.find(id) == parent.end()) {  // If no parent is found yet...
          LL curr_y = eit->type == EventType::Open ? eit->line->left.y
                                                   : eit->line->right.y;
          auto res = floor_and_ceil(tlatest, Point(curr_x, curr_y), cmp_point);
          Line *line_below = res.first ? res.first->key : nullptr;
          // assert(line_below != nullptr);
          int below_id = poly_id[line_below];
          if (is_upper[line_below]) {
            parent[id] = parent[below_id];
          } else {  // If the line below is a lower hull edge,
            // then it must either be ourself or our parent.
            if (id != below_id) {
              parent[id] = below_id;
            }
          }
        }
        if (eit->type == EventType::Open) {
          tlatest = persistent_insert(tlatest, eit->line, cmp);
        } else {
          tlatest = persistent_remove(tlatest, eit->line, cmp);
        }
        ++eit;
      }
      ++xit;
    }
  }

  int get_containing_polygon(const Point &p) {
    // Search for an x. No need to consider 0, which is an empty treap.
    size_t left = 1, right = xvals.size() - 1;
    while (left + 1 < right) {
      int mid = (left + right) / 2;
      if (xvals[mid] <= p.x) {
        left = mid;
      } else {
        right = mid;
      }
    }
    if (left != right && xvals[left] <= p.x) {
      left = right;
    }
    // Query the line immediately below.
    auto res = floor_and_ceil(tversions[left], p, cmp_point);
    Line *line_below = res.first ? res.first->key : nullptr;
    // assert(line_below != nullptr);
    int below_id = poly_id[line_below];
    return is_upper[line_below] ? parent[below_id] : below_id;
  }

  ~EnclosedPolygons() {
    for (Line *l : edges) {
      delete l;
    }
  }
};

const size_t SEED = chrono::steady_clock::now().time_since_epoch().count();

size_t get_hash(size_t v) {
  size_t x = v + SEED;
  // http://xorshift.di.unimi.it/splitmix64.c
  x += 0x9e3779b97f4a7c15;
  x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
  x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
  return x ^ (x >> 31);
}

vector<size_t> subtree_hash, overall_hash;

void dfs1(int u, const vector<vector<int>> &adj) {
  size_t tot = 0;
  for (int v : adj[u]) {
    dfs1(v, adj);
    tot += subtree_hash[v];
  }
  subtree_hash[u] = get_hash(tot);
}

void dfs2(int u, const vector<vector<int>> &adj, size_t par_hash) {
  overall_hash[u] = get_hash(subtree_hash[u] + get_hash(par_hash));
  for (int v : adj[u]) {
    dfs2(v, adj, overall_hash[u]);
  }
}

int solve() {
  // Set the root node as a giant square enclosing everything.
  const LL LO = -5, HI = (int)1e9 + 5;
  vector<vector<Point>> polygons{{{LO, LO}, {HI, LO}, {HI, HI}, {LO, HI}}};
  int N, Q;
  // Input polygons.
  cin >> N;
  for (int i = 0, M; i < N; i++) {
    cin >> M;
    vector<Point> points;
    for (int j = 0, x, y; j < M; j++) {
      cin >> x >> y;
      points.push_back(Point(x, y));
    }
    polygons.push_back(points);
  }
  EnclosedPolygons EP(polygons);
  // Build graph.
  N++;
  vector<vector<int>> adj(N);
  for (int i = 1; i < N; i++) {
    adj[EP.parent[i]].push_back(i);
  }
  subtree_hash.resize(N);
  overall_hash.resize(N);
  dfs1(0, adj);
  dfs2(0, adj, 0);
  // Process queries.
  cin >> Q;
  int ans = 0, E = 0;
  for (int i = 0, a, b, c, d, e; i < Q; i++) {
    cin >> a >> b >> c >> d >> e;
    a ^= E;
    b ^= E;
    c ^= E;
    d ^= E;
    int u = EP.get_containing_polygon(Point(a, b));
    int v = EP.get_containing_polygon(Point(c, d));
    if (overall_hash[u] == overall_hash[v]) {
      ans++;
      E ^= e;
    }
  }
  return ans;
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  int T;
  cin >> T;
  for (int t = 1; t <= T; t++) {
    cout << "Case #" << t << ": " << solve() << endl;
  }
  return 0;
}