专栏文章

CF1119D Frets On Fire

AAutream
CF1119D题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mio9c450
此快照首次捕获于
2025/12/02 15:29
3 个月前
此快照最后确认于
2025/12/02 15:29
3 个月前
查看原文
考虑先将矩阵的行按 sis_i 从小到大排序，求出 {sn}\{s_n\} 的差分数组 {cn}\{c_n\}，容易发现每一行的贡献就是它与上一行相比多出的部分，也就是 min⁡{ci,r−l+1}\min \{c_i, r - l + 1\}（第一行的贡献为 r−l+1r - l + 1）。
发现答案与 cic_i 的顺序并无关联，于是考虑将 {cn}\{c_n\} 排序，二分出第一个 ci>r−l+1c_i > r - l + 1 的位置，用前缀和求解即可。

代码

CPP
CI N = 2e5 + 5;
int n, q, a[N], c[N], s[N];
signed main() {
	n = read();
	arrin(a, n);
	std::sort(arrall(a, n));
	rep(i, 1, n) c[i] = a[i] - a[i - 1];
	c[1] = 0;
	std::sort(arrall(c, n));
	rep(i, 1, n) s[i] = s[i - 1] + c[i];
	q = read();
	while(q --) {
		int l = read(), r = read(), ans = r - l + 1;
		int idx = std::l_b(arrall(c, n), r - l + 1) - c;
		ans += s[idx - 1] + (n - idx + 1) * (r - l + 1);
		printk(ans);
	}
	return 0;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...