题解给定一个长度为$n$的排列，有两种操作，分别为区间取$mex$与交换两个相邻位置的元素。 考虑到所给序列是一个排列，所以$0~n-1$的每个元素要么在查询区间中出现，要么在区间外出现，所以区间内最小未出现的元素即区间外的最小元素（当区间包含整个序列时，答案应为$n$，没有在区间外出现，这种情况特判即可）。记录前缀后缀最小值，查询时答案即为$min(mnl[l-1],mnr[r+1])$。当交换相邻元素时，只有这两个相邻位置的前缀后缀最小值可能会发生改变。所以整体复杂度为$O(n+Q)$ （由 ...

题解若后继状态存在偏序关系（即如果状态$S_1$可以转移到$S_2$，状态$S_2$可以转移到状态$S_3$时，那么$S_1$一定可以转移到$S_3$），假设$SG(S_2)=x$，那么所有$0x-1$的$SG$值都在$S_2$的后继状态中出现过，又因为存在偏序关系，$S_1$的后继状态包含$S_2$的所有后继状态。所以$0x-1$和$x$的$SG$值一定在$S_1$的后继状态出现过，所以$SG(S_1)>x$。又因为$SG$是未在后继状态中出现过的最小自然数，所以$SG(S_1)=max ...

题解给定一个长度为$n(n \leq 10^6)$的字符串$S$，求其中的回文套娃个数。回文套娃定义为两个序列$l_1<l_2<…<l_k$和$r_1>r_2>…>r_k$，其中每个$S[l_i:r_i]$均为回文串。 在回文树中，每个节点$x$代表的字符串有两个前驱，第一个是删除第一个和最后一个字符得到的父亲节点$fa(x)$，第二个是最长前/后缀所代表的节点$f(x)$。 对于每个回文串$s[l:r]$，其包含的回文子串$s[x:y]$都可以通过如下的方式 ...

题解维护一个序列$a$，支持修改某个元素的值和寻找最小的满足$\sum_{i=1}^t a_i >= k$的$t$。（如果把该序列下标看成值域，值看作出现的次数，则第二种操作表示找第$k$大元素） 显然线段树上二分可以做到$O(logn)$的查询修改复杂度。 但是树状数组同样存在一种类似数位$DP$的方式，将修改操作做到一个$log$的复杂度。（时间空间上更优秀） 考虑树状数组的定义方式，第$i$位$Bit[i] = a[i-2^k+1] + a[i-2^k+2] + … + a[i]$（ ...

题解字符串的半前缀即前缀删除一个子串后得到的字符串，可以用$s[1…i]+s[j…k]$表示。 问题即给定一个长度为$n(n \leq 10^6)$的字符串，求其半前缀的个数。 \textbf{对于这种本质不同的字符串计数问题，通常都是将某个串在它第一次或最后一次出现时统计。} 本题中，如果将每个字符串在第一次出现的前缀中（即尽可能缩短用到的前缀长度），那么看起来就不太能做。但是如果将每一个串在最后一次出现的前缀中统计，就会非常简单：对于一个串，假设它可以表示为 $s[1…i]+s[j…k]$ ...

题解$f(n)=af(n-1)+bf(n-2),f(1)=c,f(2)=d$ 求$f(n) \ mod \ p$的最小循环节长度。 当$c$是模$p$的二次剩余时，枚举$n=p-1$的因子。 当$c$是模$p$的二次非剩余时，枚举$n=(p+1)(p-1)$的因子。 找到最小的因子$ans$，使得 $\begin{pmatrix} a & b \ 1 & 0 \end{pmatrix}^{ans}=\begin{pmatrix} 1 & 0 \ 0 & 1 \en ...

题解求满足以下条件的$(x,y)$整数对数：（适用高位到低位$DP$） $x∈[0,A],y∈[0,B]$ $x xor y≤W$ 求满足以下条件的$(x,y)$整数对数：（适用低位到高位$DP$） $x∈[0,A],y∈[0,B]$ $x xor y ≤ W$ $x - y ≤ K$ 大多数情况下，从高位到低位进行$DP$都更为便捷。但第二道例题中有加法（也可以看作减法），也就是有进位（也可以看作有借位），此时从低位到高位显然更便捷。 对于第二道例题：设$f[bit][xA] ...

因为0的个数和1的个数要保持一致，所以沿途要记录0的个数与1的个数的差，每个差值对应都要一个状态，而这个值可能是无限的，所以无法用有穷状态机表示。（D中01和10最多差1，所以是正则的）

题解定义序列$a_{1…n}$的权值为$\sum a_i$ 求满足$l_i \leq a_i \leq r_i$且$a_i$单调不降的所有序列$a_{1…n}$的权值和。 考虑最高位，那么一定存在一个$k$，使得$a[1…k]$最高位是$0$，$a[k+1…n]$最高位是$1$，那么可以分成两个子区间去做。 设$f[i][L][R][LIML][LIMR]$表示：在$i+1…60$位已经定下来的情况下（此时$a[L…R]$的$i+1..60$位的值一样），区间$[L…R]$只考虑$1…i$位的答 ...