Problem Definition

Given $n$ strings $T_1, T_2, \dots, T_n$, each of length $len$. Define $f(a, b)$ as the minimum number of sorting operations required on substrings of $a$ to make it identical to $b$. If it is impossible to transform $a$ into $b$ via substring sorting, $f(a, b) = 1337$. The objective is to compute:

Analysis of Function Values

The value of $f(a, b)$ is restricted to three possibilities: $1$, $2$, or $1337$.

• 1337: Occurs if the character sets (frequency of each character) of $a$ and $b$ differ. No amount of sorting can change the character counts.
• 2: If character sets match, we can always sort the entire string $a$ and the entire string $b$ to make them equal (both become the sorted version of the character set). Thus, the maximum required operations is 2.
• 1: Occurs if there exists a substring in $a$ such that sorting only that substring makes $a$ equal to $b$.

The total number of pairs is $\frac{n(n-1)}{2}$. We can calculate the contribution of each case separately. Let $C_{1337}$, $C_1$, and $C_2$ be the counts of pairs resulting in 1337, 1, and 2 respectively. The answer is $1337 \times C_{1337} + 1 \times C_1 + 2 \times C_2$. Since $C_2 = \text{Total} - C_{1337} - C_1$, we only need to compute $C_{1337}$ and $C_1$.

Counting Pairs with Value 1337

Two strings have different character sets if their sorted character frequency distributions differ. We can group strings by their character counts. A Trie structure can be used where each level represents a character 'a' through 'z', and the depth corresponds to the count of that character. Alternatively, simply sorting each string and grouping identical sorted strings works, but a Trie allows efficient insertion and grouping.

For each group of size $S$, the number of pairs within the group is $\frac{S(S-1)}{2}$. The number of pairs with different character sets is the total pairs minus the sum of pairs within each group.

Counting Pairs with Value 1

For $f(a, b) = 1$, strings $a$ and $b$ must share the same character set. Additionally, there must exist a range $[l, r]$ in $a$ such that sorting $a[l \dots r]$ results in $b$. This implies:

1. $a[1 \dots l-1] = b[1 \dots l-1]$ (Prefix match)
2. $a[r+1 \dots len] = b[r+1 \dots len]$ (Suffix match)
3. The substring $a[l \dots r]$ is the only part that differs and becomes sorted.

To efficiently find such pairs, we identify all maximal non-decreasing substrings in each string. If a string $a$ has a maximal non-decreasing segment $[l, r]$, sorting this segment makes the whole string sorted. If another string $b$ matches $a$ outside this segment and has the same character set, then sorting $a[l \dots r]$ transforms $a$ into $b$ (assuming $b$ is the target configuration reachable by this sort).

Specifically, for every maximal non-decreasing substring $[l, r]$ in $T_i$, we look for strings $T_j$ ($j \neq i$) in the same character set group such that $T_i$ and $T_j$ share the prefix of length $l-1$ and the suffix starting at $r+1$.

Trie Construction for Range Queries

We construct two Tries:

• Forward Trie: Inserts strings from left to right.
• Reverse Trie: Inserts strings from right to left.

Each leaf node in the Forward Trie corresponds to a complete string. We assign a DFS order index to each leaf. All strings sharing a specific prefix will correspond to a contiguous range of leaf indices in the Forward Trie. Similarly, strings sharing a specific suffix correspond to a contiguous range in the Reverse Trie.

Thus, each string $T_i$ can be represented as a point $(x_i, y_i)$, where $x_i$ is the leaf index in the Forward Trie and $y_i$ is the leaf index in the Reverse Trie. A query for a specific prefix and suffix becomes a 2D range sum query: count points $(x, y)$ such that $x \in [L_1, R_1]$ and $y \in [L_2, R_2]$.

2D Range Sum via Sweep-Line

To solve the 2D range queries efficiently:

1. Collect all query rectangles derived from the maximal non-decreasing substrings.
2. Sort queries and points by the x-coordinate.
3. Iterate through sorted x-coordinates, adding points to a Fenwick Tree (Binary Indexed Tree) based on their y-coordinate.
4. Answer queries using prefix sums on the Fenwick Tree.

Optimization: Since we only care about pairs within the same character set group, we process each group independnetly. This allows us to clear the Fenwick Tree efficiently without $O(n)$ overhead per group, by only resetting modified indices.

Finally, subtract cases where a string is counted against itself (which happens if the prefix/suffix match covers the whole string or trivial cases).

Implementation

The following C++ implementation incorporates the Trie construction, character set grouping, and the sweep-line algorithm for 2D range queries.

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

