首页 > 其他分享 >p4137-solution

p4137-solution

时间:2024-03-01 09:16:15浏览次数:31  
标签:下标 min solution 权值 mathcal p4137

P4137 Solution

link

考虑建主席树:权值线段树的叶子维护这个权值最后出现的下标,push_up 的时候取 \(\min\)。

这样一个区间的 \(\min\) 小于 \(k\) 意味着有一个权值最后出现的下标小于 \(k\),也就是说 \(k\) 后面没有出现这个权值。

也就是说 mex 就在这个区间内。

这样询问的时候就可以直接在 \(r\) 的权值树内根据 \(l\) 进行二分。

时空均为 \(\mathcal O(n\log n)\),也可以改成扫描线维护一棵权值树,空间降到 \(\mathcal O(n)\)。

标签:下标,min,solution,权值,mathcal,p4137
From: https://www.cnblogs.com/iorit/p/18046109

相关文章

  • p3990-solution
    P3990Solutionlink一次只能跳一步的情况下:\(dp_{i,j}=dp_{i-1,j-1}+dp_{i-1,j}+dp_{i-1,j+1}\)接下来考虑能跳奇数步:你发现跳\(3\)步相当于先跳一个奇数\(1\)再跳一个\(2\),跳\(5\)步相当于先跳一个奇数\(3\)再跳一个\(2\)也就是说能够一步跳到\((i,j)\)的一定能......
  • p3773-solution
    P3773Solutionlink\[\binomnm\bmod2=\binom{n\bmod2}{m\bmod2}\binom{n/2}{m/2}\bmod2\]我们要让\(\binomnm\bmod2\)不为\(0\),也就是让右式的两项均不为\(0\)。考虑\(\binom{n\bmod2}{m\bmod2}\):\(n\bmod2\)和\(m\bmod2\)的取值要么是\(0\)要么是\(1\)......
  • p3768-solution
    P3768Solutionlink\(\begin{aligned}\sum_{i=1}^n\sum_{j=1}^nij\gcd(i,j)&=\sum_{d=1}^n\sum_{i=1}^n\sum_{j=1}^nijd[\gcd(i,j)=d]\\&=\sum_{d=1}^nd^3\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}\sum_{j=1}^{\lfloor\frac{n}{d}\rfloor}ij[......
  • p3435-solution
    P3435Solutionlink画个图:显然四个黄色部分是相等的。也就是说,黄色部分是A的一个border。根据题目,周期的长度也就是Q的长度,也就是A的长度减去它的某个border的长度。现在要求这个最大,由于A的长度固定,要求的也就是A的最小border长度。根据KMP求出来的nxt......
  • p3426-solution
    P3426Solutionlink考虑dp。设\(dp_i\)表示至\(i\)的字符串的答案。KMP求出nxt数组,那么显然\(dp_i\)要么等于\(i\)要么等于\(dp_{nxt_i}\)。什么时候\(dp_i\)等于\(dp_{nxt_i}\)呢?这时这个字符串一定由一个与\(nxt_i\)有相同\(dp\)值的前缀再印上一个bo......
  • p3306-solution
    P3306Solutionlink\(x_{i+1}\equiva\timesx_i+b\pmodp\)\(x_{i+1}\equiva(ax_{i-1}+b)+b\pmodp\)\(x_{i+1}\equiva(a(ax_{i-2}+b)+b)+b\pmodp\)\(...\)\(\displaystylex_{i+1}\equiva^ix_1+b\sum\limits_{j=0}^{i-1}a^j\pmodp\)即......
  • p3214-solution
    P3214Solutionlink为了方便,我们求有序的答案最后再除掉\(m!\)。题目的限制包括:每种元素总共出现偶数次不存在相同的两个集合没有空集考虑偶数的限制,你发现每个集合中元素出现次数要么\(0\)要么\(1\)。于是如果你确定了前\(m-1\)个集合,最后一个集合会被唯一......
  • p2791-solution
    P2791Solutionlink给你\(N,M,S,L\),\(S\)组询问,每次给出\(n,m,k\),表示有\(m\)个\(1\)和\(n-m\)个\(0\),求随机选出\(k\)个数的和的\(L\)次幂的期望,模数\(998244353\)。\(S\le200,L\le2\times10^5,M\leN\le2\times10^7\),每次询问的\(n,m,k\)满足\(m,k\len......
  • p2150-solution
    P2150Solutionlink首先两人选的数两两互质相当于两人的质因数集合无交。先考虑\(n\le30\):由于\(30\)内的质因只有\(10\)个,我们考虑状压\(dp\)。设\(dp_{i,S1,S2}\)表示考虑到第\(i\)个数,G选了质因数集合\(S1\),W选了质因数集合\(S2\)的方案数。刷表转移:\[d......
  • p1587-solution
    P1587Solutionlink给你\(n,m,k\),求满足\(1\lex\len,1\ley\lem\)且最简分数\(\dfracxy\)是\(k\)进制下纯循环小数的二元组\((x,y)\)个数。考虑纯循环小数的性质:我们知道纯循环小数的小数部分去除一个循环节后与原数的循环节相等,也就是\[\fracxy-\left\lfloor......