牛客挑战赛 76

mgj 上次打牛客挑战赛也生着病，以后不打了（
食堂全是军训的害我迟到了 3min（

B 转化成作为子串和子序列都恰好出现一次，然后一直想上自动机。。。
D 以为下标也有区间限制做了半天。。。
一看剩下的全是数数，自闭了。C 可做但没时间了

B 一开始不会做，D 被卡常，罚时爆了，三题从 17 到 45，我 44。险些掉分，感觉上 2400/红名 还是比较困难的

B - Substring Not Subsequence

考虑一个必要条件：若子串 \(s[l:r]\) 合法，那么 \(l\) 之前一定没有字符 \(s[l]\)，\(r\) 之后一定没有字符 \(s[r]\)，否则可以调整成不连续的子序列

事实上这也是充分条件。这样的串最多有 \(26^2\) 个

C - 序列

key observation：类似括号序列，有且仅有一种 \(0011\) 的匹配方式，使得每次删掉的都是一个匹配

可以用栈求出匹配方式，问题变为求删空的排列数

任意排列有 \(n!\) 种方案。删 \((a_i,b_i,c_i,d_i)\) 需要先把中间删空，即排列中 \(i\) 是这 \(\frac{d_i-a_i+1}{4}\) 个种的最后一个，答案需要除掉 \(\frac{d_i-a_i+1}{4}\)

code

D - 数据结构

赛时做法

每次操作后区间内所有数同奇偶，考虑均摊

下标没有限制，直接按奇偶性分别维护有序数集

code

std

key observation：区间 \(-1\) 后不改变相对大小

排序后用线段树维护。线段树二分定位区间 \([l,r]\)（需要维护最值），继续递归到只有奇/偶数的结点进行修改（需要维护奇/偶数个数，打 \(-1\) 标记）

每次操作新增 \(O(\log n)\) 个有奇有偶的结点。时间复杂度 \(O(q\log n)\)