Codeforces 1119D Frets On Fire 题解
题意
给定$n$和$s_1,s_2,\dots,s_n$,由此得到一个$n\times(10^{18}+1)$的矩阵$f$,其中$f_{i,j}=s_i+j (1\le i\le n,0\le j\le 10^{18})$。
在样例$1$中,给定$n=6,s=[3,1,4,1,5,9]$,得到
再给定$q$个查询,每个查询有$L,R$,问第$L$列到第$R$列(以下表达为$[L,R]$)有多少个不同的数。
题解
因为问的是列,所以行的顺序不重要,可以对$s$进行从小到大排序。
对样例$1$排完序之后矩阵变为
还有:查询$[L,R]$与查询$[0,R-L]$是等价的。
定义$r=R-L,w=r+1$。
考虑当每一行对于整个矩阵即$r=10^{18}$时的贡献。
对于样例$1$:
- 第$1$行贡献了$0$个数$\{\varnothing\}$;
- 第$2$行贡献了$2$个数$\{1,2\}$;
- 第$3$行贡献了$1$个数$\{3\}$;
- 第$4$行贡献了$1$个数$\{4\}$;
- 第$5$行贡献了$4$个数$\{5,6,7,8\}$;
- 第$6$行贡献了$w$个数$\{9,10,\dots,9+10^{18}\}$。
很容易发现,第$i (1\le i<n)$行的贡献为$s_{i+1}-s_i$,第$n$行的贡献为$w$。
对于任意区间$[0,r]$,第$i (1\le i<n)$行的贡献即为$\min\{s_{i+1}-s_i,w\}$,第$n$行的贡献为$w$。
那么答案即为$\sum_{i=1}^{n-1}{\min\{s_{i+1}-s_i,w\}}+w$。
问题:时间复杂度为$O(n\cdot q)$。
解答:设数组$t$,其中$t_i=s_{i+1}-s_i (1\le i<n)$,将$t$从从小到大排序。设$p$为满足$t_p\le w$的最小值(用二分,时间复杂度为$O(\log n)$),那么答案为$t_1+t_2+\dots+t_p+w\times(n-p)$($t_1+t_2+\dots+t_p$用前缀和求出)。时间复杂度为$O(\log n\cdot q)$。
程序
1 | // #pragma GCC optimize(2) |