某島

… : "…アッカリ~ン . .. . " .. .
March 21, 2020

Luogu P4070 [SDOI2016]生成魔咒

Luogu 傳送門 | LOJ 傳送門

每次加上高度即可。中間的過程不會影響。


const int N = int(1e6) + 9;

namespace SAM{
    
    map<int, int> trans[N]; int par[N],len[N],tail,tot; LL z;
    char buf[N];
    
    int new_node(){
        //RST(trans[tot]);
        trans[tot].clear();
        return tot++;
    }
    int new_node(int u){
        //CPY(trans[tot],trans[u]),par[tot]=par[u];
        trans[tot] = trans[u]; par[tot] = par[u];
        return tot++;
    }
#define v trans[u]
#define p par[u]
#define pp par[uu]
    
    int h(int u) {
        return len[u] - len[p];
    }
    
    int Ext(int c){
        int u = tail, uu = new_node(); len[uu] = len[u] + 1;
        while (u && !v) v = uu, u = p;
        if (!u && !v) v = uu, pp = 0;
        else{
            if (len[v] == len[u] + 1) pp = v;
            else{
                int _v = v, vv = new_node(_v); len[vv] = len[u] + 1;
                par[_v] = pp = vv; while (v == _v) v = vv, u = p;
            }
        }
        
        z += h(uu);
        
        return tail = uu;
    }
    
    int adj[N][26];
    
    void Init(){
        tail = tot = 0; new_node(); z = 0; Rush {
            Ext(RD());
            cout << z << endl;
        }
    }
    
} using namespace SAM;

int main(){
    
#ifndef ONLINE_JUDGE
    //freopen("in.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);
#endif
    
    Init();
    
}