一些数据结构维护手法，好题

[蓝桥杯 2022 国 AC] 替换字符

发现字母的变换有复合性质，可以用线段树维护一个 \(lazy[26]\) 数组表示这个区间的每一个字母变成了那一个。

当两个标记合并的时候有：\(nwlazy[i]=blazy[alazy[i]]\)，相当于标记信息的复合。

One Occurrence

对于这种某个数只出现一次的经典题，考虑一个经典的 trick，我们维护一个 \(pre[i]\) 表示 \(a_i\) 上一次出现的位置，然后 \(suf[i]\) 表示 \(a_i\) 下一次出现的位置。

我们发现若 \(a_i\) 在区间 \([l,r]\) 中只出现了一次 \(\iff pre[i]<l \ or\ suf[i]>r\)。

我们发现这样我们不好处理，因为多了个 \(suf\) 的情况，我们不难想到如果能固定 \(r\)，是不是问题就好解决了。

利用扫描线思想，我们把询问离线下来，扫 \(r\), 然后去维护 \(l\) 的答案。

我们用一个线段树，维护区间 \(pre[i]\) 的最小值。

对于扫到某个位置 \(r\)，我们把 \(r\) 这个位置在线段树中的值改为 \(pre[r]\)，然后注意此时还要把 \(pre[r]\) 位置的值改为 \(INF\)，因为此时如果 \(pre[r]\) 位置的数的 \(pre\) 是满足条件的，但又因为在 \(r\) 处还出现了一次，所以此时他在所有以 \(r\) 为右端点的询问中，一定是不合法的，所以我们要改为 \(INF\)。

A Simple Task

题目要求我们对区间的所有字母排序（升序或者降序），我们不难发现其实本质就是按 \(26\) 个字母的顺序依次给区间赋值。

每次区间修改就是遍历 \(26\) 个字母，在其对应的线段树上修改。

所以我们可以用线段树维护每种字母的出现次数。

故我们开 \(26\) 个线段树，每颗线段树维护对应字母的出现次数，然后支持区间赋值即可。