题目分析

题意理解

我们有一个字符串 S，需要处理 q 次询问。每次询问给出子串 S[l..r]，要求计算满足以下条件的数对 (i,j) 的个数：

1. 1 ≤ i < j ≤ n
2. i + 1 < j（即 i 和 j 之间至少有一个位置）
3. 子串 S[l..r] 出现在以下三个部分中的至少一个：
   • S[1..i]（前缀）
   • S[i+1..j-1]（中间段）
   • S[j..n]（后缀）

关键难点

1. 子串出现位置：需要判断子串在三个区间的出现情况
2. 组合计数：计算满足条件的 (i,j) 对数量
3. 高效查询：n,q 都很大，需要高效算法

算法思路

核心思想：后缀数组 + 并查集合并 + 线段树维护

1. 后缀数组预处理

• 构建后缀数组 SA 和高度数组 height
• 便于快速处理子串出现位置

2. 离线处理

按子串长度从大到小处理询问，利用并查集合并相关信息

3. 容斥计算

计算不满足条件的 (i,j) 对，然后用总数减去

代码详解

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

const int N = 100010, M = 300010;

int n, q, m;
int sa[N], SA[N], first[2*N], First[2*N], buc[2*N], tot;
int ans[M], a1, a2;
string s;
int height[N];
int f[N], root[2*N], ls[2*N], rs[2*N], num;

// 线段树节点
struct node {
    int cnt, maxx, minn, sum;  // 计数、最大值、最小值、总和
};

struct que {
    int nowl, nowr, id;  // 询问的左右端点和id
};

vector<que> v[N];        // 按长度分组的询问
vector<int> vnum[N];     // 按高度分组的位置

node tree[2*N];

// 构建后缀数组
void suffix_array() {
    m = 11;  // 字符集大小：数字0-9
    
    // 第一次基数排序
    for (int i = 1; i <= n; i++) {
        first[i] = s[i] - '0' + 1;
        buc[s[i] - '0' + 1]++;
    }
    for (int i = 1; i <= m; i++) buc[i] += buc[i-1];
    for (int i = 1; i <= n; i++) sa[buc[s[i] - '0' + 1]--] = i;
    
    // 倍增构建
    for (int k = 1; k <= n; k <<= 1) {
        tot = 0;
        for (int i = 1; i <= m; i++) buc[i] = 0;
        
        // 统计第一关键字
        for (int i = 1; i <= n; i++) buc[first[i]]++;
        for (int i = 1; i <= m; i++) buc[i] += buc[i-1];
        
        // 第二关键字排序
        for (int i = n; i >= 1; i--) {
            if (sa[i] > k) 
                SA[buc[first[sa[i] - k]]--] = sa[i] - k;
        }
        
        // 处理没有第二关键字的部分
        for (int i = n - k + 1; i <= n; i++) {
            SA[buc[first[i]]--] = i;
        }
        
        // 重新标号
        for (int i = 1; i <= n; i++) {
            if (first[SA[i]] == first[SA[i-1]] && 
                first[SA[i] + k] == first[SA[i-1] + k]) {
                First[SA[i]] = tot;
            } else {
                First[SA[i]] = ++tot;
            }
        }
        
        // 更新数组
        for (int i = 1; i <= n; i++) {
            first[i] = First[i];
            sa[i] = SA[i];
        }
        
        if (tot == n) break;
        m = tot;
    }
}

// 计算高度数组
void get_h() {
    int now = 0;
    for (int i = 1; i <= n; i++) {
        if (first[i] == 1) continue;
        if (now > 0) now--;
        
        // 扩展匹配长度
        while (s[i + now] == s[sa[first[i] - 1] + now])
            now++;
            
        height[first[i]] = now;
        vnum[now].push_back(first[i]);  // 按高度分组
    }
}

// 线段树合并
node push_up(node x, node y) {
    if (x.sum == 0) return y;
    if (y.sum == 0) return x;
    
    node res;
    res.sum = x.sum + y.sum;
    res.maxx = max(x.maxx, y.maxx);
    res.minn = min(x.minn, y.minn);
    // 计算新的cnt值
    res.cnt = x.cnt + y.cnt + (x.maxx - 1) * (y.minn - x.maxx);
    return res;
}

// 线段树插入
void insert(int now, int &x, int l, int r) {
    if (!x) x = ++num;
    
    if (l == r) {
        tree[x] = {0, now, now, 1};
        return;
    }
    
    int mid = (l + r) >> 1;
    if (now <= mid) 
        insert(now, ls[x], l, mid);
    else 
        insert(now, rs[x], mid + 1, r);
    
    // 合并左右子树信息
    if (!ls[x] || !rs[x]) 
        tree[x] = tree[ls[x] | rs[x]];
    else 
        tree[x] = push_up(tree[ls[x]], tree[rs[x]]);
}

// 线段树查询
node query(int L, int R, int x, int l, int r) {
    if (!x || L > R) return {0, 0, 0, 0};
    if (L <= l && r <= R) return tree[x];
    
    int mid = (l + r) >> 1;
    if (L <= mid && mid < R) 
        return push_up(query(L, R, ls[x], l, mid), 
                      query(L, R, rs[x], mid + 1, r));
    if (L <= mid) 
        return query(L, R, ls[x], l, mid);
    return query(L, R, rs[x], mid + 1, r);
}

// 线段树合并
int merge(int x, int y) {
    if (!x || !y) return x | y;
    
    ls[x] = merge(ls[x], ls[y]);
    rs[x] = merge(rs[x], rs[y]);
    tree[x] = push_up(tree[ls[x]], tree[rs[x]]);
    return x;
}

