Introduction

This article records my experience solving Luogu P1637 Increasing Triples and SPOJ INCSEQ Increasing Subsequences, along with a template I happened to discover along the way that solves the general problem of counting strictly increasing subsequences of length k.

The route is roughly as follows:

1. Start with P1637 and use two Fenwick trees to express the counting of increasing triples as a very natural process.
2. Abstract that implementation into mathematical form and recognize that it is already a DP framework with “layers by length + prefix sums over the value domain.”
3. Extend the framework to arbitrary k in SPOJ INCSEQ and turn it into a template ready to drop into a code library.

Part 1: P1637 Increasing Triples (k = 3)

1. Problem Statement

Luogu P1637 Increasing Triples

The key information:

• We need to count triples

  $$(i, j, k)\quad \text{s.t. } i < j < k,\ a_i < a_j < a_k$$
• $1 \le n \le 3\times 10^4$, and the value domain is large, so coordinate compression is needed.

• The naive $O(n^3)$ approach clearly will not work.

• Even an $O(n^2)$ approach that “enumerates the middle index j, then scans left and right” is too slow.

We therefore need something on the order of $O(n\log n)$.

2. The Idea: Divide by “Length,” Rather Than “Left and Right”

Many explanations of increasing triples emphasize:

• The number of elements to the left that are smaller than $a_j$, denoted $L[j]$.
• The number of elements to the right that are greater than $a_j$, denoted $R[j]$.
• Answer = $\sum_j L[j]\cdot R[j]$.

I did not know this standard approach beforehand, so I did not write it that way. Instead, I maintained separate layers by subsequence length:

• Increasing subsequences of length 1: $(i)$.
• Increasing subsequences of length 2: $(i, j)$, satisfying $i < j,\ a_i < a_j$.
• Increasing subsequences of length 3: $(i, j, k)$, satisfying $i < j < k,\ a_i < a_j < a_k$.

Scan indices pos from left to right. When the current value is a[pos] = p, perform three steps:

1. Treat the current value as the third element $k$.
   • Count all “previously formed increasing subsequences of length 2 whose ending value is < p.”
   • Each can be extended with $p$ to form an increasing subsequence of length 3.
2. Treat the current value as the second element $j$.
   • Count all “increasing subsequences of length 1 whose ending value is < p.”
   • Each combines with $p$ to form an increasing subsequence of length 2.
3. Treat the current value as the first element $i$.
   • On its own, it is an increasing subsequence of length 1.

The mathematics behind this can be expressed with two functions:

• $f_1(v)$: the number of strictly increasing subsequences of length 1 ending with value $v$.
• $f_2(v)$: the number of strictly increasing subsequences of length 2 ending with value $v$.

For the current value $p$, with compressed index $idx$, we have:

The Chinese label in the first line means “the number of new subsequences of length 3.” The overall answer is the sum of all these new counts.

The question becomes how to efficiently compute $\sum_{u < p} f_\ell(u)$ over the value domain. This is a typical prefix-sum and point-update problem, so a Fenwick tree fits directly.

3. Coordinate Compression and Two Fenwick Trees

3.1 Compressing the Value Domain

Since the $a_i$ values can be large, using them directly as BIT indices is not a sound choice. First compress the coordinates:

1. Put every a[i] into disperse.
2. Sort and deduplicate.
3. Find each a[i] in disperse and call its 1-based index idx.

All subsequent Fenwick-tree indexing uses idx.

3.2 What the Two Fenwick Trees Represent

My code creates two trees:

• cnt_op
  • Maintains $f_1(v)$, the counts of increasing subsequences of length 1.
  • In effect, it counts occurrences of value $v$ before the current position.
• double_pair
  • Maintains $f_2(v)$, the counts of increasing subsequences of length 2.
  • Records how many increasing subsequences of length 2 end with value $v$.

Thus:

• $\sum_{u < p} f_1(u)$ is expressed as query(idx - 1, cnt_op).
• $\sum_{u < p} f_2(u)$ is expressed as query(idx - 1, double_pair).

4. The Scan and Why Forward Updates Are Correct

For each p, with compressed index idx, execute the following in order:

1. Use the current element as the third element $k$

1

ans += query(idx - 1, double_pair);

2. Use the current element as the second element $j$

1

update(idx, query(idx - 1, cnt_op), double_pair, (ll)disperse.size());

3. Use the current element as the first element $i$

1

update(idx, 1, cnt_op, (ll)disperse.size());

We scan from left to right and update the “length 2” layer before the “length 1” layer. At first glance, this may raise a concern: could the current element read results that it has just written?
But notice:

• Every query uses idx - 1.
• The Fenwick implementation ensures that query(idx - 1) only accesses positions with index < idx.
• Meanwhile, update(idx, ...) writes to nodes with index ≥ idx.

