xyq0220

未归档

题解(3)

/ 注册

全部文章 / 未归档（共3篇）

Codeforces 1167 F Scalar Queries 计算贡献+树状数组

题意给一个数列\(a\),定义\(f(l,r)\)为\(b_1, b_2, \dots, b_{r - l + 1}\),\(b_i = a_{l - 1 + i}\),将\(b\)排序,\(f(l,r)\)=\(\sum\limits_{i = 1}^{r - l + 1}{b_i \cdot...

计算贡献树状数组

2019-05-16

0 428

codeforces 1249 D2 Too Many Segments (hard version) 贪心+树状数组

题意给定n个线段，线段可以相交，第\(i\)个线段覆盖的区间为\([l_i,r_i]\)，问最少删除多少个线段让覆盖每个点的线段数量小于等于k。分析从左往右扫每个点\(x\)，若覆盖点\(x\)的线段数cnt大于k，则贪心的删去覆盖点\(x\)的线段中\(r_i\)前\(cnt-k\)大...

树状数组贪心

2019-10-24

0 414

Codeforces 1167 F Scalar Queries 计算贡献+树状数组

题意给一个数列\(a\),定义\(f(l,r)\)为\(b_1, b_2, \dots, b_{r - l + 1}\),\(b_i = a_{l - 1 + i}\),将\(b\)排序,\(f(l,r)\)=\(\sum\limits_{i = 1}^{r - l + 1}{b_i \cdot...

codeforces 计算贡献树状数组

2019-05-16

0 563