题解：P3364 Cool loves touli

· · 题解

P3364题解

题目大意

这个题的题面讲的十分清楚，只是你需要注意是什么大于什么，不然这种错误很不容易调试出来。

解题思路

这个题很模板，总结一下规律，解题流程是：

  1. 写出偏序关系（状态转移方程）。
  2. 打出暴力（熟练的话可以忽略）。
  3. 套用 cdq 分治模板。

对于这个题，我们分别记题目中的等级、力量、智力、攻击力为 a,b,c,d。

那么等级从低到高排序保证了 a 关键字重复不影响答案。 剩下的关系照着题目可以写出来，它们是 i< j，d_i\le b_j，c_i\le d_j。

然后就可以套用 cdq 分治优化 dp 模板了。

AC代码

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#define lowbit(x) (x & -(x))

using namespace std;

constexpr int N = 1e5 + 2;
constexpr int M = N * 3; // 离散化后三倍空间
int n, b[N << 2], ln, c[M], ans = 1;

struct node{
  int a, b, c, d, dp, id; // id 方便排序回初始状态
} a[N];

inline void add(const int x, const int val) { for (int i = x; i < M; i += lowbit(i)) c[i] = max(c[i], val); return; } // 树状数组
inline int ask(const int x) { int res = 0; for (int i = x; i; i &= i - 1) res = max(res, c[i]); return res; }
inline void clear(const int x) { for (int i = x; i < M; i += lowbit(i)) c[i] = 0; return; } // 清空树状数组
inline void fun(int &x) { x = lower_bound(b + 1, b + ln + 1, x) - b; return; } // 离散化

/*
i < j
ai <= aj
di <= bj
ci <= dj
偏序关系
*/

void cdq(int l, int r)
{
  if (l == r)
  {
    a[l].dp = max(a[l].dp, 1); // 这里取 max 而非直接赋值
    return;
  }

  const int mid = (l + r) >> 1;
  cdq(l, mid); 

  sort(a + l, a + mid + 1, [&](const node &A, const node &B) {
    return A.d < B.d;
  }); // 按照第二重偏序关系排序

  sort(a + mid + 1, a + r + 1, [&](const node &A, const node &B) {
    return A.b < B.b;
  }); // 按照第二重偏序关系排序

  int i = l, j = mid + 1;

  while (j <= r) // 双指针
  {
    while (i <= mid && a[i].d <= a[j].b)
    {
      add(a[i].c, a[i].dp); // 按照第三重偏序关系加入树状数组
      i++;
    }
    a[j].dp = max(a[j].dp, ask(a[j].d) + 1);
    // 按照第三重偏序关系更新答案
    ans = max(ans, a[j].dp); j++;
  }

  for (int p = l; p != i; p++) clear(a[p].c); // 清空树状数组

  sort(a + mid + 1, a + r + 1, [&](const node &A, const node &B) {
    return A.id < B.id;
  }); // 排序回原始状态

  cdq(mid + 1, r);

  return;
}
int main()
{
  ios::sync_with_stdio(false);
  cin.tie(nullptr); cout.tie(nullptr);

  cin >> n;

  for (int i = 1; i <= n; i++)
  {
    cin >> a[i].a >> a[i].b >> a[i].c >> a[i].d; 
    // b[++ln] = a[i].a; 
    b[++ln] = a[i].b; b[++ln] = a[i].c; b[++ln] = a[i].d; // 离散化
  }

  sort(b + 1, b + ln + 1); ln = unique(b + 1, b + ln + 1) - b - 1;

  for (int i = 1; i <= n; i++)
  {
    // fun(a[i].a); 
    fun(a[i].b); fun(a[i].c); fun(a[i].d);
  }

  sort(a + 1, a + n + 1, [&](const node &A, const node &B) {
    return A.a < B.a; // a 关键字直接排序可不需要离散化
  });

  for (int i = 1; i <= n; i++) a[i].id = i; // id 方便排序回去

  cdq(1, n);

  // for (int i = 1; i <= n; i++) cout << a[i].dp << ' ';

  cout << ans; // 对 dp 取 max 并输出答案

  return 0;
}

/*
begin: 2024年6月5日17:28:02
debug: 2024年6月5日18:23:49
finish: 2024年6月5日19:00:08
*/