[hiho]#1079 : 離散化 線段樹

描述：（原題位址：http://hihocoder.com/problemset/problem/1079?sid=601532）

給定一個區間0~L，以及N條線段(li, ri)，這N條線段按照輸入順序覆寫到0~L區間。0<L<=10^9, 0<=N<=10^5

問最後有幾條線段沒有被完全覆寫？

算是線段樹的另一種使用，雖然标題是離散化，但其實是連續區間下使用線段樹。中間還有一些小問題要處理，就是線段樹的邊界問題。離散情況下，線段樹每一個節點都代表一個個體；連續情況下，每一個節點代表一個區間。也就是，left和right有微妙的變化，離散情況下left = [left, mid], right = [mid + 1, right]; 而連續情況下則是left = [left, mid], right = [mid, right]，算是一個小trick。

小ho提出的方法通俗易懂，由于輸入的區間太大，是以需要做一個映射，把其中使用到的N對資料映射到0~2N之間，這樣就可以放心地用線段樹了。

不過我一開始想的是，不做映射，而是按需分區間。一開始就是一個0~L的Node，然後當有線段插入這個節點的時候，再去把這個節點分開。我這裡用的是二分，更快的方法可能是根據輸入的線段來分左右。

最後兩種方法都能AC，時間上也差不多。代碼如下：

映射方法：

// Problems.cpp : Defines the entry point for the console application.
//
#include <sstream>
#include <stdio.h>
#include <functional>
#include <string.h>
#include <iomanip>
#include <time.h>
#include <math.h>
#include <fstream>
#include <iostream>
#include <vector>
#include <stack>
#include <queue>
#include <tuple>
#include <map>
#include <string>
#include <set>
#include <algorithm>
#include <list>
#include <unordered_set>
#include <unordered_map>

using namespace std;
typedef long long ll;
const int MAXPRIME = 1000000007;

class Node {
public:
  static unordered_set<int> mark;
  bool same;
  int id;
  int rangeleft, rangeright, mid;
  Node *left, *right;
  Node(int l, int r) : same(false), id(-1), left(NULL), right(NULL) {
    mid = rangeleft = l, rangeright = r;
    if (l + 1 == r) return;
    mid = (l + r) >> 1;
    left = new Node(l, mid);
    right = new Node(mid, r);
  }
  void add(int i, int l, int r) {
    if (l <= rangeleft && r >= rangeright) {
      same = true;
      id = i;
      return;
    }
    if (same) {
      right->same = left->same = true;
      left->id = right->id = id;
      same = false;
    }
    if (r <= mid) {
      left->add(i, l, r);
    }
    else if (l >= mid) {
      right->add(i, l, r);
    }
    else {
      left->add(i, l, mid);
      right->add(i, mid, r);
    }
  }
  void count() {
    if (same) {
      mark.insert(id);
      return;
    }
    if (left) left->count();
    if (right) right->count();
  }
};
unordered_set<int> Node::mark;
void pro() {
  Node::mark.clear();
  int n, m;
  cin >> n >> m;
  vector<int> data;
  while (n--) {
    int a, b;
    cin >> a >> b;
    data.push_back(a);
    data.push_back(b);
  }
  vector<int> ind = data;
  sort(ind.begin(), ind.end());
  auto it = unique(ind.begin(), ind.end());
  ind.erase(it, ind.end());
  map<int, int> mp;
  n = ind.size();
  for (int i = 0; i < n; ++i) {
    mp[ind[i]] = i;
    ind[i] = i;
  }
  Node *root = new Node(0, n);
  for (int i = 0; i < data.size(); i += 2) {
    root->add(i, mp[data[i]], mp[data[i + 1]]);
  }
  root->count();
  cout << Node::mark.size() << endl;
}

void handle() {
  pro();
}

int main() {

  handle();
  system("PAUSE");

  return 0;
}
           

按需劃分：

// Problems.cpp : Defines the entry point for the console application.
//
#include <sstream>
#include <stdio.h>
#include <functional>
#include <string.h>
#include <iomanip>
#include <time.h>
#include <math.h>
#include <fstream>
#include <iostream>
#include <vector>
#include <stack>
#include <queue>
#include <tuple>
#include <map>
#include <string>
#include <set>
#include <algorithm>
#include <list>
#include <unordered_set>
#include <unordered_map>

using namespace std;
typedef long long ll;
const int MAXPRIME = 1000000007;

class Node {
public:
  static unordered_set<int> mark;
  int rangeleft, rangeright, mid;
  int id;
  Node *left, *right;
  Node(int l, int r) : id(-1), mid(-1), left(NULL), right(NULL) {
    rangeleft = l, rangeright = r;
  }
  void add(int i, int l, int r) {
    if (l <= rangeleft && r >= rangeright) {
      id = i;
      return;
    }
    if (mid == -1) {
      mid = (rangeleft + rangeright) >> 1;
      left = new Node(rangeleft, mid);
      right = new Node(mid, rangeright);
    }
    if (id >= 0) {
      left->id = right->id = id;
    }
    if (r <= mid) {
      left->add(i, l, r);
    }
    else if (l >= mid) {
      right->add(i, l, r);
    }
    else {
      left->add(i, l, mid);
      right->add(i, mid, r);
    }
    id = -1;
  }
  void count() {
    if (id >= 0) {
      mark.insert(id);
      return;
    }
    if (left) left->count();
    if (right) right->count();
  }
};
unordered_set<int> Node::mark;

void pro() {
  Node::mark.clear();
  int n, m;
  cin >> n >> m;
  Node *root = new Node(0, m);
  while (n--) {
    int a, b;
    cin >> a >> b;
    root->add(n, a, b);
  }
  root->count();
  cout << Node::mark.size() << endl;
}

void handle() {
  pro();
}

int main() {

  handle();

  system("PAUSE");

  return 0;
}