USACO 2016 January Contest, Platinum Problem 2. Mowing the Field

原题下载

USACO2016-JAN-P2

答案:

(Analysis by Mark Gordon)

One way to approach this is to try to quickly compute for each vertical line the number of horizontal lines it passes through that were not within T units of being mowed. That is, we'd like to compute the number of horizontal lines that cross line ii as

If we break up the absolute value component into its two respective cases this is a classic range query problem. Since there are three dimensions of interest we can answer queries using a range tree in O(log3n)O(log3n) time. However, since we are allowed to answer queries offline we can remove a log factor by scanning the field from left to right.

We insert a horizontal line when our scan hits the leftmost vertex and delete it when it reaches the rightmost vertex. We perform queries when we reach the x coordinate of a vertical line. Now it's enough to just have a data structure that can do two dimensional range queries and updates.

In my solution I use a binary indexed tree as the first level tree and an allocated-on-demand range tree as the second dimension.

#include <iostream>
#include <vector>
#include <unordered_map>
#include <algorithm>

using namespace std;

#define MAXN (1 << 17)
#define MAXV (1 << 30)

struct node {
  int val;
  struct node* C[2];

  node() {
    val = 0;
    C[0] = C[1] = NULL;
  }

  node* getc(int c) {
    if (!C[c]) {
      C[c] = new node;
    }
    return C[c];
  }

  void add(int x, int v, int lo, int hi) {
    val += v;
    if (hi - lo == 1) {
      return;
    }
    int md = (lo + hi) / 2;
    if (x < md) {
      getc(0)->add(x, v, lo, md);
    } else {
      getc(1)->add(x, v, md, hi);
    }
  }

  int query(int a, int b, int lo, int hi) {
    if (a <= lo && hi <= b) {
      return val;
    } else if (hi <= a || b <= lo) {
      return 0;
    }
    int md = (lo + hi) / 2;
    return (C[0] ? C[0]->query(a, b, lo, md) : 0) +
           (C[1] ? C[1]->query(a, b, md, hi) : 0);
  }
};

node BT[MAXN];

/* Logically executes array[y].add(x, v) += v. */
void bit_add(int x, int y, int v) {
  for(unsigned j = y | MAXN; j < (MAXN << 1); j += j & -j) {
    BT[j ^ MAXN].add(x, v, 0, MAXV);
  }
}

/* Returns the sum of array[i].query(x0, x1) for 0 <= i < y */
int bit_get(int x0, int x1, int y) {
  int ret = 0;
  for(int j = y - 1; y != 0; j &= j - 1) {
    ret += BT[j].query(x0, x1, 0, MAXV);
    if (!j) break;
  }
  return ret;
}

int main() {
  freopen("mowing.in", "r", stdin);
  freopen("mowing.out", "w", stdout);
  ios_base::sync_with_stdio(false);

  int N; cin >> N;
  int T; cin >> T;
  vector<pair<int, int> > A(N);
  for (int i = 0; i < N; i++) {
    cin >> A[i].first >> A[i].second;
  }

  vector<pair<pair<int, int>, pair<int, int> > > ev; /* The horizontal "event" set. */
  vector<pair<pair<int, int>, pair<int, int> > > vseg; /* The vertical query lines. */
  for (int i = 0; i + 1 < N; i++) {
    pair<int, int> p0 = A[i];
    pair<int, int> p1 = A[i + 1];
    if (p1 < p0) swap(p0, p1);
    if (p0.second == p1.second) {
      /* Create insertion and deletion events. */
      ev.push_back(make_pair(make_pair(p0.first + 1, p0.second),
                             make_pair(1, i)));
      ev.push_back(make_pair(p1, make_pair(-1, i)));
    } else {
      /* Create a vertical line query. */
      vseg.push_back(make_pair(p0, make_pair(p1.second, i)));
    }
  }

  /* Sort events and queries by x value. */
  sort(ev.begin(), ev.end());
  sort(vseg.begin(), vseg.end());

  int evi = 0;
  int vsegi = 0;
  int result = 0;
  while (vsegi < vseg.size()) {
    int x = vseg[vsegi].first.first; /* The x-coordinate of our scan. */

    /* Process all horizontal line insertions/deletions. */
    for (; evi < ev.size() && ev[evi].first.first <= x; evi++) {
      bit_add(ev[evi].first.second, ev[evi].second.second,
              ev[evi].second.first);
    }

    /* Perform all vertical line queries. */
    for (; vsegi < vseg.size() && vseg[vsegi].first.first == x; vsegi++) {
      int lo = vseg[vsegi].first.second;
      int hi = vseg[vsegi].second.first;
      int tm1 = vseg[vsegi].second.second - T + 1;
      int tm2 = vseg[vsegi].second.second + T;

      /* Count horizontal lines T or more after this. */
      if (tm2 < MAXN) {
        result += bit_get(lo + 1, hi, MAXN);
        result -= bit_get(lo + 1, hi, tm2);
      }

      /* Count horizontal lines T or more before this. */
      if (tm1 > 0) {
        result += bit_get(lo + 1, hi, tm1);
      }
    }
  }
  cout << result << endl;

  return 0;
}