「十二省联考 2019」字符串问题

知识点：SA，可持久化线段树，优化建图，DAGDP
原题面：Loj，Luogu

神笔出题人居然卡清空/jk
调一上午发现把昨天的 TLE 代码的邻接表换成 vector 就过了/jk
草草草草草

可怜金发小女孩

简述

(T) 组数据，每次给定一字符串 (S)。
在 (S) 中存在 (n_a) 个 A 类子串 ((la_i, ra_i))，(n_b) 个 B 类子串 ((lb_i,rb_i))。且存在 (m) 组支配关系，支配关系 ((x,y)) 表示第 (x) 个 A 类串支配第 (y) 个 B 类串。
要求构造一个目标串 (T)，满足：

  • (T) 由若干 A 类串拼接而成。
  • 对于分割中所有相邻的串，后一个串存在一个被前一个串支配的前缀。

求该目标串的最大长度，若目标串可以无限长输出 (-1)。
(1le Tle 100)，(n_a,n_b,|S|,mle 2 imes 10^5)。
6S，1G。

分析

首先建立图论模型，从每个 A 类子串向其支配的 B 串连边，从每个 B 串向以它为前缀的 A 串连边。A 串节点的权值为其长度，B 串节点权值为 0。
在图上 DP 求得最长路即为答案，若图中存在环则无解。
第一类边有 (m) 条，但第二类边数可以达到 (n_an_b) 级别，考虑优化建图。

对于某 A 串 ((la_i, ra_i))，它以 B 串 ((lb_j, rb_j)) 作为一个前缀的充要条件是 (operatorname{lcp}(S[la_i:n],S[lb_j:n]) ge rb_j-lb_j+1) 且 (ra_i - la_i + 1ge rb_j-lb_j+1)。
对于限制一，考虑求得 (S) 的 SA，对 (operatorname{height}) 建立 ST 表，可在 (sa) 上二分求得满足 (operatorname{lcp}ge rb_j-lb_j+1) 的区间的左右边界，满足条件的 A 串一定都在这段区间内。第二类边转化为区间连边问题。
此时不考虑限制二直接线段树优化建图，可以拿到 80 分的好成绩。

限制二实际上限定了 B 连边的对象的长度。
考虑将所有 A，B 串按长度递减排序，按长度递减枚举 A 串并依次加入可持久化线段树。
对于每一个 B 串，先找到使得 A 串长度大于其长度的最晚的历史版本，此时线段树上的所有 A 串长度都大于其长度，再向这棵线段树上的节点连边。

时间复杂度 (O((|S| + n_a + n_b)log n))，空间复杂度 (O(m + (|S| + n_a + n_b)log n))，不需要刻意卡常就能稳过。

看见上面轻描淡写的是不是觉得这题太傻逼了？以下是菜鸡 Lb 在代码实现上的小问题。

边数在极限数据下可以达到 (10^7) 级别，不注意空间大小和清空时的实现会被卡到 60。这个时空限制显然就是给选手乱搞的，数组往大了开就行。

在线段树优化建图中，实点会在建树操作中就与虚点连好边。本题的实点是代表 A，B 串的节点，在本题的可持久化线段树优化中，实点与虚点的连边发生在动态开点的插入过程中。
在新建节点时，需要将该节点连向上一个版本中对应位置的节点。
对于 A 串 ((la_i, ra_i))，它应该被插入到线段树中 (rk_{la_i}) 的位置，即叶节点 (rk_{la_i}) 与该实点相连。

(operatorname{height}_1) 没有意义。

注意二分时的初始值。

long long

函数传参顺序 是通过栈传递的，因此是从右向左的，下面这段代码会输出 cba：

int f(int a, int b, int c) {
  return 0;
}
int main() {
  return  f(printf("a"),printf("b"),printf("c"));
  return 0;
}

代码

