首页 > 其他分享 >cf1621g-solution

cf1621g-solution

时间:2024-02-28 13:58:14浏览次数:212  
标签:suf cf1621g 后缀 个数 solution lst 序列 右侧

CF1621G Solution

link

考虑对每个位置 \(i\) 作为 \(i_j\) 时计算贡献。\(i\) 对一次答案有贡献当且仅当:

  • 设其子序列内最右端的位置为 \(r\),则要满足 \(r\) 右侧存在一个数大于 \(a_{i}\)。

  • 即,设 \(lst_i\) 表示整个序列最右侧的大于 \(a_i\) 的数,要满足 \(lst_i>r\)。

现在,对于每个 \(i\) 我们要求包含它且右端点小于 \(lst_i\) 的上升子序列个数。

\(i\) 左侧包含 \(i\) 的子序列个数容易计算,那么现在求右侧的子序列个数,乘起来就好了。

右侧要满足:以 \(i\) 开头,右端点小于 \(r=lst_i\)。这个可能有点麻烦,我们用总的减去不合法的,即先求出 \(i\) 右侧包含 \(i\) 的所有子序列个数,减去 \(i\) 开头 \(r\) 结尾的上升子序列个数。(右端点不可能大于 \(r\),因为 \(r\) 之后的都小于 \(a_i\))

对于所有的 \(i\) 我们可以得到若干个 \(r\),这些 \(r\) 恰好是序列的后缀最大值位置。设 \(suf_i\) 表示从后往前第 \(i\) 个后缀最大值位置。

那么对于一个后缀最大值位置 \(r=suf_i\),满足 \(lst_i=r\) 的所有 \(i\) 需要满足:\(a_i\in[a_{suf_{i-1}},a_{suf_i})\)。

这样把所有 \(a\) 划分为若干个互不相交的区间。由于以 \(i\) 开头以 \(r\) 结尾的上升子序列中间的数一定在 \([a_i,a_r]\) 中,我们枚举每个后缀最大值位置,把满足 \(a_i\in[a_{suf_{i-1}},a_{suf_i})\) 的所有 \(i\) 拉出来,求一遍上升子序列即可。

复杂度 \(\mathcal O(n\log n)\)。

标签:suf,cf1621g,后缀,个数,solution,lst,序列,右侧
From: https://www.cnblogs.com/iorit/p/18040129

相关文章

  • cf1606e-solution
    CF1606ESolutionlink考虑dp。注意到这个题造成的伤害与剩余人数有关,每次消灭的人数又与剩余人的血量最大值有关:设\(dp_{i,j}\)表示剩下\(i\)个人中血量最大值为\(j\)的方案数。显然当\(i-1>=j\)时一次伤害就可以杀光所有人,于是这时\(dp_{i,j}=j^i-(j-1)^i\)(只需让......
  • cf1599j-solution
    CF1599JSolutionlink题意:给你一个长为\(n\)的序列\(b\),请你构造一个长为\(n\)的序列\(a\),满足\(b\)中的数都能由\(a\)中两个不同下标的数相加得到。无解报告NO,\(n\le10^3,b_i\le10^6\)。我们发现如果我们能用\(a_1\sima_m\)来凑出\(b_1\simb_m\),剩下的令......
  • cf1583h-solution
    CF1583HSolutionlink第一问容易处理,将边权从大到小排序,并查集维护一下连通块最大值简单搞搞就好。考虑第二问。我们对原树,按照\(t\)的权值建造克鲁斯卡尔重构树,那么两点的lca权值即它们路径上边权最大值。同样按照边权\(c\)从大到小将边排序,维护连通块内最大值的同时,维......
  • cf1555f-solution
    CF1555FSolutionlink分析一张图中的环,我们可以考虑把图表示为一棵生成树加上许多非树边。对于这题,我们考虑动态维护一片森林,在每次准备加一条边\((u,v)\)时:如果这条边加进去后与森林不形成环,那么它与图肯定也不形成环,那么直接加进森林中。如果这条边是森林的一条非树......
  • cf1553f-solution
    CF1553FSolutionlink首先显然地\(\displaystylep_i=p_{i-1}+\sum_{j=1}^{i-1}a_j\bmoda_i+\sum_{j=1}^{i-1}a_i\bmoda_j\)。那么两部分分开来算。\(\displaystyle\sum_{j=1}^{i-1}a_j\bmoda_i\):我们知道\(x\bmody=x-y\lfloor\fracxy\rfloor\),那么我们先把答案加上......
  • cf1548c-solution
    CF1548CSolutionlink题意说人话就是每次给\(x\)求\(\displaystyle\sum_{i=1}^n\binom{3i}x\)。由于多组询问,考虑能不能生成函数。设\[\begin{aligned}f_k&=\sum_{i=1}^n\binom{3i}k\\F(x)&=\sum_{i=0}^\inftyf_{i}x^i\\&=\sum_{i=0}^\infty\sum_{j=1}^n\bin......
  • cf1491h-solution
    CF1491HSolutionlink考虑分块。按照点的编号分块,维护\(b_i\)表示\(i\)往上跳遇到的第一个与\(i\)异块的点。对于散块修改,直接暴力重构整块的\(b\)。重构方式是,如果\(a_i\)与\(i\)异块,则\(b_i\getsa_i\);否则\(b_i\getsb_{a_i}\)。对于整块,打标记维护整体减了多......
  • cf1491e-solution
    CF1491ESolutionlink首先,把一棵大小为\(f_i\)的树切成两棵树只能是切成\(f_{i-1}\)和\(f_{i-2}\)的,而且最多只有两种切的方案。证明考虑分类讨论是否有大小为\(f_{i-1}\)的子树(以\(1\)为根)即可,感性理解就好。接下来你可以选择每次暴力通过两种割边方案递归检验,但是......
  • cf1487g-solution
    CF1487GSolutionlink想一想没有字符的限制怎么做。首先,没有长度大于一的奇回文串显然等价于没有长度为\(3\)的回文串。也就等价于\(\foralli\in[1,n-2],s_i\not=s_{i+2}\)。那么在没有限制的情况下,我们确定好了前两位字符,后面的\(n-2\)位各有\(25\)种字符可选。方......
  • cf1446d2-solution
    CF1446D2Solutionlink首先,最终答案区间中的众数一定包括整个序列的众数\(K\)。证明:设这个区间中众数出现次数为\(cnt\)。如果上述不成立,由于\(K\)在这个区间中出现次数小于\(cnt\),我们将区间向两边延申,\(K\)的出现次数应当不断增加直到等于区间的众数出现次数。这样子......