二维偏序问题应用(二维数点)

简介: 二维偏序问题应用(二维数点)


将二维数点问题转移为二维偏序问题来做,CDQ分治主席树也可以做,但是本人太菜,只会树状数组做法:

无需离散化写法:(注意询问数组开四倍,树状数组0没有意义+1)

#include <bits/stdc++.h>
using namespace std;
#define x first
#define y second
# define rep(i,be,en) for(int i=be;i<=en;i++)
# define pre(i,be,en) for(int i=be;i>=en;i--)
#define ll long long
#define endl "\n"
#define LOCAL
#define pb push_back
typedef pair<ll, ll> PII;
#define eb emplace_back
#define sp(i) setprecision(i)
const int N = 5e5 + 10, INF = 0x3f3f3f3f;
int n;
PII a[N];
int tr[10000005];
int m;
ll ans[N];
struct ques
{
  int x, y, id, type;
  ques(int _x = 0, int _y = 0, int _id = 0, int _type = 0)
  {
    x = _x;
    y = _y;
    id = _id;
    type = _type;
  }
  bool operator<(const ques &t)const
  {
    if (x == t.x)
      {
        return y < t.y;
      }
    else
      {
        return x < t.x;
      }
  }
} q[N << 2];
int cnt;
inline int lowbit(int x)
{
  return x & -x;
}
void modify(int x, int t)
{
  for (int i = x; i < 10000005; i += lowbit(i))
    {
      tr[i] += t;
    }
}
int  query(int x)
{
  ll sum = 0;
  for (int i = x; i; i -= lowbit(i))
    {
      sum += tr[i];
    }
  return sum;
}
void solve()
{
  cnt = 0;
  n = read();
  m = read();
  for (int i = 1; i <= n; i++)
    {
      a[i].x = read() + 1;
      a[i].y = read() + 1;
    }
  for (int i = 1; i <= m; i++)
    {
      int x1, x2, y1, y2;
      x1 = read() + 1;
      y1 = read() + 1;
      x2 = read() + 1;
      y2 = read() + 1;
      q[++cnt] = ques(x2, y2, i, 1);
      q[++cnt] = ques(x2, y1 - 1, i, -1);
      q[++cnt] = ques(x1 - 1, y2, i, -1);
      q[++cnt] = ques(x1 - 1, y1 - 1, i, 1);
    }
  sort(a + 1, a + 1 + n);
  sort(q + 1, q + 1 + cnt);
  int now = 1;
  for (int i = 1; i <= cnt; i++)
    {
      while (a[now].x <= q[i].x && now <= n)
        {
          modify(a[now].y, 1);
          now++;
        }
      ans[q[i].id] += 1LL * q[i].type * query(q[i].y);
    }
  for (int i = 1; i <= m; i++)
    {
      write(ans[i]);
      puts("");
    }
}
signed main()
{
  //#ifdef LOCAL
  //freopen("data.in.txt","r",stdin);
  //freopen("data.out.txt","w",stdout);
  //#endif
  int __ = 1;
  //cin >> __;
  while (__--)
    {
      solve();
    }
  return 0;
}

需要离散化写法

代码源oj 数数

这时要将两个数组放到一起

不需要加一,离散化会配好的:

/*********************************************************************
    程序名:
    版权:
    作者: Joecai
    日期: 2022-05-12 14:44
    说明:
*********************************************************************/
#include <bits/stdc++.h>
using namespace std;
#define x first
#define y second
# define rep(i,be,en) for(int i=be;i<=en;i++)
# define pre(i,be,en) for(int i=be;i>=en;i--)
#define ll long long
#define endl "\n"
#define LOCAL
#define pb push_back
#define int long long
typedef pair<ll, ll> PII;
#define eb emplace_back
#define sp(i) setprecision(i)
const int N = 1e6 + 10, INF = 0x3f3f3f3f;
int n, m;
int tr[N];
int t[N];
int ans[N];
inline int read()
{
  int X = 0;
  bool flag = 1;
  char ch = getchar();
  while (ch < '0' || ch > '9')
    {
      if (ch == '-')
        flag = 0;
      ch = getchar();
    }
  while (ch >= '0' && ch <= '9')
    {
      X = (X << 1) + (X << 3) + ch - '0';
      ch = getchar();
    }
  if (flag)
    return X;
  return ~(X - 1);
}
inline void write(int X)
{
  if (X < 0)
    {
      X = ~(X - 1);
      putchar('-');
    }
  if (X > 9)
    write(X / 10);
  putchar(X % 10 + '0');
}
struct node
{
  int x;
  int y;
  int id;
  int type;
  node(int _x = 0, int _y = 0, int _id = 0, int _type = 0)
  {
    x = _x;
    y = _y;
    id = _id;
    type = _type;
  }
  bool operator<(const node &w)const
  {
    if (x == w.x)
      {
        if (y == w.y)
          {
            return id < w.id;
          }
        else
          return y < w.y;
      }
    else
      return x < w.x;
  }
} q[N];
inline int lowbit(int x)
{
  return x & (-x);
}
void up(int x, int s)
{
  for (int i = x; i < N; i += lowbit(i))
    {
      tr[i] += s;
    }
}
int query(int x)
{
  int sum = 0;
  for (int i = x; i; i -= lowbit(i))
    {
      sum += tr[i];
    }
  return sum;
}
void solve()
{
  int cnt = 0;
  memset(tr, 0, sizeof(tr));
  memset(ans, 0, sizeof(ans));
  cin >> n >> m;
  for (int i = 1; i <= n; i++)
    {
      int x;
      x = read();
      q[++cnt].x = i;
      q[cnt].y = x;
      q[cnt].type = 0;
      q[cnt].id = 0;
    }
  for (int i = 1; i <= m; i++)
    {
      int x, y, z;
      x = read();
      y = read();
      z = read();
      q[++cnt] = node(y, z, i, 1);
      q[++cnt] = node(x - 1, -1, i, 1);
      q[++cnt] = node(x - 1, z, i, -1);
      q[++cnt] = node(y, -1, i, -1);
    }
  for (int i = 1; i <= cnt; i++)
    t[i] = q[i].y;
  sort(q + 1, q + 1 + cnt);
  sort(t + 1, t + 1 + cnt);
  int te = unique(t + 1, t + 1 + cnt) - t - 1;
  for (int i = 1; i <= cnt; i++)
    {
      q[i].y = lower_bound(t + 1, t + 1 + te, q[i].y) - t;
    }
  for (int i = 1; i <= cnt; i++)
    {
      if (q[i].id) //查询的点
        {
          ans[q[i].id] += q[i].type * query(q[i].y);
        }
      else
        {
          up(q[i].y, 1);
        }
    }
  for (int i = 1; i <= m; i++)
    {
      write(ans[i]);
      printf(" ");
    }
  cout << endl;
}
signed main()
{
  //#ifdef LOCAL
  //freopen("data.in.txt","r",stdin);
  //freopen("data.out.txt","w",stdout);
  //#endif
  int __ = 1;
  cin >> __;
  while (__--)
    {
      solve();
    }
  return 0;
}