Therefore, whether we have two dimensions—the f1/f2 in P1637—or extend to k dimensions later, forward updates will never read the entry just written by the current element. There is no contamination.

5. Final Accepted Code for P1637

I have kept the code exactly in my own style: vector + 离散化 + 两棵 Fenwick—a vector, coordinate compression, and two Fenwick trees.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const ll maxn = 3e4 + 5;

ll n, ans;
vector<ll> a, disperse;

ll lowbit(ll x) {
    return x & -x;
}

void update(ll x, ll add, vector<ll> &tree, ll limit) {
    for (ll i = x; i <= limit; i += lowbit(i)) {
        tree[i] += add;
    }
}

ll query(ll x, vector<ll> &tree) {
    ll sum = 0;
    for (ll i = x; i; i -= lowbit(i)) {
        sum += tree[i];
    }
    return sum;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    a.reserve(maxn);
    disperse.reserve(maxn);
    cin >> n;
    for (ll i = 1; i <= n; ++i) {
        ll num;
        cin >> num;
        a.push_back(num);
        disperse.push_back(num);
    }
    sort(disperse.begin(), disperse.end());
    disperse.erase(unique(disperse.begin(), disperse.end()), disperse.end());
    vector<ll> double_pair(disperse.size() + 5, 0);
    vector<ll> cnt_op(disperse.size() + 5, 0);
    for (ll p: a) {
        ll idx = lower_bound(disperse.begin(), disperse.end(), p) - disperse.begin() + 1;
        ans += query(idx - 1, double_pair);
        update(idx, query(idx - 1, cnt_op), double_pair, (ll) disperse.size());
        update(idx, 1, cnt_op, (ll) disperse.size());
    }
    cout << ans;
    return 0;
}

(Some scratch notes from solving the problem.)

Figure legend: “tree (coordinate compression)” labels the compressed value domain. The second tree counts increasing pairs. The notes on the right show the order: count new answers using the pair tree, then update the pair counts using the single-element tree. The examples also work through duplicate values.

That solves P1637, the k=3 case. Next comes the main point of this article: extending this implementation to arbitrary k and making it a template.

Part 2: From P1637 to a General k-Layer Template—Applying It to INCSEQ

This part does three main things:

1. Fully abstract the P1637 implementation into mathematical form.
2. Extend it to arbitrary length $k$.
3. Validate the template on SPOJ INCSEQ, a representative problem, and provide the final code.

1. Abstracting the DP Structure in P1637

First, let us extract the structure from the P1637 implementation.

Over the compressed value domain $[1, m]$, for each length $\ell \ge 1$, define:

In English, $f_\ell(v)$ is the number of strictly increasing subsequences of length $\ell$ whose ending value has compressed index $v$.

In P1637:

• $f_1(v)$ is stored in cnt_op.
• $f_2(v)$ is stored in double_pair.
• Each scan step produces some new subsequences of length 3 and adds their count to ans, without explicitly storing $f_3(v)$.

For the current element value $p$, at index idx, the transitions can be written together as:

If we also choose to store $f_3$ explicitly, then:

This naturally gives a unified formula for any $\ell \ge 2$:

This is the core structure: “DP layers by length, with Fenwick prefix sums over the value domain.”

2. Extending to Arbitrary k: The General Recurrence

For the general problem of “counting strictly increasing subsequences of length k,” after processing every element, we want:

The transition rules become:

Each layer has a corresponding Fenwick tree:

• The Fenwick tree for layer $\ell$ maintains prefix sums of $f_\ell(v)$ over the value domain, so

  $$\sum_{u < v} f_{\ell-1}(u) = \text{Fenwick}\_{\ell-1}.query(\text{idx}-1)$$

To express this DP in array notation, let:

The same transitions can then be written as:

Use a Fenwick tree to reduce the “prefix sum” on the right to $O(\log m)$.

3. Why Are Forward Updates Safe Here Too?

Notice the loop order above, corresponding to my INCSEQ code:

1
2
3
4
5
6
7

for (ll p: a) {
    int idx = ...;
    for (int i = 2; i <= k; ++i) {
        update(idx, query(idx - 1, dp_tree[i - 1]), dp_tree[i], size);
    }
    update(idx, 1, dp_tree[1], size);
}

Unlike many DP problems, this one does not require iterating backward from k → 1. There are two reasons:

1. For a fixed len, we read from the previous layer, dp_tree[len - 1].
   That layer has not yet been updated in the loop for the current element p.
2. Even where there is a dependency along the length dimension, such as len=3 depending on len=2,
   we only query query(idx - 1, dp_tree[len - 1]),
   while the current element’s new contributions are written only to idx and subsequent nodes.
   These new contributions therefore cannot be read.

