【校内训练2019-11-10】套路

【题目概括】

求给定\(n\)个元素的二元组序列\((x,y)\)，对于每一个\(i\)，我们需要统计有多少个\(j\)，满足\(x_i\leq x_j,y_j\leq y_i\)。

【思路要点】

【代码】

#include <bits/stdc++.h>

#define REP(i, s, t) for (int i = s; i <= t; i++)
#define PER(i, s, t) for (int i = s; i >= t; i--)
#define FI first
#define SE second

using namespace std;

template <class T> void chkmax(T& x, T y) { x = max(x, y); }
template <class T> void chkmin(T& x, T y) { x = min(x, y); }

template <class T>
void re(T& x) {
  x = 0; char ch = 0; int f = 1;
  for (; !isdigit(ch); ch = getchar()) if (ch == '-') f = -1;
  for (; isdigit(ch); ch = getchar()) x = x * 10 + ch - 48;
  x *= f;
}

const int N = 1e5 + 5;

int n, dc;
struct Node {
  int x, y, id;
  bool operator < (const Node& rhs) const {
    return x > rhs.x;
  }
} a[N];
int d[N], ans[N];

struct Fenwick {
  int lowbit(int x) {
    return x & -x;
  }

  int tr[N];
  int lim;

  void setLim(int L) {
    lim = L;
  }

  void modify(int p, int v) {
    for (; p <= dc; p += lowbit(p))
      tr[p] += v;
  }

  int query(int p) {
    int ans = 0;
    for (; p; p -= lowbit(p))
      ans += tr[p];
    return ans;
  }
} bit1;

int main() {
  re(n);
  for (int i = 1; i <= n; i++)
    re(a[i].x), re(a[i].y), a[i].id = i, d[++dc] = a[i].y;
  sort(a + 1, a + 1 + n);
  sort(d + 1, d + 1 + dc);
  dc = unique(d + 1, d + 1 + dc) - d - 1;
  bit1.setLim(dc);
  for (int i = 1; i <= n; i++) {
    a[i].y = lower_bound(d + 1, d + 1 + dc, a[i].y) - d;
    ans[a[i].id] = bit1.query(a[i].y);
    bit1.modify(a[i].y, 1);
  }
  for (int i = 1; i <= n; i++)
    printf("%d\n", ans[i]);
  return 0;
}