串串超人与山姆大叔

串串超人与山姆大叔

完成度，(6 of 8) and (0 of 7)。。。。。。

working on

---

CF547E 题意 给你n个字符串，问一个字符串在一个区间出现的次数。

safe

较为容易的一道题，我的做法是先建出广义SAM,对于一个串对应一个节点。

那就按时间在广义SAM上加串（给中止点+1），然后一个询问拆成前缀减前缀即可。

复杂度 \(\mathcal{O(n\log n)}\)。

---

bad

CF504 题意给你一颗树，树上节点有字符，询问是对两个链询问 lcp长度。

挺屑的一道题，，，

一眼二分哈希，但是直接二分/倍增的话k级祖先不是很好处理。

那么我们就要请出解决链上问题的利器，链剖分。

重链剖分后，如果两个点在一条重链上那么会可以通过预处理 \(O(n)-O(1)\) 求出k级祖先。

现在链被分为 \(O(\log n)\) 个区间，我们对两组区间求lcp。

这就有一个灵魂的问题了。。这个像two pointers 的问题怎么实现 ，我一直不是很会这个东西的实现，，包括联合省选的D1T2。

解决办法是我们从左往右扫每次，每次左端点是对齐的，我们只需要选较小的右端点即可。

实现类似two pointers ，注意将一些功能函数化会事半功倍。

部分代码，供参考。

inline int up(int x,int k){
    return p[top[x]][dep[x]-k];
}
inline int down(int x,int k){
    return p[top[x]][dep[x]+k];
}
inline int nxt(int ori,int x,int k){
    if(lca(ori,x)!=x) return down(x,k);
    return up(x,k);
}

void app(int &i,int &l,int &r,const vii &a){
    i++;if(i<a.size()) l=a[i].first,r=a[i].second;
}
inline int ext(const vii &a,const vii &b){
    while(i<a.size()&&j<b.size()){
        int d1=dis(oa,r1),d2=dis(ob,r2),d=dis(oa,l1);
        int k=min(d1,d2)-d;
        if(w(l1,nxt(oa,l1,k))==w(l2,nxt(ob,l2,k))){
            if(d1==d2) app(i,l1,r1,a),app(j,l2,r2,b);
            else if(d1<d2){
                app(i,l1,r1,a);
                l2=nxt(ob,l2,k+1);
            }
            else {
                app(j,l2,r2,b);
                l1=nxt(oa,l1,k+1);
            }
        }
    }
}

这个要维护4个点因为实在树上，尽管左端点rank一样但实际上可能不一样。

这里的 \(d1-d\) 和 \(d2-d\) 代表的是rank。

虽然但是，他还是好屑呀。

---

Euclid

CF204E 题意，给n个字符串，问每一个字符串有多少子串在最少k个串中出现。

最开始不是很会，在几处都卡住了.......以为只能SA。。。。。。

首先我是山姆大叔的忠实信徒。

先建出广义SAM，考虑现在只有 \(O(\sum|s|)\) 个等价类了，我们要对每个等价类看他的出现次数。

这本质上我们要覆盖一棵“导出子树”，大概就是给出几个关键点，覆盖这个虚树。

这个比较厉害的树上差分出现了，首先任意dfs出来一个顺序。

按dfs序排序，然后现在整棵树的权值就是

\(w(1)+\sum_{i\ge 2} w(i)-w(lca(i,i-1))\)。这样的，为啥对？我们实际上维护的是树的最右链。这样的话那一定对了。

这样可以让我们在 \(O(|s|\log|s|)\) 的复杂度内加入贡献。

剩下的统计也是类似的。

---

wait for solving

CF1012D

---

safe

String Problem 题意给你一个串对于每一个前缀求出前缀的字典序最大子串。

首先你一定一定要发现答案是一个前缀的后缀。你发现就是对前 \(i\) 个后缀排序，直接求出后缀数组即可。

山姆大叔呜呜呜。

---

safe

Suffix Automaton 也是比较简单的。题意吧所有子串先按len排，再按字典序拍问rank=i的串是啥。

我的做法是倒着SAM求出后缀树。这样可以dfs出来等价类的大小顺序。

然后你考虑按时间枚举长度，你会发现节点出现的时间是一个区间，这样也是可以化成两个操作。

然后那线段树维护一下，在上面二分即可。

---

safe

Substrings in a String 题意是你要支持修改一个字符，和查询一个串在 \(s[l,r]\) 出现次数。

前几天模拟赛的题提示我们字符串问题由于字符集大小有限，可以使用bitset 维护每个字符出现的位置，通过&和<<匹配给定串。

这样做就可以做到 \(\mathcal{O(\frac{n^2}{w})}\)。

---

Euclid

CF700E

waiting for update