読者です 読者をやめる 読者になる 読者になる

Codeforces Round #337 Div2 D: Vika and Segments

解法

y座標について Fenwick Tree を作りたいので、y 座標を座標圧縮する。

  1. xを小さい方から順に見ていく。
    1. xで始まる水平方向の区間があれば、それをBITに保存する。
    2. x上にある垂直方向の区間を全て足し合わせる。ただし、水平方向と重なる部分は取り除く。これはBITから取り出せる。
    3. xで終わる水平方向の区間があればそれをBITから取り除く。
  1. yが小さい方から順に見ていく。この時垂直方向と重なる部分は既に取り除いてあるので気にせず普通に足す。

コード

#include <cstdio>
#include <iostream>
#include <sstream>
#include <fstream>
#include <iomanip>
#include <algorithm>
#include <cmath>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <bitset>
#include <numeric>
#include <limits>
#include <climits>
#include <cfloat>
#include <functional>

using namespace std;
typedef signed long long ll;

#define ALL(a) (a.begin()), (a.end())
#define UNIQUE(a) a.erase(unique(a.begin(), a.end()), a.end())

template <typename T>
class FenwickTree {
 private:
  vector<T> bit;
  int M;

 public:
  FenwickTree(int M) : bit(vector<T>(M + 1, 0)), M(M) {}

  int sum(int i) {
    if (!i) return 0;
    return bit[i] + sum(i - (i & -i));
  }

  void add(int i, T x) {
    if (i > M) return;
    bit[i] += x;
    add(i + (i & -i), x);
  }
};

int main() {
  ios::sync_with_stdio(false);
  int N;
  cin >> N;

  vector<int> X1(N), X2(N), Y1(N), Y2(N);
  vector<int> y_inv;
  y_inv.push_back(INT_MIN);
  for (int i = 0; i < N; ++i) {
    int x1, x2, y1, y2;
    cin >> x1 >> y1 >> x2 >> y2;
    if (x2 < x1) swap(x1, x2);
    if (y2 < y1) swap(y1, y2);
    y_inv.push_back(y1 - 1);
    y_inv.push_back(y1);
    y_inv.push_back(y1 + 1);
    y_inv.push_back(y2 - 1);
    y_inv.push_back(y2);
    y_inv.push_back(y2 + 1);
    X1[i] = x1, X2[i] = x2, Y1[i] = y1, Y2[i] = y2;
  }
  sort(ALL(y_inv));
  UNIQUE(y_inv);

  map<int, vector<int>> H_beginning, H_ending;
  map<int, vector<pair<int, int>>> V, H;
  set<int> x_compressed;
  for (int i = 0; i < N; ++i) {
    // 座標圧縮
    Y1[i] = lower_bound(ALL(y_inv), Y1[i]) - y_inv.begin();
    Y2[i] = lower_bound(ALL(y_inv), Y2[i]) - y_inv.begin();
    if (X1[i] == X2[i]) {
      V[X1[i]].push_back({Y1[i], Y2[i]});
      x_compressed.insert(X1[i]);
    } else {
      H_beginning[X1[i]].push_back(Y1[i]);
      H_ending[X2[i]].push_back(Y1[i]);
      H[Y1[i]].push_back({X1[i], X2[i]});
      x_compressed.insert(X1[i]);
      x_compressed.insert(X2[i]);
    }
  }

  FenwickTree<ll> fenwick(y_inv.size());
  map<int, int> y_check;
  ll ans = 0;
  for (int x : x_compressed) {
    //始まっている区間があったら BIT に保存
    for (int y : H_beginning[x]) {
      y_check[y]++;
      if (y_check[y] == 1) fenwick.add(y, 1);
    }

    if (V.count(x)) {
      sort(ALL(V[x]));
      int maximum = INT_MIN;
      for (auto r : V[x]) {
        int y1 = max(r.first, maximum + 1);
        int y2 = r.second;
        if (y1 > y2) continue;
        ans += y_inv[y2] - y_inv[y1] + 1;
        ans -= (fenwick.sum(y2) - fenwick.sum(y1 - 1));
        maximum = y2;
      }
    }

    for (auto y : H_ending[x]) {
      //終わっている区間があったら BIT に反映させる
      y_check[y]--;
      if (y_check[y] == 0) fenwick.add(y, -1);
    }
  }

  for (auto hy : H) {
    vector<pair<int, int>>& x_pair = hy.second;
    sort(ALL(x_pair));
    int maximum = INT_MIN;
    for (auto r : x_pair) {
      int x1 = max(r.first, maximum + 1);
      int x2 = r.second;
      if (x1 > x2) continue;
      ans += x2 - x1 + 1;
      maximum = x2;
    }
  }

  cout << ans << endl;
}