「HDU 2021 Multi 10」[HDU 7074] Pty loves string

「题意」

给定长为 $n$ 的字符串 $s[1\cdots n]$,有 $m$ 个询问。每次给定 $x,y$,查询由 $s[1,x]$ 和 $s[n-y+1,n]$ 拼接而成的字符串在 $s$ 中的出现次数。

$T\leq 5,n,m\leq 2\times 10^5$

「链接」

7084

「分析」

对于一个出现位置 $s[l,r]$ ,满足 $s[l,l + x − 1]$ 和 $s[1,x]$ 相等, $s[r − y + 1,r]$ 和 $s[n − y + 1,n]$ 相等,且 $l+x-1+1=r-y+1$。

对于 $s[1,l+x-1]$ 来说,这两个相等的部分就是前后缀,这能联想到border。

用KMP预处理,通过跳next,$s[l+x-1]$ 能跳到 $s[x]$。从后往前跑KMP,反着建next,$s[r-y+1]$ 能跳到 $s[n-y+1]$。

因此可以建成正反两棵next树,$i$ 与 $next[i]$ 连边,那么符合条件的便是 $x$ 子树的所有节点。

而由于 $l+x=r-y+1$,因此若两棵子树上的两个点编号差为 $1$,则它们对应的 $[l,r]$ 便是一个出现位置。

问题转化为两棵树,查询在第一棵树中 $x$ 的子树与第二棵树中 $n-y+1$ 的子树中,节点编号差为 $1$ 的点对数量。

这可以转化为二维数点问题。

具体来说,对两棵树求DFS序,并将第一棵树的DFS序(因为节点编号差 $1$,因此整体右移一位)映射到第二棵树上。现在只需要求DFS序在 $[Dfn[y],Dfn[y]+Sz[y]-1]$ 中,权值在 $[Dfn[x],Dfn[x]+Sz[x]-1]$ 中的点个数。

这可以用主席树或者其他一个log的方法解决。

复杂度 $O(m\log{n})$。

「参考代码」

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
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
/*
* @date:
* @source:
*/
#include <bits/stdc++.h>

using namespace std;

typedef pair<int, int> pii;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
#define fir first
#define sec second
#define ALL(x) (x).begin(), (x).end()
#define SZ(x) (int)x.size()
#define up(i, l, r) for (int i = l; i <= r; ++i)
#define dn(i, l, r) for (int i = l; i >= r; --i)
#define Trav(i, x) for (auto & i : x)
#define pb push_back
template<class T, class G> bool chkMax(T &x, G y) {
return y > x ? x = y, 1 : 0;
}
template<class T, class G> bool chkMin(T &x, G y) {
return y < x ? x = y, 1 : 0;
}

const int N = 2e5 + 5;

int n, m;
char s[N];
int Nxt[N], Nxt2[N];

struct Tree {
static const int N = ::N;
vi G[N];
int Dfn[N], Nfd[N], Sz[N], tot;
void addEdge(int u, int v) {
G[u].pb(v);
G[v].pb(u);
}
void dfs(int x, int fa) {
Dfn[x] = ++tot;
Nfd[tot] = x;
Sz[x] = 1;
Trav(v, G[x]) {
if (v == fa) continue;
dfs(v, x);
Sz[x] += Sz[v];
}
}
void init(int n) {
for (int i = 0; i <= n; ++i) G[i].clear();
tot = 0;
}
} t1, t2;

struct PresidentTree {
static const int N = ::N * 40;
struct Node {
int ls, rs, sum;
} A[N];
int tot;
int newNode() {
A[tot].ls = A[tot].rs = A[tot].sum = 0;
return tot++;
}
void init() {
tot = 1;
}
int insert(int u, int l, int r, int p) {
int rt = newNode();
A[rt] = A[u];
if (l == r) {
A[rt].sum++;
} else {
int m = (l + r) >> 1;
if (p <= m) A[rt].ls = insert(A[u].ls, l, m, p);
else A[rt].rs = insert(A[u].rs, m + 1, r, p);
A[rt].sum = A[A[rt].ls].sum + A[A[rt].rs].sum;
}
return rt;
}
int query(int u, int v, int l, int r, int a, int b) {
if (a <= l && r <= b) return A[v].sum - A[u].sum;
int m = (l + r) >> 1, sum = 0;
if (a <= m) sum += query(A[u].ls, A[v].ls, l, m, a, b);
if (m < b) sum += query(A[u].rs, A[v].rs, m + 1, r, a, b);
return sum;
}
} t3;

int Rt[N];

void solve() {
cin >> n >> m >> (s + 1);
Nxt[1] = 0;
for (int i = 2, j = 0; i <= n; ++i) {
while (j >= 1 && s[i] != s[j + 1]) j = Nxt[j];
if (s[j + 1] == s[i]) j++;
Nxt[i] = j;
}
Nxt2[n] = n + 1;
for (int i = n - 1, j = n + 1; i >= 1; --i) {
while (j <= n && s[i] != s[j - 1]) j = Nxt2[j];
if (s[j - 1] == s[i]) j--;
Nxt2[i] = j;
}
t1.init(n + 1); t2.init(n + 1);
for (int i = 1; i <= n; ++i) {
t1.addEdge(i, Nxt[i]);
t2.addEdge(i, Nxt2[i]);
}
t1.dfs(0, -1);
t2.dfs(n + 1, -1);
t3.init();
for (int i = 1; i <= n + 1; ++i) {
Rt[i] = t3.insert(Rt[i - 1], 1, n + 1, t2.Dfn[t1.Nfd[i] + 1]);
}
for (int i = 1, x, y; i <= m; ++i) {
cin >> x >> y;
y = n - y + 1;
cout << t3.query(Rt[t1.Dfn[x] - 1], Rt[t1.Dfn[x] + t1.Sz[x] - 1], 1, n + 1, t2.Dfn[y], t2.Dfn[y] + t2.Sz[y] - 1) << "\n";
}
}


int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int Case;
cin >> Case;
while (Case--) solve();
return 0;
}