传送门

原本的想法是把所有的串不管是名字还是询问都连起来，记录一下询问串在sa数组中的位置

对于每个询问可以在sa数组中二分出左右边界，第一问用莫队，第二问差分乱搞。

结果发现我差分的思路想错了，先写了一个暴力，二分出左右边界之后直接从l枚举到r，想试试正确性，就交了一遍，结果过了。。。。

因为是暴力，可以不用二分左右边界，直接向左向右枚举扩展就可以了，st表也不用了，但我懒得改了

#include <cmath>#include <cstdio>#include <cstring>#include <iostream>#define N 2000001using namespace std;int n, m, cnt, mx, len;int M[N], x[N], y[N], s[N], sa[N], b[N], d[N][21], Rank[N], Log[N], height[N], id[N], pos[N], ans[N], num[N];inline int read()inline void build_sa()}inline void build_height()}inline void build_st()Log[i] = log2(i);for(j = 1; (1 << j) < len; j++)for(i = 1; i + (1 << j)  1 < len; i++)d[i][j] = min(d[i][j  1], d[i + (1 << j  1)][j  1]);}inline int query(int l, int r)inline int search2(int p, int llen)return r;}inline int search1(int p, int llen)return l  1;}inline void solve()for(i = 1; i <= n; i++) printf("%d ", ans[i]);}int main()s[len++] = mx++;}for(i = 1; i <= m; i++)mx = 120000;build_sa();build_height();build_st();solve();return 0;}