题解 P3810 【【模板】三维偏序（陌上花开）】

_rqy · 2018-05-21 20:35:50 · 题解

这题咋做啊？

emm楼下有树状数组套treap。

诶呀我只会树状数组怎么办啊？

显然我们可以排序去掉一维。

二维树状数组开不下怎么办啊？

开map又多一个log啊？

手写哈希表大法好（别告诉我unordered_map，反正考场上你用不了）！

手写一个哈希表，然后二位树状数组美滋滋啊~

不过要注意一个地方：有完全相同的点的时候后面的可能会对前面的造成影响。

#include <algorithm>
#include <cctype>
#include <cstdio>
#include <cstring>

typedef long long LL;

inline int readInt() {
  int ans = 0, c, f = 1;
  while (!isdigit(c = getchar()))
    if (c == '-') f *= -1;
  do ans = ans * 10 + c - '0';
  while (isdigit(c = getchar()));
  return ans * f;
}

const int N = 100050;
const int M = 39999983;

struct{
  LL key[M];
  int val[M];

  int operator()(int i, int j, int) {
    LL x = (LL)i * N + j;
    int t = x % M;
    while (key[t] != 0 && key[t] != x)
      if (++t == M) t = 0;
    return val[t];
  }

  int& operator()(int i, int j) {
    LL x = (LL)i * N + j;
    int t = x % M;
    while (key[t] != 0 && key[t] != x)
      if (++t == M) t = 0;
    key[t] = x;
    return val[t];
  }
} H;

struct Point{
  int a, b, c;

  bool operator<(const Point &t) const {
    if (a != t.a) return a < t.a;
    if (b != t.b) return b < t.b;
    return c < t.c;
  }

  bool operator==(const Point &t) const {
    return a == t.a && b == t.b && c == t.c;
  }
} P[N];

int n, na, nb, nc, A[N], B[N], C[N];
int ans[N];

void Add(int x, int y) {
  for (int i = x; i <= nb; i += i & -i)
    for (int j = y; j <= nc; j += j & -j)
      ++H(i, j);
}

int Query(int x, int y) {
  int ans = 0;
  for (int i = x; i > 0; i -= i & -i)
    for (int j = y; j > 0; j -= j & -j)
      ans += H(i, j, 0);
  return ans;
}

int main() {
  n = readInt();
  readInt();
  for (int i = 0; i < n; ++i) {
    A[i] = P[i].a = readInt();
    B[i] = P[i].b = readInt();
    C[i] = P[i].c = readInt();
  }
  std::sort(A, A + n);
  std::sort(B, B + n);
  std::sort(C, C + n);
  na = std::unique(A, A + n) - A;
  nb = std::unique(B, B + n) - B;
  nc = std::unique(C, C + n) - C;
  for (int i = 0; i < n; ++i) {
    P[i].a = std::lower_bound(A, A + na, P[i].a) - A + 1;
    P[i].b = std::lower_bound(B, B + nb, P[i].b) - B + 1;
    P[i].c = std::lower_bound(C, C + nc, P[i].c) - C + 1;
  }
  std::sort(P, P + n);
  for (int i = 0, j = 0, l = 0; i < n; ++i) {
    while (j < i || (j < n && P[j] == P[i])) ++j;
    if (i > 0 && P[i - 1] < P[i])
      l = Query(P[i].b, P[i].c) + j - i - 1;
    ++ans[l];
    Add(P[i].b, P[i].c);
  }

  for (int i = 0; i < n; ++i)
    printf("%d\n", ans[i]);
  return 0;
}