来个无脑点的做法,考虑分块。每个块维护 li,ri,fil_i,r_i,f_ili,ri,fi 表示 iii 在块中第一次出现的位置和最后一次出现的位置,还有块内包含 iii 的连续段长度的最大值,每个点再维护 Li,RiL_i,R_iLi,Ri 表示 iii 往左往右在相同块内的连续段长度,每次修改就直接重构整个块即可。
考虑一次询问,只会出现 O(n)\mathcal O(\sqrt n)O(n) 个跨越两个块的连续段,直接从前往后扫每个块,利用上面维护的那些东西不难求出所有跨越多个块的连续段的长度与是否含有 xxx,只在一个块内的答案就是 fxf_xfx,散块就直接暴力加入即可。时间复杂度 O(nn)\mathcal O(n\sqrt n)O(nn),有点卡常。
Using your HFOJ universal account