[HNOI 2019] JOJO

LOJ #3055.

首先考虑一个暴力的做法……我们很显然可以把一个二元组$(x, c)$看成一个字符,然后快乐地去跑 kpm kmp,在跳next的过程中,每个跳到的位置是$x$个$c$中的一段区间的border,在这个过程中计算一下$x$个$c$的位置中每一个的答案就行了

然而这样的话要是想搞操作2很显然就GG了,因为kmp那一套$O(n)$的复杂度是建立在复杂度均摊的基础上的。我们简单思考一下,好像暴力跳 next 的操作可以上线段树,因为决定一个位置可不可以成为border的决定性因素就是这一段的$c$的数量,就比如现在是在长度为$n$的串$s$后边加$x$个$c$,我们跳next跳到了第$p$个二元组,假如$p$后边有$y$个$c$,那么$s_{1}, s_{2}, \dots, s_{y}$的border就可以是这些前缀。那么建出来关于增删二元组的树形结构,然后在树上dfs,用主席树维护一下跳next的操作就可以了

另外主席树修改的时候要建新节点……因为这个WA了好几发……Orz

#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>

#define mp std::make_pair
#define X first
#define Y second
#define pb push_back
#define MAX_N 100010
#define MAX_M 10000
#define MOD 998244353
typedef std::pair<int, int> pii;

namespace SEG{
    #define mid ((l + r) >> 1)
    struct Node{
        Node *ls, *rs;
        int sum, val, tag;
        Node() : ls(NULL), rs(NULL), tag(-1){}
        void cov(int val, int l, int r){
            sum = 1ll * (r-l+1) * val % MOD;
            tag = val;
        }
        void push_down(int l, int r){
            if(tag == -1) return;
            ls = new Node(); rs = new Node(); 
            ls->cov(tag, l, mid);
            rs->cov(tag, mid + 1, r);
            tag = -1;
        }
        void push_up(){
            sum = ((ls?ls->sum:0) + (rs?rs->sum:0)) % MOD;
        }
    }*rt[MAX_N][26];
    void query(Node *v, int l, int r, int p, int &res, int &nxt){
        if(!v) return;
        if(r < p){
            res = (res + v->sum) % MOD;
            return;
        }
        if(l == r){
            res = (res + v->sum) % MOD;
            nxt = v->val;
            return;
        }
        v->push_down(l, r);
        query(v->ls, l, mid, p, res, nxt);
        if(p > mid) query(v->rs, mid + 1, r, p, res, nxt);
    }
    void modify(Node *&v, int l, int r, int p, int val1, int val2){
        Node *x = v; v = new Node();
        if(x) *v = *x;
        if(r < p){
            v->cov(val1, l, r);
            return;
        }
        if(l == r){
            v->cov(val1, l, r);
            v->val = val2;
            return;
        }
        v->push_down(l, r);
        modify(v->ls, l, mid, p, val1, val2);
        if(p > mid) modify(v->rs, mid + 1, r, p, val1, val2);
        v->push_up();
    }
    #undef mid
}
using SEG::rt;

int n, tot, pos[MAX_N], mx[MAX_N][26], ans[MAX_N], b[MAX_N], top;
pii val[MAX_N], a[MAX_N];
std::vector<int> to[MAX_N];

int calc(int x){
    return 1ll * x * (x + 1) / 2 % MOD;
}

void dfs(int v){
    int nxt = 0, x = val[v].X, c = val[v].Y;
    a[++top] = val[v]; b[top] = b[top-1] + x;
    if(top == 1) ans[v] = (ans[v] + calc(x - 1)) % MOD;
    else{
        ans[v] = (ans[v] + calc(std::min(x, mx[top][c]))) % MOD;
        SEG::query(rt[top][c], 1, MAX_M, x, ans[v], nxt);
        if(!nxt && val[v].X > a[1].X && val[v].Y == a[1].Y){
            nxt = 1;
            ans[v] = (ans[v] + 1ll * b[1] * std::max(0, x - mx[top][c]) % MOD) % MOD;
        }
    }
    mx[top][c] = std::max(mx[top][c], x);
    SEG::modify(rt[top][c], 1, MAX_M, x, b[top - 1], top);
    for(auto i: to[v]){
        ans[i] = ans[v];
        memcpy(rt[top+1], rt[nxt+1], sizeof(rt[top+1]));
        memcpy(mx[top+1], mx[nxt+1], sizeof(mx[top+1]));
        dfs(i);
    }
    top--;
}

int main(){
    int opt, x; char c;
    scanf("%d", &n);
    for(int i = 1; i <= n; i++){
        scanf("%d%d", &opt, &x);
        if(opt == 1){
            do c = getchar(); while(c < 'a' || c > 'z');
            to[pos[i-1]].pb(++tot);
            val[tot] = mp(x, c - 'a');
            pos[i] = tot;
        }else pos[i] = pos[x];
    }
    for(auto i: to[0]){
        memset(rt[1], 0, sizeof(rt[1]));
        memset(mx[1], 0, sizeof(mx[1]));
        dfs(i);
    }
    for(int i = 1; i <= n; i++) 
        printf("%d\n", ans[pos[i]]);
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注