// 初始化并查集和线段树
void init() {
    for (int i = 1; i <= n; i++) {
        f[i] = i;
        insert(sa[i], root[i], 1, n);  // 每个后缀初始独立
    }
}

// 并查集查找
int Find(int x) {
    return f[x] == x ? x : f[x] = Find(f[x]);
}

// 并查集合并
void Union(int x, int y) {
    int fx = Find(x), fy = Find(y);
    if (fx != fy) {
        root[fy] = merge(root[fx], root[fy]);
        f[fx] = fy;
    }
}

// 处理单个询问
void solve(que x) {
    int len = x.nowr - x.nowl + 1;
    int fx = Find(first[x.nowl]);  // 找到所在集合
    
    // 如果整个字符串都包含该子串，直接返回
    if (tree[root[fx]].maxx == n || x.nowl == x.nowr) 
        return;
        
    int mx = tree[root[fx]].maxx, mn = tree[root[fx]].minn;
    node temp, temp1, temp2;
    
    // 情况1：最大值-长度+1 > 最小值
    if (mx - len + 1 > mn) {
        int lmx = mx - len + 1, rmn = mn + len - 1;
        
        if (lmx > rmn) {
            // 子串出现位置有间隔
            if (rmn + 1 <= lmx - 1) {
                temp = query(rmn + 1, lmx - 1, root[fx], 1, n);
                if (temp.sum > 0) return;  // 中间有出现，不满足条件
            }
            
            temp1 = query(1, lmx - 1, root[fx], 1, n);
            temp2 = query(lmx, n, root[fx], 1, n);
            ans[x.id] += (temp2.minn - lmx + 1) * (rmn - temp1.maxx + 1);
        } else {
            // 子串出现位置有重叠
            temp1 = query(rmn + 1, n, root[fx], 1, n);
            temp = query(lmx, temp1.minn, root[fx], 1, n);
            temp2 = query(1, lmx - 1, root[fx], 1, n);
            ans[x.id] += (temp.minn - lmx + 1) * (rmn - temp2.maxx + 1);
            ans[x.id] += (temp.maxx - temp.minn) * rmn - temp.cnt;
        }
    } else {
        // 情况2：其他复杂情况
        int lmx = mx - len + 1, rmn = mn + len - 1;
        ans[x.id] += (mx - 1 + rmn - 1) * (rmn - mx + 1) / 2;
        
        if (mx + len - 1 > n - 1) {
            temp = query(mn, n - 1 - len + 1, root[fx], 1, n);
            ans[x.id] += (temp.maxx - temp.minn) * rmn - temp.cnt;
            ans[x.id] += (n - 1 - len + 1 - temp.maxx + 1) * 
                        (n - 1 - len + 1 - temp.maxx) / 2;
            return;
        }
        
        temp = query(mn, mx, root[fx], 1, n);
        ans[x.id] += (temp.maxx - temp.minn) * rmn - temp.cnt;
        ans[x.id] += (n - 1 - (mx + len - 1)) * (rmn - mx + 1);
    }
}

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    
    cin >> n >> q;
    cin >> s;
    s = '#' + s;  // 转为1-index
    
    // 预处理
    suffix_array();
    get_h();
    
    // 读入询问并按长度分组
    for (int i = 1; i <= q; i++) {
        cin >> a1 >> a2;
        if (a1 > a2 || a1 < 1 || a1 > n || a2 < 1 || a2 > n) {
            ans[i] = -1;  // 标记非法询问
            continue;
        }
        v[a2 - a1 + 1].push_back({a1, a2, i});
    }
    
    init();  // 初始化数据结构
    
    // 从大到小处理长度
    for (int i = n; i > 0; i--) {
        // 合并高度为i的后缀
        for (int j : vnum[i]) {
            Union(j - 1, j);
        }
        // 处理该长度的所有询问
        for (auto j : v[i]) {
            solve(j);
        }
    }
    
    // 输出结果
    int total = (n - 1) * (n - 2) / 2;  // 总对数
    for (int i = 1; i <= q; i++) {
        if (ans[i] == -1) 
            cout << total << endl;  // 非法询问输出总数
        else 
            cout << total - ans[i] << endl;  // 合法询问输出剩余对数
    }
    
    return 0;
}

算法核心要点详解

1. 后缀数组的作用

• 快速定位：通过后缀数组可以快速找到子串的所有出现位置
• 高度数组：记录相邻后缀的最长公共前缀，用于合并相关信息

2. 并查集合并策略

按高度从大到小合并后缀：

• 高度大的后缀先合并，保证正确性
• 每个集合维护该子串的所有出现位置

3. 线段树维护的信息

每个集合用线段树维护：

• 出现位置：子串在原文中的所有起始位置
• 统计信息：用于快速计算不满足条件的 (i,j) 对

4. 容斥计算

总方案数 = 所有 (i,j) 对的数量 不满足条件的方案 = 子串不出现在任何一段的方案 答案 = 总方案数 - 不满足条件的方案

复杂度分析

• 后缀数组：O(n log n)
• 并查集+线段树合并：O(n log² n)
• 查询处理：O(q log n)
• 总复杂度：能够处理 n=10⁵, q=3×10⁵ 的数据

总结

这道题综合运用了：

1. 后缀数组 处理字符串匹配
2. 并查集 维护连通性
3. 线段树合并 维护集合信息
4. 离线处理 优化查询
5. 容斥原理 计算方案数

是一个很好的字符串与数据结构综合题目，考察了后缀数组和复杂数据结构的深入应用。