CF1037H Security——SAM+线段树合并

又是一道\(SAM\)维护\(endpos\)集合的题，我直接把的板子粘过来了QwQ

思路

如果我们有\([l,r]\)对应的\(SAM\)，只需要在上面贪心就可以了。因为要求的是字典序比\(T\)大且最小的子串，我们从前到后让尽可能多的位相等，如果再也无法相等了就从后往前找一位变大。
但是每次询问会给我们一个可行区间\([l,r]\)，而我们又显然不能直接把对应区间的\(SAM\)建出来，否则复杂度会\(GG\)。
仔细想一下，其实我们并不需要知道\([l,r]\)区间对应的\(SAM\)，只要知道能否向某一个结点转移就行了。这个我们可以用\(endpos\)集合来判断。具体一下，就是当前已经考虑了\(i\)个字符且在结点\(u\)，现在需要判断能否转移到\(v\)，只需要判断\(u\)是否有到\(v\)的转移边和\(v\)结点的\(endpos\)是否有元素在\([l+i-1,r]\)中就行了
\(endpos\)拿线段树合并维护一下就行了（也可以用树上主席树搞一下）
其实本菜鸡来学这个套路完全是为写你的名字做铺垫的

#include 
#include  
#include   
#include   
#include    
#include    
#include    
#include     
#include     
#include     
#include       
#include       

using namespace std;

#define IINF 0x3f3f3f3f3f3f3f3fLL
#define ull unsigned long long
#define pii pair
#define uint unsigned int
#define mii map
#define lbd lower_bound
#define ubd upper_bound
#define INF 0x3f3f3f3f
#define vi vector
#define ll long long
#define mp make_pair
#define pb push_back

#define N 200000
#define Q 200000

int 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;
}
字符串——后缀自动机SAM数据结构——线段树合并后缀自动机SAM线段树合并

相关

「NOI2020」命运（树形DP+线段树合并）

【线段树合并】【P2824】 [HEOI2016/TJOI2016]排序

[学习笔记] 线段树合并

P3521 [POI2011]ROT-Tree Rotations（线段树合并）

CF1276F-Asterisk Substrings【SAM,线段树合并】

标签