题目分析

小 Z 和小 A 玩扑克比大小游戏，规则是：

1. 双方各发一堆牌（字符串）
2. 每轮比较堆顶牌，字母小者胜；若相同则将牌放回牌堆底继续
3. 系统从牌库 $a_1a_2\cdots a_n$ 中取子串 $a_la_{l+1}\cdots a_r$ 发给小 A
4. 求小 Z 有多少种可能的手牌能赢小 A

手牌不同当且仅当：长度不同或存在某位置牌不同。

核心思路

1. 游戏胜负判定

比较两个循环字符串 $S$ 和 $T$：

• 设 $S = s_1s_2\cdots s_m$，$T = t_1t_2\cdots t_k$
• 游戏等价于比较无限循环串 $S^\infty$ 和 $T^\infty$ 的字典序
• $S^\infty < T^\infty$ 当且仅当小 Z 获胜

2. 问题转化

对于给定的 $T = a_la_{l+1}\cdots a_r$，求有多少个字符串 $S$ 满足 $S^\infty < T^\infty$。

进一步转化：将 $S$ 按长度分类：

• 长度 $m < k$：$S^\infty$ 是周期串，比较 $S^\infty$ 和 $T^\infty$ 的前 $m$ 个周期
• 长度 $m = k$：直接比较循环同构
• 长度 $m > k$：需要特殊处理

算法实现详解

1. 后缀数组预处理

// 构建后缀数组、Height数组、ST表
void Init() {
    m = max(300, n + 1);
    
    // 倍增法构建后缀数组
    for (int h = 1, w = 1; w <= n; h++, w <<= 1) {
        // 双关键字基数排序
        memset(cnt, 0, sizeof(cnt)), memcpy(id, sa, sizeof(sa));
        for (int i = 1; i <= n; i++) cnt[rk[id[i] + w]]++;
        for (int i = 1; i <= m; i++) cnt[i] += cnt[i - 1];
        for (int i = n; i; i--) sa[cnt[rk[id[i] + w]]--] = id[i];
        
        // 类似处理第一关键字...
        
        // 更新排名
        for (int i = 1, p = 0; i <= n; i++) {
            if (rk_[sa[i]] != rk_[sa[i-1]] || rk_[sa[i] + w] != rk_[sa[i-1] + w])
                p++, fl++;
            rk[sa[i]] = p;
            if (h < 20) bel[h][sa[i]] = fl, tg[fl].push_back(sa[i]);
        }
    }
    
    // 构建Height数组和ST表
    for (int i = 1, k = 0; i <= n; i++) {
        k = max(k - 1, 0);
        while (S[i + k] == S[sa[rk[i] - 1] + k]) k++;
        height[rk[i]] = k;
    }
    
    // 构建ST表用于RMQ查询LCP
    for (int i = 2; i <= n; i++) Log[i] = Log[i >> 1] + 1;
    for (int i = 1; i <= Log[n]; i++)
        for (int j = 1; j + (1 << i) - 1 <= n; j++)
            st[i][j] = min(st[i-1][j], st[i-1][j + (1 << i - 1)]);
    
    // 前缀和：sum[i] = Σ_{j=1}^i (n - sa[j] + 1 - height[j])
    for (int i = 1; i <= n; i++)
        sum[i] = sum[i - 1] + (n - sa[i] + 1) - height[i];
}

2. 关键数据结构：等差数列表示

struct Info {
    int l, r, d;  // 等差数列：首项l，末项r，公差d
    inline int cnt() { return (r - l) / d + 1; }
    inline bool in(int x) { return l <= x && x <= r && (x - l) % d == 0; }
};

// 等差数列的交集运算
Info operator+(Info A, Info B) {
    if (A.cnt() > 2) {
        if (B.cnt() > 2) {
            // 都是长等差数列：检查是否同公差且相交
            if ((A.l - B.l) % A.d || A.r < B.l || B.r < A.l)
                return nop;
            else
                return Info{max(A.l, B.l), min(A.r, B.r), A.d};
        } else {
            // 处理混合情况...
        }
    } else {
        // 处理短序列情况...
    }
}

3. 循环串比较函数

// 比较 S[x:n] 和 S[l:r]^∞ (无限循环串)
bool cmpinf(int x, int l, int r) {
    int t = lcpinf(x, l, r);  // 最长公共前缀
    return S[x + t] < S[l + t % (r - l + 1)];
}