The structure of a Fenwick tree guarantees:

• update(idx, ...) writes only to nodes with index ≥ idx.
• query(idx - 1) reads only nodes with index ≤ idx - 1.

Therefore, updating forward through len=2..k is completely safe. Each layer always uses “the previous layer’s state before the current element.”

4. Putting the Template into Practice: SPOJ INCSEQ

SPOJ INCSEQ - Increasing Subsequences

Problem outline: Given $n$, $k$, and a sequence of length $n$, count the strictly increasing subsequences of length exactly k, modulo MOD = 5,000,000.
The constraints are approximately:

• $1 \le n \le 10^4$
• $1 \le k \le 50$
• $0 \le a_i < 100000$

This matches the model we have abstracted perfectly, making it an excellent template problem.

5. Implementation Details

There are several key points in my accepted code:

5.1 Coordinate Compression

Again, sort and deduplicate coord to map the original values to $[1, size]$:

1
2
3
4

sort(coord.begin(), coord.end());
coord.erase(unique(coord.begin(), coord.end()), coord.end());
int size = (int) coord.size();
int idx = (int) (lower_bound(coord.begin(), coord.end(), p) - coord.begin()) + 1;

This makes the Fenwick-tree size depend only on size, rather than the original value domain.

5.2 Organizing k Fenwick Layers

Use a two-dimensional array:

1

vector<vector<ll> > dp_tree(k + 5, vector<ll>(size + 5, 0));

Here:

• dp_tree[len] is “the internal array of the Fenwick tree for subsequence length len.”
• dp_tree[len][pos] is an internal Fenwick-tree node representing $f_\ell(v)$.

Together with update and query, this forms a structure of k Fenwick layers.

5.3 Modular Arithmetic

All additions in the code use:

1
2

tree[i] = (tree[i] + val) % MOD;
sum = (sum + tree[i]) % MOD;

This keeps values within $[0, \text{MOD})$ and prevents overflow.
The problem also requires the answer modulo 5,000,000, which is handled directly during every Fenwick update.

5.4 Complexity

For every element p:

• Perform a query + update for each len = 2..k, with each taking $O(\log size)$.
• Perform one more update for len = 1.

The overall time complexity is:

With $n = 10^4, k \le 50$, this is comfortably fast enough.

6. Final Accepted Code for INCSEQ

This is the version accepted on SPOJ, using exactly the template idea developed above.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const ll maxn = 1e4 + 5, MOD = 5000000;

ll n, k;
vector<ll> a, coord;

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

void update(int idx, ll val, vector<ll> &tree, int limit) {
    for (int i = idx; i <= limit; i += lowbit(i)) {
        tree[i] = (tree[i] + val) % MOD;
    }
}

ll query(int idx, const vector<ll> &tree) {
    ll sum = 0;
    for (int i = idx; i; i -= lowbit(i)) {
        sum = (sum + tree[i]) % MOD;
    }
    return sum;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    a.reserve(maxn);
    coord.reserve(maxn);
    cin >> n >> k;
    for (int i = 1; i <= n; ++i) {
        ll num;
        cin >> num;
        a.push_back(num);
        coord.push_back(num);
    }
    sort(coord.begin(), coord.end());
    coord.erase(unique(coord.begin(), coord.end()), coord.end());
    int size = (int) coord.size();
    vector<vector<ll> > dp_tree(k + 5, vector<ll>(size + 5, 0));
    for (ll p: a) {
        int idx = (int) (lower_bound(coord.begin(), coord.end(), p) - coord.begin()) + 1;
        for (int i = 2; i <= k; ++i) {
            update(idx, query(idx - 1, dp_tree[i - 1]), dp_tree[i], size);
        }
        update(idx, 1, dp_tree[1], size);
    }
    cout << query(size, dp_tree[k]);
    return 0;
}

(Some more scratch notes from solving the problem.)

Figure legend: In tree[len][r], the Chinese labels identify len as the subsequence length and r as the position of the subsequence’s largest element in coord. Rows are length layers and columns are compressed ending values. The left example has n=7, k=4 and answer 4; the right example includes repeated values.

Takeaways: A Result Ready for the Code Library

The main result I want to retain from this article is this set of transitions:

In array notation, let:

Then the equivalent DP formulation is:

Use a Fenwick tree to reduce the “prefix sum” on the right to $O(\log m)$, and we obtain a general template that:

• Runs in $O(n\cdot k \cdot \log n)$ time.
• Counts strictly increasing subsequences for any $k$.
• Is easy to apply to different problems.

P1637 is a “special-case implementation” of this template for $k=3$.
INCSEQ is a standard template problem that develops the structure in full.

The next time a problem involves “strictly increasing subsequences of length k,” I can modify and extend this code directly rather than derive the approach from scratch.