typedef long long ll;
const int MAXN = 200005;
const int IMPOSSIBLE = 1337;

int n, len;
char buffer[MAXN];
string strs[MAXN];

// Forward and Reverse Trie structures
int trieFwd[MAXN][27], trieBwd[MAXN][27];
int cntFwd = 0, cntBwd = 0;
int leafFwd[MAXN], leafBwd[MAXN]; // Leaf index for each string
int minIdxFwd[MAXN], maxIdxFwd[MAXN]; // Range covered by node in DFS order
int minIdxBwd[MAXN], maxIdxBwd[MAXN];
int dfsCntFwd = 0, dfsCntBwd = 0;
bool isLeafFwd[MAXN], isLeafBwd[MAXN];

// Character set grouping
int charsetTrie[MAXN][27], cntCharset = 0;
int groupID[MAXN], groupSize[MAXN];
int totalGroups = 0;
vector<int> groupMembers[MAXN];

// Data structures for 2D queries
struct Point {
    int x, y, gid;
} points[MAXN];

struct Query {
    int x, y, type, id;
} queries[MAXN * 4];

int bit[MAXN];
vector<int> modifiedIndices;

void update(int idx, int val) {
    for (; idx <= n; idx += idx & -idx) {
        if (bit[idx] == 0) modifiedIndices.push_back(idx);
        bit[idx] += val;
    }
}

int query(int idx) {
    int res = 0;
    for (; idx > 0; idx -= idx & -idx) {
        res += bit[idx];
    }
    return res;
}

void clearBIT() {
    for (int idx : modifiedIndices) {
        bit[idx] = 0;
    }
    modifiedIndices.clear();
}

// Insert into Forward Trie
void insertFwd(int strIdx) {
    int node = 0;
    for (int i = 0; i < len; ++i) {
        int c = strs[strIdx][i] - 'a' + 1;
        if (!trieFwd[node][c]) trieFwd[node][c] = ++cntFwd;
        node = trieFwd[node][c];
    }
    isLeafFwd[node] = true;
    leafFwd[strIdx] = node;
}

// Insert into Reverse Trie
void insertBwd(int strIdx) {
    int node = 0;
    for (int i = len - 1; i >= 0; --i) {
        int c = strs[strIdx][i] - 'a' + 1;
        if (!trieBwd[node][c]) trieBwd[node][c] = ++cntBwd;
        node = trieBwd[node][c];
    }
    isLeafBwd[node] = true;
    leafBwd[strIdx] = node;
}

// DFS to assign ranges for Forward Trie
void dfsFwd(int u) {
    if (isLeafFwd[u]) {
        minIdxFwd[u] = maxIdxFwd[u] = ++dfsCntFwd;
        return;
    }
    minIdxFwd[u] = MAXN;
    maxIdxFwd[u] = 0;
    for (int i = 1; i <= 26; ++i) {
        if (trieFwd[u][i]) {
            dfsFwd(trieFwd[u][i]);
            minIdxFwd[u] = min(minIdxFwd[u], minIdxFwd[trieFwd[u][i]]);
            maxIdxFwd[u] = max(maxIdxFwd[u], maxIdxFwd[trieFwd[u][i]]);
        }
    }
}

// DFS to assign ranges for Reverse Trie
void dfsBwd(int u) {
    if (isLeafBwd[u]) {
        minIdxBwd[u] = maxIdxBwd[u] = ++dfsCntBwd;
        return;
    }
    minIdxBwd[u] = MAXN;
    maxIdxBwd[u] = 0;
    for (int i = 1; i <= 26; ++i) {
        if (trieBwd[u][i]) {
            dfsBwd(trieBwd[u][i]);
            minIdxBwd[u] = min(minIdxBwd[u], minIdxBwd[trieBwd[u][i]]);
            maxIdxBwd[u] = max(maxIdxBwd[u], maxIdxBwd[trieBwd[u][i]]);
        }
    }
}

