首页 > 其他分享 >cf1396d-solution

cf1396d-solution

时间:2024-02-28 13:45:29浏览次数:22  
标签:nxt sum solution 枚举 cf1396d mathcal 矩形 赋值

CF1396D Solution

link

题面:

给你一个 \(L\times L\) 的矩形,有 \(n\) 个点放在不同的格子内,每个点有颜色,共 \(k\) 种颜色,求有多少个矩形满足其内部含有所有颜色的点,对 \(10^9+7\) 取模。

\(k\le n\le2000,L\le10^9\)。


首先离散化。

看到数据范围说明可以枚举矩形的某个端点或者上下(左右)边界。枚举端点没什么用,考虑枚举上下边界 \(u,d\)。

现在只看第 \(u\) 行到第 \(d\) 行,我们要统计有多少对 \((l,r)\) 满足第 \(l\) 列到第 \(r\) 列是满足条件的。

这是一个典型问题。设 \(f_i\) 表示最小的 \(j\) 满足第 \(i\) 列到第 \(j\) 列是满足条件的,那么 \(l=i\) 的贡献即为 \(L-f_i+1\)。

设 \(m\) 为 \([u,d]\) 内点数,\(c_i\) 表示离散化后的点的列编号,答案即为

\[\begin{aligned} \sum_{i=1}^m(c_i-c_{i-1})(L-f_i+1)&=\sum_{i=1}^m(c_i-c_{i-1})(L+1)-\sum_{i=1}^m(c_i-c_{i-1})f_i\\ &=c_m(L+1)-\sum_{i=1}^m(c_i-c_{i-1})f_i \end{aligned}\]

至于如何求 \(f\),考虑设 \(nxt_i\) 为第 \(i\) 列所有颜色的下一个出现的列的最大值。

如果现在求出了 \(f_i\),显然 \(f_{i+1}=\max(f_i,nxt_i)\)。每次处理 \(f\) 是 \(\mathcal O(n)\) 的,我们得到了一个 \(\mathcal O(n^3)\) 的算法。

现在考虑固定 \(u\),在枚举 \(d\) 时优化。你发现如果从小到大枚举 \(d\) 会出现插入点的操作,这使得有些 \(nxt\) 需要缩小,不方便处理 \(\max\)。

于是考虑反过来,从大到小枚举 \(d\),把插入变成删除,这样子 \(nxt\) 只会增大。

\(f\) 数组实质上是 \(nxt\) 数组的前缀最大值,那么我们修改 \(nxt\) 时只需要将其后面的某一段 \(f\) 统一赋值即可。这个赋值的边界可以二分得到。

那么你现在需要支持 \(f\) 数组的:区间赋值,总体求和。这个显然可以线段树维护。

这样每个 \(u\) 耗费 \(\mathcal O(n\log n)\) 的时间,总复杂度即为 \(\mathcal O(n^2\log n)\)。

标签:nxt,sum,solution,枚举,cf1396d,mathcal,矩形,赋值
From: https://www.cnblogs.com/iorit/p/18040099

相关文章

  • cf1340d-solution
    CF1340DSolutionlink手❤玩❤一❤下,答案大概就是所有点的度数最大值。下面证明。首先这个肯定是答案的下界,因为度数最大的点至少被经过了它的度数次。现在考虑构造。对于一棵以\(u\)为根的子树,如果我们能证明第一次到\(u\)的时间是\(t\),最后一次到\(u\)的时间是\(t-......
  • cf1332f-solution
    CF1332FSolutionlink设\(dp_{u,0/1,0/1}\)表示在\(u\)的子树中,节点\(u\)与它父亲的边是否在导出子图中,点\(u\)是否在独立集中,的方案数。\[dp_{u,0,0}\gets\prod_v(dp_{v,0,0}+dp_{v,1,0}+dp_{v,0,1}+dp_{v,1,1})\]\[dp_{u,1,0}\gets\prod_v(dp_{v,0,0}+dp_{v,1,0}+......
  • cf1303g-solution
    CF1303GSolutionlink\(k\)个数\(a_i\)的前缀和的和就是\(\displaystyle\sum_{i=1}^k(k-i+1)a_i\)。这个题可以考虑换一下\(u,v\),那么式子就变成了\(\displaystyle\sum_{i=1}^kia_i\)。注意到要统计树上路径的最值,考虑点分治。考虑上面的式子从\(j\)处断开,那么式子变......
  • cf1286d-solution
    CF1286DSolutionlink题面:有\(n\)个粒子,第\(i\)个粒子在位置\(x_i\)并有\(v_i\)的初速度。实验开始后,第\(i\)个粒子有\(p_i\)的概率向右移动,有\(1-p_i\)的概率向左移动。求第一次发生粒子碰撞的期望时间,对\(998244353\)取模。\(n\le10^5,|x_i|\le10^9\)。......
  • cf1265e-solution
    CF1265ESolutionlink题解在说啥???期望步数不就是期望轮数乘上每轮的期望步数期望轮数就是这轮结束的概率的倒数即\(\dfrac1{\prod_{i=1}^np_i}\)每轮期望步数根据期望的线性性就是\(\sum_{i=1}^ni(1-p_i)\prod_{j=1}^{i-1}p_j\)也就是步数乘上在这里停下来的概率,停下来的概......
  • 2.27 闲话 & solution 『你是太阳神倾倒而下美酒的甜香/是最高的永恒破碎之后的希望』
    考完试了,我想听歌写了几道LCT,但是都是板子我想听歌Cave洞穴勘测LCT板子啊,直接乱搞就行对于Connect操作和Destroy操作其实是Link和Cut的板子至于Query操作么...阿拉阿拉,直接对(u,v)都进行一次Find,然后判断是否相等即可核心代码就那么几行intn,m;FastI>>n>>m;while(m--......
  • cf1209g2-solution
    CF1209G2Solutionlink根据题意,对于一个颜色的所有下标集合\(S\),设其最小,最大位置是\(l,r\),那么最后染完色的\([l,r]\)区间一定是同一种颜色。如果有两个颜色\(i,j\),\([l_i,r_i]\)和\([l_j,r_j]\)有交集,那么这个区间并起来的大区间也一定是同一种颜色的。这样我们并并......
  • cf1153f-solution
    CF1153FSolutionlink题意:有一段长为\(l\)的线段,有\(n\)个实数区间,左右端点在\([0,l)\)间均匀随机。求期望被至少\(k\)段区间覆盖的长度,对\(998244353\)取模。\(1\lek\len\le10^7,1\lel\le10^{10^6}\)首先\(l\)是没用的,我们可以计算线段长为\(1\)时的......
  • cf1148h-solution
    CF1148HSolutionlink对于区间mex,若固定一个右端点\(r\),左端点\(l\)越小mex肯定越大。假设我们维护了右端点为\(n\),左端点为\(i\in[1,n]\)的区间mex(设为\(b_i\)),考虑在序列末尾加入一个数\(x\):显然有且仅有原先\(b_i=x\)的一段\(b\)会被改掉。改成什么呢?大概......
  • cf1184a3-solution
    CF1184A3Solutionlink题意:给你两个长度为\(n\)的小写字符串\(s,t\)和一个\(m\),定义哈希函数\[h(s)=\left(\sum_{i=0}^{n-1}s_ir^i\right)\bmodp\]求构造\((p,r)\)且\(p\gem,r\in[2,p-1]\),使得\(h(s)=h(t)\)。\(n,m\le10^5\)。题目即求一个多项式\(f(x)=\sum_{......