//知识点：SA，可持久化线段树，优化建图，DAGDP
/*
By:Luckyblock
*/
#include <algorithm>
#include <cctype>
#include <cstdio>
#include <cstring>
#include <queue>
#define LL long long
const int kN = 2e5 + 10;
//=============================================================
struct Str {
  int l, r, lth, id;
} subs[kN << 1];
int node_num, n, na, nb, m, into[kN <<5];
int e_num, head[kN << 5], v[50 * kN], ne[50 * kN];
LL val[kN << 5], f[kN << 5];
char s[kN];
//=============================================================
inline int read() {
  int f = 1, w = 0;
  char ch = getchar();
  for (; !isdigit(ch); ch = getchar())
    if (ch == '-') f = -1;
  for (; isdigit(ch); ch = getchar()) {
    w = (w << 3) + (w << 1) + (ch ^ '0');
  }
  return f * w;
}
void Chkmax(LL &fir_, LL sec_) {
  if (sec_ > fir_) fir_ = sec_;
}
void Chkmin(int &fir_, int sec_) {
  if (sec_ < fir_) fir_ = sec_;
}
bool cmp(Str fir_, Str sec_) {
  if (fir_.lth != sec_.lth) return fir_.lth > sec_.lth;
  return fir_.id < sec_.id;
}
void Add(int u_, int v_) {
  v[++ e_num] = v_, ne[e_num] = head[u_], head[u_] = e_num;
  into[v_] ++;
}
namespace ST {
  int Minn[kN][21], Log2[kN];
  void MakeST(int *a_) {
    for (int i = 1; i <= n; ++ i) Minn[i][0] = a_[i];
    for (int i = 2; i <= n; ++ i) Log2[i] = Log2[i >> 1] + 1;
    for (int j = 1; j <= 20; ++ j) {
      for (int i = 1; i + (1 << j) - 1 <= n; ++ i) { //
        Minn[i][j] = std::min(Minn[i][j - 1], Minn[i + (1 << (j - 1))][j - 1]);
      }
    }
  }
  int Query(int l_, int r_) {
    int k = Log2[r_ - l_ + 1];
    return std::min(Minn[l_][k], Minn[r_ - (1 << k) + 1][k]);
  }
}
namespace SA {
  int sa[kN], rk[kN << 1];
  int oldrk[kN << 1], cnt[kN], id[kN];
  int height[kN];
  void SuffixSort() {
    int rknum = std::max(n, 300);
    memset(cnt, 0, sizeof (cnt));
    for (int i = 1; i <= n; ++ i) cnt[rk[i] = s[i]] ++;
    for (int i = 1; i <= rknum; ++ i) cnt[i] += cnt[i - 1];
    for (int i = n; i >= 1; -- i) sa[cnt[rk[i]] --] = i;
    
    for (int w = 1, p; w < n; w <<= 1) {
      p = 0;
      for (int i = n; i > n - w; -- i) id[++ p] = i;
      for (int i = 1; i <= n; ++ i) {
        if (sa[i] > w) id[++ p] = sa[i] - w;
      }
      
      memset(cnt, 0, sizeof (cnt));
      for (int i = 1; i <= n; ++ i) ++ cnt[rk[id[i]]];
      for (int i = 1; i <= rknum; ++ i) cnt[i] += cnt[i - 1];
      for (int i = n; i >= 1; -- i) sa[cnt[rk[id[i]]] --] = id[i];
      
      for (int i = 1; i <= n; ++ i) oldrk[i] = rk[i];
      rknum = 0;
      for (int i = 1; i <= n; ++ i) {
        rknum += (oldrk[sa[i]] == oldrk[sa[i - 1]] && 
                  oldrk[sa[i] + w] == oldrk[sa[i - 1] + w]) ^ 1;
        rk[sa[i]] = rknum;
      }
    }
  }
  void GetHeight() {
    for (int i = 1, k = 0; i <= n; ++ i) {
      if (rk[i] == 1) {
        k = 0;
      } else {
        if (k) -- k;
        int j = sa[rk[i] - 1];
        while (i + k <= n && j + k <= n && 
               s[i + k] == s[j + k]) {
          ++ k;
        }
      }
      height[rk[i]] = k;
    }
  }
  int Lcp(int x_, int y_) {
    if (x_ > y_) std::swap(x_, y_);
    return ST::Query(x_ + 1, y_);
  }
  void Init() {
    SuffixSort();
    GetHeight();
    ST::MakeST(SA::height);
  }
}
namespace Hjt {
  #define ls lson[now_]
  #define rs rson[now_]
  #define mid ((L_+R_)>>1)
  int root[kN], lson[kN << 5], rson[kN << 5];
  void Insert(int &now_, int pre_, int L_, int R_, int pos_, int id_) {
    now_ = ++ node_num;
    ls = lson[pre_], rs = rson[pre_];
    if (pre_) Add(now_, pre_);
    if (L_ == R_) {
      Add(now_, id_);
      return ;
    }
    if (pos_ <= mid) {
      Insert(ls, lson[pre_], L_, mid, pos_, id_);
      Add(now_, ls);
    } else {
      Insert(rs, rson[pre_], mid + 1, R_, pos_, id_);
      Add(now_, rs);
    }
  }
  void AddEdge(int now_, int L_, int R_, int l_, int r_, int id_) {
    if (! now_) return ;
    if (l_ <= L_ && R_ <= r_) {
      Add(id_, now_);
      return ;
    }
    if (l_ <= mid) AddEdge(ls, L_, mid, l_, r_, id_);
    if (r_ > mid) AddEdge(rs, mid + 1, R_, l_, r_, id_);
  }
  #undef ls
  #undef rs
  #undef mid
}
void Init() {
  e_num = 0;
  for (int i = 0; i <= node_num; ++ i) {
    head[i] = val[i] = into[i] = f[i] = 0;
  }
  
  scanf("%s", s + 1);
  n = strlen(s + 1);
  SA::Init();
  na = read();
  for (int i = 1; i <= na; ++ i) {
    int l_ = read(), r_ = read();
    subs[i] = (Str) {l_, r_, r_ - l_ + 1, i};
    val[i] = subs[i].lth;
  }
  nb = read();
  for (int i = 1; i <= nb; ++ i) {
    int l_ = read(), r_ = read();
    subs[na + i] = (Str) {l_, r_, r_ - l_ + 1, na + i};
  }
  m = read();
  for (int i = 1; i <= m; ++ i) {
    int u_ = read(), v_ = read();
    Add(u_, v_ + na); //Add(read(), read()+na) 会倒着读
  }
  node_num = na + nb;
}
bool Check(int x_, int y_, int lth_) {
  return SA::Lcp(x_, y_) >= lth_;
}
void AddEdgeB(int id_, int now_) {
  int pos = SA::rk[subs[id_].l], l_ = pos, r_ = pos; //l_，r_ 初始值
  for (int l = 1, r = pos - 1; l <= r; ) {
    int mid = (l + r) >> 1;
    if (Check(mid, pos, subs[id_].lth)) {
      r = mid - 1;
      l_ = mid;
    } else {
      l = mid + 1;
    }
  }
  for (int l = pos + 1, r = n; l <= r; ) {
    int mid = (l + r) >> 1;
    if (Check(pos, mid, subs[id_].lth)) {
      l = mid + 1;
      r_ = mid;
    } else {
      r = mid - 1; 
    }
  }
  Hjt::AddEdge(Hjt::root[now_], 1, n, l_, r_, subs[id_].id);
}
void Build() {
  node_num = na + nb;
  std::sort(subs + 1, subs + na + nb + 1, cmp);
  for (int now = 0, i = 1; i <= na + nb; ++ i) {
    if (subs[i].id > na) {
      AddEdgeB(i, now);
      continue;
    }
    ++ now;
    Hjt::Insert(Hjt::root[now], Hjt::root[now - 1], 1, n, SA::rk[subs[i].l], 
                subs[i].id);
  }
}
void TopSort() {
  std::queue <int> q;
  for (int i = 1; i <= node_num; ++ i) {
    if (!into[i]) {
      f[i] = val[i];
      q.push(i);
    }
  }
  while (! q.empty()) {
    int u_ = q.front(); q.pop();
    for (int i = head[u_]; i; i = ne[i]) {
      int v_ = v[i];
      Chkmax(f[v_], f[u_] + val[v_]);
      -- into[v_];
      if (!into[v_]) q.push(v_);
    }
  }
  LL ans = 0;
  for (int i = 1; i <= node_num; ++ i) {
    Chkmax(ans, f[i]);
    if (into[i]) {
      printf("-1
");
      return ;
    }
  }
  printf("%lld
", ans);
}
//=============================================================
int main() {
  int T = read();
  while (T --) {
    Init();
    Build();
    TopSort();
  }
  return 0;
}
【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/luckyblock/p/14262712.html