// Group strings by character set
void assignGroups(int strIdx) {
    int node = 0;
    int counts[27] = {0};
    for (char c : strs[strIdx]) counts[c - 'a' + 1]++;
    
    for (int i = 1; i <= 26; ++i) {
        for (int k = 0; k < counts[i]; ++k) {
            if (!charsetTrie[node][i]) charsetTrie[node][i] = ++cntCharset;
            node = charsetTrie[node][i];
        }
    }
    
    if (groupSize[node] == 0) {
        groupSize[node] = 0;
        totalGroups++;
        groupID[node] = totalGroups;
    }
    
    int gid = groupID[node];
    groupMembers[gid].push_back(strIdx);
    groupSize[node]++;
    points[strIdx].gid = gid;
}

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

    if (!(cin >> n)) return 0;
    
    ll totalPairs = (ll)n * (n - 1) / 2;
    ll ans = 0;
    ll count1337 = 0;
    ll count1 = 0;

    for (int i = 1; i <= n; ++i) {
        cin >> buffer;
        strs[i] = string(buffer);
        if (i == 1) len = strs[i].length();
        
        insertFwd(i);
        insertBwd(i);
        assignGroups(i);
    }

    dfsFwd(0);
    dfsBwd(0);

    // Calculate 1337 pairs
    for (int i = 1; i <= n; ++i) {
        points[i].x = minIdxFwd[leafFwd[i]];
        points[i].y = minIdxBwd[leafBwd[i]];
    }

    for (int g = 1; g <= totalGroups; ++g) {
        ll sz = groupMembers[g].size();
        count1337 += sz * (n - sz);
    }
    count1337 /= 2; // Each pair counted twice
    ans += count1337 * IMPOSSIBLE;
    ll remainingPairs = totalPairs - count1337;

    // Prepare points sorted by group and x-coordinate
    sort(points + 1, points + n + 1, [](const Point& a, const Point& b) {
        if (a.gid != b.gid) return a.gid < b.gid;
        return a.x < b.x;
    });

    int groupStart[MAXN], groupEnd[MAXN];
    int currentG = -1;
    for (int i = 1; i <= n; ++i) {
        if (points[i].gid != currentG) {
            if (currentG != -1) groupEnd[currentG] = i - 1;
            currentG = points[i].gid;
            groupStart[currentG] = i;
        }
    }
    groupEnd[currentG] = n;

    // Process each group for f=1
    for (int g = 1; g <= totalGroups; ++g) {
        if (groupMembers[g].empty()) continue;
        
        int qCount = 0;
        int selfMatch = 0;

        for (int idx : groupMembers[g]) {
            int l = 0;
            for (int r = 1; r < len; ++r) {
                if (strs[idx][r] < strs[idx][r - 1]) {
                    // Maximal non-decreasing segment ended at r-1
                    // Prefix: 0 to l-1, Suffix: r to len-1
                    // Query ranges in Tries
                    int pFwd = 0;
                    for (int k = 0; k < l; ++k) pFwd = trieFwd[pFwd][strs[idx][k] - 'a' + 1];
                    int L1 = minIdxFwd[pFwd], R1 = maxIdxFwd[pFwd];
                    
                    int pBwd = 0;
                    for (int k = len - 1; k >= r; --k) pBwd = trieBwd[pBwd][strs[idx][k] - 'a' + 1];
                    int L2 = minIdxBwd[pBwd], R2 = maxIdxBwd[pBwd];

                    // Add 2D query
                    queries[++qCount] = {L1 - 1, L2 - 1, -1, 0};
                    queries[++qCount] = {R1, R2, 1, 0};
                    queries[++qCount] = {L1 - 1, R2, -1, 0};
                    queries[++qCount] = {R1, L2 - 1, -1, 0};
                    
                    l = r;
                    selfMatch++;
                }
            }
            // Last segment
            int pFwd = 0;
            for (int k = 0; k < l; ++k) pFwd = trieFwd[pFwd][strs[idx][k] - 'a' + 1];
            int L1 = minIdxFwd[pFwd], R1 = maxIdxFwd[pFwd];
            
            int pBwd = 0;
            for (int k = len - 1; k >= l; --k) pBwd = trieBwd[pBwd][strs[idx][k] - 'a' + 1];
            int L2 = minIdxBwd[pBwd], R2 = maxIdxBwd[pBwd];

            queries[++qCount] = {L1 - 1, L2 - 1, -1, 0};
            queries[++qCount] = {R1, R2, 1, 0};
            queries[++qCount] = {L1 - 1, R2, -1, 0};
            queries[++qCount] = {R1, L2 - 1, -1, 0};
            selfMatch++;
        }

        // Sort queries by x
        sort(queries + 1, queries + qCount + 1, [](const Query& a, const Query& b) {
            return a.x < b.x;
        });

        int pIdx = groupStart[g];
        int limit = groupEnd[g];
        
        for (int i = 1; i <= qCount; ++i) {
            while (pIdx <= limit && points[pIdx].x <= queries[i].x) {
                update(points[pIdx].y, 1);
                pIdx++;
            }
            count1 += queries[i].type * query(queries[i].y);
        }
        clearBIT();
        count1 -= selfMatch; // Remove self-matches
    }

    ans += count1;
    ll count2 = remainingPairs - count1;
    ans += count2 * 2;

    cout << ans << endl;
    return 0;
}