K元上升子序列 | 冷门杂谈

_Kasty_ · 2026-08-21 19:11:57 · 算法·理论

介绍 | Introduce

本文主要介绍 k 元上升子序列，作为小杂谈冷门知识。

二元子序列 | 顺序对 & 逆序对

题目传送门

关于逆序对的定义为，在一个长度为 n 的序列中，\exists\,1 \le i < j \le n,\, a_j < a_i。

那么最简单的暴力想法就是双重枚举，从 n 到 1，在 [i, n] 中枚举是否有元素 a_j < a_i。

显然通过不了此题，所以我们考虑用数据结构优化时间复杂度。

从后往前枚举的过程是不能省略的，所以我们要一种数据结构要支持在 O(\log n) 的时间复杂度下在 [i, n] 中找到所有小于 a_i 的个数。这其实相当于一种前缀和，来维护当前区间下有多少个数（除了当前元素 a_i），其他元素的值域都在 [1, a_i - 1]，每次枚举到一个 a_i 就将 a_{i + 1} 放进这个数据结构中。

而通过前缀和与单次修改，我们可以知晓用树状数组，那么树状数组 c_x 的定义就是：在当前扫过的 [i, n] 中，有多少个元素的值域是 [1, a_i - 1]。

至此，我们就可以用树状数组高效计算逆序对了。 ::::info[Code]

#include<bits/stdc++.h>
using namespace std;

using ll = long long;
constexpr int N = 5e5 + 7;

struct BIT {
  int n; int c[N];
  BIT(int _n = 0) {init(_n);}
  void init(int _n) {n = _n; memset(c, 0, sizeof(c));}
  void add(int k, int x){
    for(int i = k; i <= n; i += (i & -i)) c[i] += x;
  }
  int sum(int x) const {
    int res = 0;
    while(x) res += c[x], x -= (x & -x);
    return res;
  }
  int range_sum(int l, int r) const {
    return sum(r) - sum(l - 1);
  }
};

int n;
BIT b;
int a[N];
vector<int> d;
ll ans;

int get(int x){
  return lower_bound(d.begin(), d.end(), x) - d.begin() + 1;
}

void disc(){
  sort(d.begin(), d.end());
  d.erase(unique(d.begin(), d.end()), d.end());
}

signed main(){
  ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);

  cin >> n;
  for(int i = 1; i <= n; i++){
    cin >> a[i];
    d.push_back(a[i]);
  }

  disc(); b.init(n);

  for(int i = n; i; i--){
    int id = get(a[i]);
    ans += b.sum(id - 1);
    b.add(id, 1);
  }

  cout << ans << "\n";

  return 0;
}

:::: 而顺序对是将枚举方向改为从前往后，去计算 [1, i] 中有多少个值域为 [1, a_i - 1] 的元素个数。

三元上升子序列 | Triple

[题目传送门]()

同样的定义，在一个长度为 n 的序列中，\exists\,1 \le i < j < p \le n,\, a_i < a_j < a_p。

我们还是不变化主体思路，顺序对就从前往后枚举。

我们把它拆为 a_i < a_j 和 a_j < a_p 的格式，对于 i < j 且 a_i < a_j 其实就是求顺序对，而 j < p 且 a_j < a_p 也是顺序对。

那么，假设左边比自己小的元素个数 lcnt 和右边比自己大的元素个数 rcnt，根据乘法原理，当前可以组成的三元上升子序列的个数为 lcnt × rcnt。

所以最后，用树状数组刷两遍就可以计算出三元上升子序列了。
::::info[Code]

#include<bits/stdc++.h>
using namespace std;

using ll = long long;
constexpr int N = 5e5 + 7;

struct BIT {
  int n; int c[N];
  BIT(int _n = 0) {init(_n);}
  void init(int _n) {n = _n; memset(c, 0, sizeof(c));}
  void add(int k, int x){
    for(int i = k; i <= n; i += (i & -i)) c[i] += x;
  }
  int sum(int x) const {
    int res = 0;
    while(x) res += c[x], x -= (x & -x);
    return res;
  }
  int range_sum(int l, int r) const {
    return sum(r) - sum(l - 1);
  }
};

int n;
BIT b;
int a[N];
vector<int> d;
ll l[N], r[N];
ll ans;

