辣鸡爆炸OJ又被卡了说好的修bug呢说好的新OJ呢哼我去loj交了

本题的正解是SA，但很显然可以用SAM搞过去（逃

首先字符集过大？我们可以考虑开map解决转移的问题。

然后思考一个点加入后对答案会有什么影响。一个点的对答案的贡献，就是他自己的最大表示范围减去他父亲的。因为更小的长度在之前都已经被表示过了。即使之后这个点被拆成了两个，那这两个点对答案的总贡献是不会变的。所以每次加完点，把贡献加到答案里即可。

代码：

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <map>
typedef long long ll;
#define REP(i, l, r) for(int i = (l); i <= (r); i ++)
struct Node {
  Node *fa;
  std::map<int, Node*> *ch;
  int len;
  Node() {
    fa = NULL;
    ch = new std::map<int, Node*>();
  }
  Node(int l) {
    fa = NULL;
    ch = new std::map<int, Node*>();
    len = l;
  }
  ~Node() {
    delete ch;
  }
};
Node *rt, *last;
void init() {
  rt = new Node(0);
  // rt -> tl = 1;
  last = rt;
}
ll ans = 0;
void insert(int c) {
  static int clk = 1;
  Node *np = new Node();
  np -> len = last -> len + 1;
  Node *p = last;
  while(p != NULL && p -> ch -> count(c) == 0) {
    p -> ch -> insert(std::make_pair(c, np));
    p = p -> fa;
  }
  if(p == NULL) {
    np -> fa = rt;
  } else {
    Node *q = (*(p -> ch -> find(c))).second;
    if(q -> len == p -> len + 1) {
      np -> fa = q;
    } else {
      Node *nq = new Node(p -> len + 1);
      nq -> fa = q -> fa;
      nq -> ch -> insert(q -> ch -> begin(), q -> ch -> end());
      // nq -> ch -> insert(std::make_pair(c, np));
      np -> fa = q -> fa = nq;
      while(p != NULL && ((*(p -> ch -> find(c))).second) == q) {
        p -> ch -> erase(p -> ch -> find(c));
        p -> ch -> insert(std::make_pair(c, nq));
        p = p -> fa;
      }
    }
  }
  last = np;
  ans += np -> len - np -> fa -> len;
}
 
int main() {
  int n; scanf("%d", &n);
  init();
  REP(i, 1, n) {
    int c; scanf("%d", &c);
    insert(c);
    printf("%lld\n", ans);
  }
  return 0;
}

• 相关文章
• 全局相关文章