1

/*********************************************************************
    程序名:
    版权:
    作者: Joecai
    日期: 2022-05-12 16:20
    说明:
*********************************************************************/
#include <bits/stdc++.h>
using namespace std;
#define x first
#define y second
# define rep(i,be,en) for(int i=be;i<=en;i++)
# define pre(i,be,en) for(int i=be;i>=en;i--)
#define ll long long
#define endl "\n"
#define LOCAL
#define pb push_back
typedef pair<ll, ll> PII;
#define eb emplace_back
#define sp(i) setprecision(i)
const int N = 1e6 + 10, INF = 0x3f3f3f3f;
int n;
int tr[N];
inline int lowbit(int x)
{
  return x & (-x);
}
void up(int x, int s)
{
  for (int i = x; i < N; i += lowbit(i))
    {
      tr[i] += s;
    }
}
int query(int x)
{
  int sum = 0;
  for (int i = x; i; i -= lowbit(i))
    {
      sum += tr[i];
    }
  return sum;
}
struct node
{
  int x;
  int y;
  int id;
  int type;
  node(int _x = 0, int _y = 0, int _id = 0, int _type = 0)
  {
    x = _x;
    y = _y;
    id = _id;
    type = _type;
  }
  bool operator<(const node &w)const
  {
    if (x == w.x)
      {
        return y < w.y;
      }
    else
      return x < w.x;
  }
} q[N];
int t[N];
int ans[N];
void solve()
{
  int n;
  cin >> n;
  int cnt = 0;
  for (int i = 1; i <= n; i++)
    {
      int x, y;
      cin >> x >> y;
      q[++cnt].x = x;
      q[cnt].y = y;
      q[++cnt] = node(y, y, i, 1);
      q[++cnt] = node(x - 1, x - 1, i, 1);
      q[++cnt] = node(x - 1, y, i, -1);
      q[++cnt] = node(y, x - 1, i, -1);
    }
  sort(q + 1, q + 1 + cnt);
  for (int i = 1; i <= cnt; i++)
    t[i] = q[i].y;
  sort(t + 1, t + 1 + cnt);
  int te = unique(t + 1, t + 1 + cnt) - t - 1;
  for (int i = 1; i <= cnt; i++)
    {
      q[i].y = lower_bound(t + 1, t + 1 + te, q[i].y) - t;
    }
  for (int i = 1; i <= cnt; i++)
    {
      if (q[i].id)
        {
          ans[q[i].id] += q[i].type * query(q[i].y);
        }
      else
        up(q[i].y, 1);
    }
  for (int i = 1; i <= n; i++)
    {
      cout << ans[i] - 1 << endl;
    }
}
signed main()
{
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
  //#ifdef LOCAL
  //freopen("data.in.txt","r",stdin);
  //freopen("data.out.txt","w",stdout);
  //#endif
  int __ = 1;
  //cin>>__;
  while (__--)
    {
      solve();
    }
  return 0;
}


目录
相关文章
|
6月前
|
存储 人工智能 算法
二维差分与二维前缀和
二维差分与二维前缀和
60 3
|
6月前
|
机器学习/深度学习 存储 人工智能
利用前缀和计算二维矩阵子矩阵的和
利用前缀和计算二维矩阵子矩阵的和
64 0
|
6月前
|
存储 人工智能 算法
【C/C++ 数据结构 】三角矩阵的基本了解
【C/C++ 数据结构 】三角矩阵的基本了解
85 0
二维平面的欧几里得距离
二维平面的欧几里得距离
|
Python
点云在任意平面上获取二维投影
点云在任意平面上获取二维投影
1137 0
点云在任意平面上获取二维投影
|
前端开发 图形学
二维空间下的向量旋转
向量运算是计算机图形学的数学基础,而向量的旋转是向量的一种常见操作,本文将详细讲解向量在二维空间下的旋转原理。
810 0
二维空间下的向量旋转
|
人工智能 vr&ar
一维 二维求前缀和、差分
一维 二维求前缀和、差分
53 0
|
C++ 计算机视觉 异构计算