Spy97

线段树

2018 Multi-University Training(7) 2019牛客多校(1) AC自动机(1) BFS(2) CCPC(7) Codeforces(16) DFS序(1) Hash(4) ICPC(6) pb_ds(2) 主席树(2) 分块(2) 分治(2) 动态规划(2) 博弈(4) 后缀数组(6) 回文树(2) 图论(15) 差分约束系统(1) 思维(8) 数学(2) 未归档(5) 树(5) 树链剖分(3) 模拟(1) 模拟退火(1) 矩阵快速幂(2) 线性基(1) 莫队(1) 计算几何(30) 贪心(2)

/ 注册

全部文章 / 线段树（共7篇）

2019牛客多校第八场 Explorer

题意一个无向图，每条边有一个区间，数值在此区间内才能通过，为从1到n可行的数值有多少个题解离散化线段树+并查集优化思路清奇每条路有个区间，我们将这个区间插入到线段树中，实际插入的是路径怎么理解呢对于线段树中的某个结点，它所包含的路径都在它表示的区间的范围内进一步说，这么多的路径...

2019-08-11

0 396

2019杭电多校第三场 HDU 6606

题意一个n个数字的序列，要分给k个人，使每个人和的最大值最小，注意可以舍弃最后的任意多个数字题解二分答案考虑二分最小值为 K K ...

HDU 6606

2019-07-30

0 391

ZOJ 4100 浙江省第16届大学生程序设计竞赛 A题 Vertices in the Pocket

题意 n n n个点，一开始没有边，有两种操作一是连接点 ( ...

2019-05-01

0 466

wannafly25 E 01串

题意：给出一个01串，有两种操作，操作一是将某一个位置的数字修改，操作二是询问某一个区间，将这个区间看做1个二进制数，可以随意加减2的幂次，问将这个数变为0的最小操作步数。题解：对于一个区间，用变成0用4种情况从后面进一位，不向前面进位从后面进一位，向前面进位不从后...

2018-10-24

0 358

离散化后线段树

正常的线段树是这样的 [1,10]->[1,5]+[6,10]; 我们统计区间和的时候也很方便每个区间的r-l+1就是区间长度现在的问题是如果数据范围太大，维护一段区间的和就不简单了例如以下对应关系 1 2 3 4 5 6 10 20 30...

2018-09-13

0 307

2018 HNCPC 湖南省程序设计竞赛 CSU 2167 Grid

题意：初始有n*m的点，矩形排列。有2种操作，第一种是将第i行的所有点联通（a<=i<=b）,第二种是将第i列的所有点联通（a<=i<=b）。每次操作后输出有多少个联通块。题解：先说结论，若某次操作后有a行，b列联通，则联通块的个数为n*m-a*(m-1)-b*(...

2018-09-13

0 644

2017香港regional Black and White

题意：给一个n*n的矩阵，初始全是白色，进行m次操作，每次操作是让一个子矩阵的颜色翻转，求最后有几个黑色的方格。题解：每行分别处理，将一个子矩阵拆成两条线段，分别是上底和下底，然后按照线段的高度排序。每到一行，将所有高度等于该行的下底的线段加入线段树中，表示对这个线段进行翻转，更新答案...

2018-09-03

0 2806