int get(int x){
  return lower_bound(d.begin(), d.end(), x) - d.begin() + 1;
}

void disc(){
  sort(d.begin(), d.end());
  d.erase(unique(d.begin(), d.end()), d.end());
}

signed main(){
  ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);

  cin >> n;
  for(int i = 1; i <= n; i++){
    cin >> a[i];
    d.push_back(a[i]);
  }

  disc(); 

  b.init(n);
  for(int i = 1; i <= n; i++){
    int id = get(a[i]);
    l[i] += b.sum(id - 1);
    b.add(id, 1);
  }

  b.init(n);
  for(int i = n; i; i--){
    int id = get(a[i]);
    r[i] += b.sum(n) - b.sum(id);
    b.add(id, 1);
  }

  for(int i = 1; i <= n; i++) ans += l[i] * r[i];

  cout << ans << "\n";

  return 0;
}

::::

K 元上升子序列 | Final

题目传送门

对于 k 元上升子序列，我们显然不能去用树状数组拆分每种情况，而是分为多个子问题。

我们还是来看一下三元上升子序列找找灵感，首先的是我们要找到一个三元组 (i, j, p)，而我们在计算三元上升子序列时固定了中间的 j，去左边寻找顺序对，右边也寻找顺序对，而我们对于这个固定元素只会在意两件事：

前面有多少个元素 i，满足 i < j 且 a_i < a_j；后面有多少个元素 p，满足 j < p 且 a_j < a_p。

每个以这样的 j 结尾的且长度为 2 的上升子序列有多少个。

而我们不妨发现，如果我们想知道长度为 len 的信息，那么需要得知 len - 1 的信息，这样的子问题很容易让我们想到用动态规划。

设 f_{i,len} 为以第 i 个元素结尾且长度为 len 的上升子序列个数。

假设能转移到 i，那么结尾为 i 且长度为 len 的上升子序列个数都可以从以某个更靠前的 j，长度为 len - 1 的序列，接上 a_i 得到，所以转移方程即为：

f_{i,len} = \sum_{j = 1 且 a_j < a_i}^{i - 1} f_{j, len - 1}

现在我们明确了转移方程，但如果暴力转移，因为要遍历所有的 j，这个算法的时间复杂度是 O(n^2 \times k)。

而我们要求的无非是一个顺序对，也就是二维偏序。所以我们把值作为下标，将所有 j < i 的元素信息放到可以解决这个问题的数据结构中，最后查询所有小于 a_i 的前缀和即可。

时间复杂度是 O(nk \log n)。
::::info[Code]

#include<bits/stdc++.h>
using namespace std;

using ll = long long;
constexpr int N = 1e5 + 7;
constexpr int K = 15;

struct BIT {
  int n; ll c[N];
  BIT(int _n = 0) {init(_n);}
  void init(int _n) {n = _n; memset(c, 0, sizeof(c));}
  void add(int k, ll x) {
    for(int i = k; i <= n; i += (i & -i)) c[i] += x;
  }
  ll sum(int x) const {
    ll res = 0;
    while(x) res += c[x], x -= (x & -x);
    return res;
  }
  ll range_sum(int l, int r) const {
    return sum(r) - sum(l - 1);
  }
};

vector<int> d;
int a[N];
BIT bit[K];  // bit[len] 表示长度为 len 的树状数组
int n, k;

int get(int x) {
  return lower_bound(d.begin(), d.end(), x) - d.begin() + 1;
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);

  cin >> n >> k;
  for(int i = 1; i <= n; i++) {
    cin >> a[i];
    d.push_back(a[i]);
  }

  sort(d.begin(), d.end());
  d.erase(unique(d.begin(), d.end()), d.end());

  // 初始化每个 BIT
  for(int i = 1; i <= k; i++) bit[i].init(n);

  ll ans = 0;

  for(int i = 1; i <= n; i++) {
    int id = get(a[i]);

    // 长度为 1：只有自己
    bit[1].add(id, 1);

    // 从大到小更新，防止重复使用同一个元素
    for(int len = k; len >= 2; len--) {
      ll cnt = bit[len - 1].sum(id - 1);
      if(cnt) {
        bit[len].add(id, cnt);
        if(len == k) ans += cnt;
      }
    }
  }

  if(k == 1) cout << n << "\n";
  else cout << ans << "\n";

  return 0;
}

::::