又是一道\(SAM\)維護(hù)\(endpos\)集合的題，我直接把CF700E的板子粘過(guò)來(lái)了QwQ
思路
如果我們有\([l,r]\)對(duì)應(yīng)的\(SAM\)，只需要在上面貪心就可以了。因?yàn)橐蟮氖亲值湫虮?span id="ze8trgl8bvbq" class="math inline">\(T\)大且最小的子串，我們從前到后讓盡可能多的位相等，如果再也無(wú)法相等了就從后往前找一位變大。
但是每次詢(xún)問(wèn)會(huì)給我們一個(gè)可行區(qū)間\([l,r]\)，而我們又顯然不能直接把對(duì)應(yīng)區(qū)間的\(SAM\)建出來(lái)，否則復(fù)雜度會(huì)\(GG\)。
仔細(xì)想一下，其實(shí)我們并不需要知道\([l,r]\)區(qū)間對(duì)應(yīng)的\(SAM\)，只要知道能否向某一個(gè)結(jié)點(diǎn)轉(zhuǎn)移就行了。這個(gè)我們可以用\(endpos\)集合來(lái)判斷。具體一下，就是當(dāng)前已經(jīng)考慮了\(i\)個(gè)字符且在結(jié)點(diǎn)\(u\)，現(xiàn)在需要判斷能否轉(zhuǎn)移到\(v\)，只需要判斷\(u\)是否有到\(v\)的轉(zhuǎn)移邊和\(v\)結(jié)點(diǎn)的\(endpos\)是否有元素在\([l+i-1,r]\)中就行了
\(endpos\)拿線(xiàn)段樹(shù)合并維護(hù)一下就行了（也可以用樹(shù)上主席樹(shù)搞一下）
其實(shí)本菜雞來(lái)學(xué)這個(gè)套路完全是為寫(xiě)你的名字做鋪墊的
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <string>
#include <vector>
#include <cmath>
#include <ctime>
#include <queue>
#include <map>
#include <set>using namespace std;#define IINF 0x3f3f3f3f3f3f3f3fLL
#define ull unsigned long long
#define pii pair<int, int>
#define uint unsigned int
#define mii map<int, int>
#define lbd lower_bound
#define ubd upper_bound
#define INF 0x3f3f3f3f
#define vi vector<int>
#define ll long long
#define mp make_pair
#define pb push_back#define N 200000
#define Q 200000int n, q, m;
char s[N+5], t[N+5], ans[N+5];struct SAM {int nxt[26][2*N+5], maxlen[2*N+5], link[2*N+5], tot, lst;int sumv[100*N+5], ch[2][100*N+5], root[2*N+5], nid;int node[N+5];vi G[2*N+5];void init() {tot = lst = 1;nid = 0;}void pushup(int o) {sumv[o] = sumv[ch[0][o]]+sumv[ch[1][o]];}void add(int &o, int l, int r, int x) {if(!o) o = ++nid;if(l == r) {sumv[o] = 1;return ;}int mid = (l+r)>>1;if(x <= mid) add(ch[0][o], l, mid, x);else add(ch[1][o], mid+1, r, x);pushup(o);}int merge(int o, int u, int l, int r) {if(!o || !u) return o|u;int v = ++nid;if(l == r) {sumv[v] = sumv[o]+sumv[u] ? 1 : 0;return v;}int mid = (l+r)>>1;ch[0][v] = merge(ch[0][o], ch[0][u], l, mid);ch[1][v] = merge(ch[1][o], ch[1][u], mid+1, r);pushup(v);return v;}int query(int o, int l, int r, int L, int R) {if(L > R || !o) return 0;if(L <= l && r <= R) return sumv[o];int ret = 0, mid = (l+r)>>1;if(L <= mid) ret += query(ch[0][o], l, mid, L, R);if(R > mid) ret += query(ch[1][o], mid+1, r, L, R);return ret;}void extend(int c) {int cur = ++tot;maxlen[cur] = maxlen[lst]+1;while(lst && !nxt[c][lst]) nxt[c][lst] = cur, lst = link[lst];if(!lst) link[cur] = 1;else {int p = lst, q = nxt[c][p];if(maxlen[q] == maxlen[p]+1) link[cur] = q;else {int clone = ++tot;maxlen[clone] = maxlen[p]+1;link[clone] = link[q], link[q] = link[cur] = clone;for(int i = 0; i < 26; ++i) nxt[i][clone] = nxt[i][q];while(p && nxt[c][p] == q) nxt[c][p] = clone, p = link[p];}}lst = cur;}void dfs(int u) {for(int i = 0, v; i < G[u].size(); ++i) {v = G[u][i];dfs(v);root[u] = merge(root[u], root[v], 1, n);}}void build() {init();for(int i = 1; i <= n; ++i) {add(root[tot+1], 1, n, i);extend(s[i]-'a');}for(int i = 2; i <= tot; ++i) G[link[i]].pb(i);dfs(1);}void search(int L, int R) {m = strlen(t+1);int u = 1, v, x;for(int i = 1; 1; ++i) {ans[i] = -1;for(int j = max(t[i]-'a'+1, 0); j < 26; ++j) {v = nxt[j][u];if(v && query(root[v], 1, n, L+i-1, R)) {ans[i] = j;break;}}v = nxt[max(t[i]-'a', 0)][u];x = i;if(i == m+1 || !v || !query(root[v], 1, n, L+i-1, R)) break;u = v;}while(x && ans[x] == -1) --x;if(!x) printf("-1\n");else {for(int j = 1; j < x; ++j) printf("%c", t[j]);printf("%c\n", ans[x]+'a');}}
}sam;int main() {scanf("%s%d", s+1, &q);n = strlen(s+1);sam.build();for(int i = 1, L, R; i <= q; ++i) {scanf("%d%d%s", &L, &R, t+1);sam.search(L, R);}return 0;
}
轉(zhuǎn)載于:https://www.cnblogs.com/dummyummy/p/10937663.html
《新程序員》：云原生和全面數(shù)字化實(shí)踐50位技術(shù)專(zhuān)家共同創(chuàng)作，文字、視頻、音頻交互閱讀
總結(jié)
以上是生活随笔為你收集整理的CF1037H Security——SAM+线段树合并的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。
如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。
