GenmCai

题解

ACM(1) C++(2) C\C++(1) Git(1) Linux(1) Python(2) shell(3) 算法和数据结构(6)

/ 注册

全部文章 / 题解（共7篇）

题解 | 《算法竞赛进阶指南》interval GCD

【题目】给定一个长度为N的数列A，以及M条指令，每条指令可能是以下两种之一：1、“C l r d”，表示把 A[l],A[l+1],…,A[r] 都加上 d。2、“Q l r”，表示询问 A[l],A[l+1],…,A[r] 的最大公约数(GCD)。对于每个询问，输出一个整数表示答案。【题解】 ...

线段树

2019-09-08

0 857

题解 | 《算法竞赛进阶指南》整数的一个小问题

【题目】给定长度为N的数列A，然后输入M行操作指令。第一类指令形如“C l r d”，表示把数列中第l~r个数都加d。第二类指令形如“Q X”，表示询问数列中第x个数的值。对于每个询问，输出一个整数表示答案。【题解】区间更新，单点查询，第一反应要么树状数组，要么线段树。个人更擅长线段树，就说说...

线段树

2019-08-27

0 547

题解 | 《算法竞赛进阶指南》你能回答这些问题吗（三）

【题目】给定长度为N的数列A，以及M条指令，每条指令可能是以下两种之一：“1 x y”，查询区间 [x,y] 中的最大连续子段和，即 “2 x y”，把 A[x] 改成 y。对于每个查询指令，输出一个整数表示答案【题解】刚开始看的时候，单点更新，区间修改，第一反应就是线段树，但问题就出在求...

线段树

2019-08-27

1 796

题解 | 《算法竞赛进阶指南》一个简单的整数问题

【题目】 You have N integers,.You need to deal with two kinds of operations. One type of operation is to add some given number to each number in a given i...

线段树

2019-08-26

0 682

CodeForces - 12D Ball 线段树

题意：emmmm，就是题目描述的女性很奇葩，她们去参加国王举办的舞会，而每个女士有B、I、R三种属性，如果她们得知舞会上存在一个比自身所有属性都要高，那么她就会选择跳楼。。。问有多少个要跳楼的女士。题解：其实很简单，即按照B进行从大到小排序，然后线段树对比I大的区间进行查询最大值，如果最大值大于自身...

线段树

2019-07-27

1 672

POJ - 2777 Count Color 线段树+位运算

Count ColorTime Limit: 1000MS Memory Limit: 65536KTotal Submissions: 55483 Accepted: 16628Description Chosen Problem Solving and Program...

线段树位运算

2019-07-27

0 663

UVA - 11992 线段树+并查集+模拟

题目意思就是，road命令连接第A坐标和第B坐标的点。而line则是查看纵坐标C拉出的扫描线过几个联通块，而联通块中的数量和是多少。（具体的可以查看原题）题解：其实是线段树一个简单的模拟，即并查集找联通块和联通块中点的数量，然后每次更新删除A点和B点的信息，重新建立A点和B点连接后的信息就行...

线段树

2019-07-27

1 872