题意：求字符串[l, r]这些前缀的两两之间最长的最长公共后缀。
把fail树建出来，就是编号在一段区间的最深lca。
套用我之前口胡的莫队做法可以做到O(n√n)，光荣70分。
而且我还非常SB的把原串，fail树，链表上的节点搞混了......
这个链表是那些关键节点按照DFS序串起来的。莫队的时候注意严格按照顺序来搞...
1 /** 2 * There is no end though there is a start in space. ---Infinity. 3 * It has own power, it ruins, and it goes though there is a start also in the star. ---Finite. 4 * Only the person who was wisdom can read the most foolish one from the history. 5 * The fish that lives in the sea doesn't know the world in the land. 6 * It also ruins and goes if they have wisdom. 7 * It is funnier that man exceeds the speed of light than fish start living in the land. 8 * It can be said that this is an final ultimatum from the god to the people who can fight. 9 * 10 * Steins;Gate 11 */ 12 13 #include <bits/stdc++.h> 14 15 const int N = 200010; 16 17 struct Edge { 18 int nex, v; 19 }edge[N << 1]; int tp; 20 21 int tot = 1, last = 1, tr[N][2], fail[N], len[N], e[N]; 22 int d[N], ST[N << 2][20], pw[N << 2], num2, pos2[N], lc[N], rc[N]; 23 int n, m, id[N], T, fr[N], pre[N], nex[N], Ans[N], id2[N], num; 24 char str[N]; 25 26 struct Ask { 27 int l, r, id; 28 inline bool operator < (const Ask &w) const { 29 if(fr[l] != fr[w.l]) return l < w.l; 30 return r > w.r; 31 } 32 }ask[N]; 33 34 namespace BlockV { 35 int cnt[N], a[N]; 36 inline void clear() { 37 memset(cnt + 1, 0, fr[n] * sizeof(int)); 38 memset(a, 0, sizeof(a)); 39 return; 40 } 41 inline void insert(int x, int v) { 42 a[x] += v; 43 cnt[fr[x]] += v; 44 //printf("Block add %d %d ", x, v); 45 return; 46 } 47 inline int getMax() { 48 for(int i = fr[n]; i >= 0; i--) { 49 if(cnt[i]) { 50 for(int j = rc[i]; j >= lc[i]; j--) { 51 if(a[j]) return j; 52 } 53 return -1; 54 } 55 } 56 return -1; 57 } 58 } 59 60 inline bool cmp(const int &a, const int &b) { 61 return pos2[a] < pos2[b]; 62 } 63 64 inline void add(int x, int y) { 65 tp++; 66 edge[tp].v = y; 67 edge[tp].nex = e[x]; 68 e[x] = tp; 69 return; 70 } 71 72 inline void insert(char c) { 73 int f = c == '1', p = last, np = ++tot; 74 last = np; 75 len[np] = len[p] + 1; 76 while(p && !tr[p][f]) { 77 tr[p][f] = np; 78 p = fail[p]; 79 } 80 if(!p) { 81 fail[np] = 1; 82 } 83 else { 84 int Q = tr[p][f]; 85 if(len[Q] == len[p] + 1) { 86 fail[np] = Q; 87 } 88 else { 89 int nQ = ++tot; 90 len[nQ] = len[p] + 1; 91 fail[nQ] = fail[Q]; 92 fail[Q] = fail[np] = nQ; 93 memcpy(tr[nQ], tr[Q], sizeof(tr[Q])); 94 while(tr[p][f] == Q) { 95 tr[p][f] = nQ; 96 p = fail[p]; 97 } 98 } 99 } 100 return; 101 } 102 103 void DFS_1(int x, int f) { 104 pos2[x] = ++num2; 105 ST[num2][0] = x; 106 d[x] = d[f] + 1; 107 for(int i = e[x]; i; i = edge[i].nex) { 108 int y = edge[i].v; 109 if(y == f) { 110 continue; 111 } 112 DFS_1(y, x); 113 ST[++num2][0] = x; 114 } 115 return; 116 } 117 118 inline void prework() { 119 for(int i = 2; i <= num2; i++) pw[i] = pw[i >> 1] + 1; 120 for(int j = 1; j <= pw[num2]; j++) { 121 for(int i = 1; i <= num2; i++) { 122 if(d[ST[i][j - 1]] < d[ST[i + (1 << (j - 1))][j - 1]]) 123 ST[i][j] = ST[i][j - 1]; 124 else 125 ST[i][j] = ST[i + (1 << (j - 1))][j - 1]; 126 } 127 } 128 return; 129 } 130 131 inline int lca(int x, int y) { 132 x = pos2[x], y = pos2[y]; 133 if(x > y) std::swap(x, y); 134 int t = pw[y - x + 1]; 135 if(d[ST[x][t]] < d[ST[y - (1 << t) + 1][t]]) { 136 return ST[x][t]; 137 } 138 else { 139 return ST[y - (1 << t) + 1][t]; 140 } 141 } 142 143 inline void Add(int x) { 144 //printf("add x = %d id = %d ", x, id[x]); 145 x = id[x]; 146 if(nex[x]) pre[nex[x]] = x; 147 if(pre[x]) nex[pre[x]] = x; 148 if(nex[x] && pre[x]) BlockV::insert(len[lca(nex[x], pre[x])], -1); 149 if(nex[x]) { 150 BlockV::insert(len[lca(x, nex[x])], 1); 151 } 152 if(pre[x]) { 153 BlockV::insert(len[lca(x, pre[x])], 1); 154 } 155 return; 156 } 157 158 inline void Del(int x) { 159 //printf("del x = %d id = %d ", x, id[x]); 160 x = id[x]; 161 if(pre[x]) nex[pre[x]] = nex[x]; 162 if(nex[x]) pre[nex[x]] = pre[x]; 163 if(nex[x] && pre[x]) { 164 BlockV::insert(len[lca(nex[x], pre[x])], 1); 165 } 166 if(nex[x]) { 167 BlockV::insert(len[lca(x, nex[x])], -1); 168 } 169 if(pre[x]) { 170 BlockV::insert(len[lca(x, pre[x])], -1); 171 } 172 return; 173 } 174 175 int main() { 176 scanf("%d%d", &n, &m); 177 T = n / sqrt(m); 178 //printf("T = %d sqrt(m)= %d ", T, (int)sqrt(m)); 179 for(int i = 1; i <= n; i++) { 180 fr[i] = (i - 1) / T + 1; 181 //printf("fr %d = %d ", i, fr[i]); 182 } 183 for(int i = 1; i <= fr[n]; i++) { 184 lc[i] = rc[i - 1] + 1; 185 rc[i] = lc[i] + T - 1; 186 if(i == fr[n]) rc[i] = n; 187 } 188 scanf("%s", str + 1); 189 for(int i = 1; i <= m; i++) { 190 scanf("%d%d", &ask[i].l, &ask[i].r); 191 ask[i].id = i; 192 } 193 std::sort(ask + 1, ask + m + 1); 194 for(int i = 1; i <= n; i++) { 195 insert(str[i]); 196 id[i] = id2[i] = last; 197 } 198 for(int i = 2; i <= tot; i++) { 199 add(fail[i], i); 200 //printf("add : %d %d ", fail[i], i); 201 } 202 DFS_1(1, 0); 203 prework(); 204 /// solve 205 206 std::sort(id2 + 1, id2 + n + 1, cmp); 207 208 int p = 1; 209 for(int i = 1; i <= n; i++) { 210 p = tr[p][str[i] == '1']; 211 if(id[i] != p) { 212 printf("ERROR! "); 213 } 214 } 215 216 for(int i = 1; i < n; i++) { 217 int x = id2[i], y = id2[i + 1]; 218 //printf("i = %d x = %d y = %d ", i, x, y); 219 nex[x] = y; 220 pre[y] = x; 221 BlockV::insert(len[lca(x, y)], 1); 222 } 223 p = 1; 224 int l = 1, r = n; 225 for(int i = 1; i <= fr[n]; i++) { 226 while(r < n) Add(++r); 227 while(l < lc[i]) Del(l++); 228 while(fr[ask[p].l] == i) { 229 while(ask[p].r < r) Del(r--); 230 while(l < ask[p].l) Del(l++); 231 Ans[ask[p].id] = BlockV::getMax(); 232 //printf("id = %d ", ask[p].id); 233 while(lc[i] < l) Add(--l); 234 p++; 235 } 236 } 237 for(int i = 1; i <= m; i++) { 238 printf("%d ", Ans[i]); 239 } 240 return 0; 241 }
然后是启发式合并 + 树状数组 + 扫描线代码。
1 /** 2 * There is no end though there is a start in space. ---Infinity. 3 * It has own power, it ruins, and it goes though there is a start also in the star. ---Finite. 4 * Only the person who was wisdom can read the most foolish one from the history. 5 * The fish that lives in the sea doesn't know the world in the land. 6 * It also ruins and goes if they have wisdom. 7 * It is funnier that man exceeds the speed of light than fish start living in the land. 8 * It can be said that this is an final ultimatum from the god to the people who can fight. 9 * 10 * Steins;Gate 11 */ 12 13 #include <bits/stdc++.h> 14 15 const int N = 200010; 16 17 struct Edge { 18 int nex, v; 19 }edge[N << 1]; int tp; 20 21 struct Ask { 22 int l, r, id; 23 Ask(int L = 0, int R = 0, int ID = 0) { 24 l = L; 25 r = R; 26 id = ID; 27 } 28 inline bool operator < (const Ask &w) const { 29 return l < w.l; 30 } 31 }ask[N], node[N * 20]; int Cnt; 32 typedef Ask Node; 33 34 char str[N]; 35 int e[N], n, m, tot = 1, last = 1, tr[N][2], fail[N], len[N], id[N], Ans[N], ta[N]; 36 std::set<int> st[N]; 37 std::set<int>::iterator it, it2; 38 39 inline void add(int x, int y) { 40 tp++; 41 edge[tp].v = y; 42 edge[tp].nex = e[x]; 43 e[x] = tp; 44 return; 45 } 46 47 inline void Add(int x, int y) { 48 //printf("add %d %d ", x, y); 49 for(int i = x; i <= n; i += i & (-i)) { 50 ta[i] = std::max(ta[i], y); 51 } 52 return; 53 } 54 55 inline int Ask(int x) { 56 //printf("ask %d ", x); 57 int ans = 0; 58 for(int i = x; i >= 1; i -= i & (-i)) { 59 ans = std::max(ans, ta[i]); 60 } 61 return ans; 62 } 63 64 inline void insert(char c) { 65 int f = c == '1', p = last, np = ++tot; 66 last = np; 67 len[np] = len[p] + 1; 68 while(p && !tr[p][f]) { 69 tr[p][f] = np; 70 p = fail[p]; 71 } 72 if(!p) { 73 fail[np] = 1; 74 } 75 else { 76 int Q = tr[p][f]; 77 if(len[Q] == len[p] + 1) { 78 fail[np] = Q; 79 } 80 else { 81 int nQ = ++tot; 82 len[nQ] = len[p] + 1; 83 fail[nQ] = fail[Q]; 84 fail[Q] = fail[np] = nQ; 85 memcpy(tr[nQ], tr[Q], sizeof(tr[Q])); 86 while(tr[p][f] == Q) { 87 tr[p][f] = nQ; 88 p = fail[p]; 89 } 90 } 91 } 92 return; 93 } 94 95 void DFS_1(int x) { 96 if(id[x]) { 97 st[x].insert(id[x]); 98 //printf("id %d = %d ", x, id[x]); 99 } 100 for(int i = e[x]; i; i = edge[i].nex) { 101 int y = edge[i].v; 102 DFS_1(y); 103 /// merge 104 if(st[x].size() < st[y].size()) { 105 std::swap(st[x], st[y]); 106 } 107 for(it = st[y].begin(); it != st[y].end(); it++) { 108 int a = *it; 109 it2 = st[x].lower_bound(a); 110 if(it2 != st[x].end()) { 111 int b = *it2; 112 /// node a b 113 if(a > b) std::swap(a, b); 114 node[++Cnt] = Node(a, b, len[x]); 115 //printf("Node : %d %d %d ", a, b, len[x]); 116 } 117 if(it2 != st[x].begin()) { 118 it2--; 119 int b = *it2; 120 /// node a b 121 if(a > b) std::swap(a, b); 122 node[++Cnt] = Node(a, b, len[x]); 123 //printf("Node : %d %d %d ", a, b, len[x]); 124 } 125 } 126 for(it = st[y].begin(); it != st[y].end(); it++) { 127 st[x].insert(*it); 128 } 129 st[y].clear(); 130 } 131 return; 132 } 133 134 int main() { 135 scanf("%d%d", &n, &m); 136 scanf("%s", str + 1); 137 for(int i = 1; i <= m; i++) { 138 scanf("%d%d", &ask[i].l, &ask[i].r); 139 ask[i].id = i; 140 } 141 for(int i = 1; i <= n; i++) { 142 insert(str[i]); 143 id[last] = i; 144 } 145 for(int i = 2; i <= tot; i++) { 146 add(fail[i], i); 147 } 148 DFS_1(1); 149 150 std::sort(ask + 1, ask + m + 1); 151 std::sort(node + 1, node + Cnt + 1); 152 153 int p1 = Cnt, p2 = m; 154 for(int i = n; i >= 1; i--) { 155 //printf("i = %d ", i); 156 while(node[p1].l == i) { 157 Add(node[p1].r, node[p1].id); 158 p1--; 159 } 160 while(ask[p2].l == i) { 161 Ans[ask[p2].id] = Ask(ask[p2].r); 162 p2--; 163 } 164 } 165 for(int i = 1; i <= m; i++) { 166 printf("%d ", Ans[i]); 167 } 168 return 0; 169 }