人之初 性本恶

懵逼的 题目

BZOJ1396

BZOJ 2865

扯淡的 题解

嗯…我会求每个点的$|endpos|$! 对于每个点$i$, 我们发现我们只需要把

  • $[1, maxlen_i - minlen_i - 1]$中的点$j$和$maxlen_i - j + 1$取$\min$(感谢gayge拉住了我告诉我这个东西不用写区间修改等差数列…)
  • $[maxlen_i - minlen_i, wz_i]$中的点和$maxlen_i - minlen_i + 1$取$\min$就完事了

沙茶的 代码

2865那题卡SAM? 我估计只用一个线段树并且把线段树改成不记录左右端点的版本应该就可以了

/**************************************************************
    Problem: 1396
    User: Cansult
    Language: C++
    Result: Accepted
    Time:1384 ms
    Memory:37660 kb
****************************************************************/


#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#define LL long long
#define MAXN (100000 + 5)
#define INF (0X7FFFFFFF)
#define MAXZ (26)
#define LS(dq) ((dq) << 1)
#define RS(dq) (((dq) << 1) | 1)
using namespace std;
struct xds {
    struct node {
        int le, ri, zh;
    } b[MAXN << 2];
    void js(int dq, int le, int ri) {
        b[dq].zh = INF, b[dq].le = le, b[dq].ri = ri;
        if (le == ri) return ;
        int mi = (le + ri) >> 1;
        js(LS(dq), le, mi), js(RS(dq), mi + 1, ri);
    }
    int cx(int dq, int wz) {
        int re = b[dq].zh;
        if (b[dq].le == b[dq].ri) return re;
        int mi = (b[dq].le + b[dq].ri) >> 1;
        if (wz <= mi) return min(cx(LS(dq), wz), re);
        else return min(cx(RS(dq), wz), re);
    }
    void xg(int dq, int le, int ri, int zh) {
        if (le > ri) return ;
        if (b[dq].le == le && b[dq].ri == ri) {
            b[dq].zh = min(b[dq].zh, zh);
            return ;
        }
        int mi = (b[dq].le + b[dq].ri) >> 1;
        if (ri <= mi) xg(LS(dq), le, ri, zh);
        else if (le > mi) xg(RS(dq), le, ri, zh);
        else xg(LS(dq), le, mi, zh), xg(RS(dq), mi + 1, ri, zh);
    }
};
struct SAM {
    struct node {
        int maxlen, suff_link, trans[MAXZ], size, wz;
        node (int maxlen = 0): maxlen(maxlen), suff_link(0), size(0) { memset(trans, 0, sizeof(trans)); }
    } b[MAXN << 1];
    struct edg {
        int to, next;
    } tb[MAXN << 1];
    int s, last, cntb, g[MAXN << 1], cntt, n;
    xds qwq, qaq;
    void init() { s = last = cntb = 1, n = 0; }
    void adn(int from, int to) {
        tb[++cntt].next = g[from];
        tb[cntt].to = to;
        g[from] = cntt;
    }
    void ins(char xc) {
        int y = xc - 'a', dq = ++cntb, dql = last;
        b[dq] = node(b[dql].maxlen + 1);
        for (; dql && !b[dql].trans[y]; dql = b[dql].suff_link) b[dql].trans[y] = dq;
        if (!dql) b[dq].suff_link = s;
        else if (b[dql].maxlen + 1 == b[b[dql].trans[y]].maxlen) b[dq].suff_link = b[dql].trans[y];
        else {
            int c = ++cntb, dqd = b[dql].trans[y];
            b[c] = node(b[dql].maxlen + 1);
            b[c].suff_link = b[dqd].suff_link;
            b[dq].suff_link = b[dqd].suff_link = c;
            for (int i = 0; i < MAXZ; i++) b[c].trans[i] = b[dqd].trans[i];
            for (; dql && b[dql].trans[y] == dqd; dql = b[dql].suff_link) b[dql].trans[y] = c;
        }
        b[dq].wz = ++n;
        b[last = dq].size = 1;
    }
    int dfs(int dq) {
        for (int i = g[dq]; i; i = tb[i].next) b[dq].size += dfs(tb[i].to);
        return b[dq].size;
    }
    void solve() {
        for (int i = 2; i <= cntb; i++) adn(b[i].suff_link, i);
        dfs(1);
        qwq.js(1, 1, n), qaq.js(1, 1, n); 
        for (int i = 1; i <= cntb; i++)
            if (b[i].size == 1) {
                qaq.xg(1, 1, b[i].wz - b[b[i].suff_link].maxlen, b[i].maxlen + 1);
                qwq.xg(1, b[i].wz - b[b[i].suff_link].maxlen + 1, b[i].wz, b[b[i].suff_link].maxlen + 1);
            }
        for (int i = 1; i <= n; i++)
            printf("%d\n", min(qwq.cx(1, i), qaq.cx(1, i) - i));
    }
} refun;
int n;
char s[MAXN];
int main() {
    scanf("%s", s);
    n = strlen(s);
    refun.init();
    for (int i = 0; i < n; i++)
        refun.ins(s[i]);
    refun.solve();
    return 0;
}

By 准备退役旅游的 Cansult