// 计算 S[x:n] 和 S[l:r]^∞ 的LCP
int lcpinf(int x, int l, int r) {
    int t = lcp(x, l);  // 普通LCP
    if (t < r - l + 1) return t;
    else return lcp(x, x + r - l + 1) + r - l + 1;
}

4. 主要查询逻辑

int find_loc(int L, int R) {
    // 二分查找在SA中 S[L:R]^∞ 的位置
    int l = 1, r = n, mid, ans = 0;
    while (l <= r) {
        mid = (l + r >> 1);
        if (cmpinf(sa[mid], L, R))  // S[sa[mid]:] < S[L:R]^∞
            ans = mid, l = mid + 1;
        else r = mid - 1;
    }
    return ans;
}

// 主查询函数
long long ans = 0;
int tk = find_loc(l, r);  // 找到边界位置
ans = sum[tk] - lcpinf(sa[tk], l, r);  // 基础答案

// 处理特殊情况：需要修正的边界情况
int pl = lcpinf(sa[tk], l, r), pr = lcpinf(sa[tk + 1], l, r);
if (pr > pl) tk++, L = pr;
else L = pl;

// 添加需要BIT处理的查询
op[tk].push_back(qry{sa[tk] + 1, sa[tk] + len - 1, i, L / len});
op[tk].push_back(qry{sa[tk] + 1, sa[tk] + L % len, i, 1});

// 处理border：利用等差数列优化
for (int h = 0, w = 1, cnt; w < len; h++, w <<= 1) {
    Info g = ((r + 1) - get_border(bel[h][l], max(l + 1, r - (w << 1) + 2), r - w + 1)) 
             + (get_border(bel[h][r - w + 1], l, min(l + w - 1, r - 1)) + (w - l));
    
    if (g.l <= g.r) {
        cnt = g.cnt();
        // 二分查找需要修正的位置
        // 计算并修正答案...
    }
}

5. 树状数组处理

namespace BIT {
    int num[500010];
    void add(int x) { for (; x <= n; x += (x & -x)) num[x]++; }
    int sum(int x) { int ret = 0; for (; x; x -= (x & -x)) ret += num[x]; return ret; }
    int sum(int l, int r) { return sum(r) - sum(l - 1); }
}

// 离线处理查询
for (int i = n; i; i--) {
    for (qry &g : op[i]) {
        ans[g.id] += g.xs * BIT::sum(g.L, g.R);
    }
    BIT::add(sa[i]);
}

关键算法技术

1. 后缀数组技术

• 倍增法构建SA，$O(n \log n)$
• Height数组 + ST表实现 $O(1)$ LCP查询
• 支持快速比较任意子串

2. 等差数列优化

• 使用等差数列表示候选位置集合
• 高效计算集合交集
• 减少二分查找次数

3. 循环串处理

• 将无限循环串比较转化为有限比较
• 利用字符串周期性质优化
• 处理border的修正

4. 离线处理

• 将所有查询按右端点排序
• 使用树状数组维护前缀信息
• 避免重复计算

复杂度分析

时间复杂度

• 预处理：$O(n \log n)$ 构建后缀数组
• 单次查询：$O(\log^2 n)$
  • 二分查找边界：$O(\log n)$
  • border处理：$O(\log n)$ 层，每层 $O(\log n)$
• 总复杂度：$O(n \log n + q \log^2 n)$，适合 $n, q \leq 5\times 10^5$

空间复杂度

• 后缀数组相关：$O(n \log n)$
• 查询处理：$O(n + q)$

算法标签

主要算法：

• 后缀数组
• 树状数组
• 二分查找
• 等差数列优化

关键技术：

• 循环串比较
• 离线处理
• 字符串周期分析

问题特征：

• 无限循环串字典序比较
• 大规模多查询
• 字符串匹配与比较

总结

这道题通过巧妙的后缀数组应用和等差数列优化，高效解决了大规模循环串比较问题。算法核心在于将无限循环串的比较转化为有限比较，利用字符串的周期性质和border结构进行优化，最终在 $O(n \log n + q \log^2 n)$ 的时间复杂度内处理了高达 $5\times 10^5$ 的查询，展示了字符串处理算法的强大能力。