798. 差分矩阵 输入一个n行m列的整数矩阵，再输入q个操作，每个操作包含五个整数x1, y1, x2, y2, c，其中(x1, y1)和(x2, y2)表示一个子矩阵的左上角坐标和右下角坐标。 每个操作都要将选中的子矩阵中的每个元素的值加上c。 请你将进行完所有操作后的矩阵输出。 输入格式第一行包含整数n,m,q。 接下来n行，每行包含m个整数，表示整数矩阵。 接下来q行，每行包含5个整数x1, y1, x2, y2, c，表示一个操作。 输出格式共 n 行，每行 m 个整数，表示所有操作进行完毕后的最终矩阵。 数据范围1≤n,m≤1000,1≤q≤100000,1≤x1≤x2≤n,1≤...

797. 差分 题目描述 输入一个长度为n的整数序列。 接下来输入m个操作，每个操作包含三个整数l, r, c，表示将序列中[l, r]之间的每个数加上c。 请你输出进行完所有操作后的序列。 输入格式第一行包含两个整数n和m。 第二行包含n个整数，表示整数序列。 接下来m行，每行包含三个整数l，r，c，表示一个操作。 输出格式共一行，包含n个整数，表示最终序列。 数据范围 1≤n,m≤100000, 1≤l≤r≤n, −1000≤c≤1000, −1000≤整数序列中元素的值≤1000输入样例： 6 3 1 2 2 1 2 1 1 3 1 3 5 1 1 6 1输出样例： 3 4 5 3 4 ...

1264. 动态求连续区间和 题目描述 给定 n 个数组成的一个数列，规定有两种操作，一是修改某个元素，二是求子数列 [a,b] 的连续和。 输入格式第一行包含两个整数 n 和 m，分别表示数的个数和操作次数。 第二行包含 n 个整数，表示完整数列。 接下来 m 行，每行包含三个整数 k,a,b （k=0，表示求子数列[a,b]的和；k=1，表示第 a 个数加 b）。 数列从 1 开始计数。 输出格式输出若干行数字，表示 k=0 时，对应的子数列 [a,b] 的连续和。 数据范围 1≤n≤100000, 1≤m≤100000， 1≤a≤b≤n输入样例： 10 5 1 2 3 4 5 6 7 8...

C. Covered Points Count 题意 给N条线段，这些线段可以覆盖至少一个点，求被1～N条线段覆盖的点各有多少个？input 3 0 3 1 3 3 8output 6 2 1 样例解释 分析 开始为一条高度为0直线，对于每一条线段[l,r]，我们就让位于[l,r]部分高度-1，处理完之后，某个点下降了多少高度就是被多少条线段所覆盖。从这里就已经可以看出来是一个典型的差分题，让位于[l,r]部分高度-1，就是差分数组B[l]-=1,B[r+1]+=1, 处理完之后再还原成原始高度数组即可。但是此题还涉及了离散化，所以不能一个点一个点的算，而需要按线段来算(其实就是离散化还...

101. 最高的牛 这是一个比较典型使用差分技巧的题。题目中给出了M对牛可以互相看见对关系，那么对于两个可以互相看到的牛a，b。在差分数组B中，只需要让 B[a+1] -= 1 B[b] += 1这样做可以保证a，b之间的牛至少比a，b少一个高度，这样就能使得a，b可以互相看见进过M次处理之后，就可以把差分数组转换成原始数组，原始数组还有加上最高位与原始数组上对应位的差值，也就是加上H-A[p]因为此题的M对关系可能重复，这里我用的set进行去重复 #include <iostream> #include <algorithm> #include <set>...

F. Three Paths on a Tree 题意 给一个树，让在树上找三个结点A，B，C，使得ABC三个结点3条路径中出现的结点数最多 分析 因为这是一棵树，三条路径必定会有一个交点O，所以我们需要让OA+OB+OC的长度尽可能的长，而OA+OB我们可以直接认为是树的直径，OC认为是这条直径上最长的一个分支。 具体做法 这里我用的是两次DFS求树的直径以及经过的路径结点，第一次DFS：先从任意一个结点开始DFS到最远的距离，保存最远点A第二次DFS：从A再进行一次DFS到最远的距离B，并且记录B->A的路径(倒着存的)此时就以及求出了直径了，也就是OA+OB第一次遍历直径中的结点，...

E. Obtain a Permutation 题意：给定一个n*m的矩阵，你需要通过操作变成目标矩阵，每一次操作可以是修改一个数，可以是将一列循环上升一位，求最小的操作次数。 分析 其实这题只能算是一个暴力题，每一列其实是独立的，把每一列的最小操作次数求出来累加就是结果。而对于每一列，需要统计出每一个元素需要几次上升操作能够移动到正确位置上，用step[i] = c 表示，此列向上移动i次，可以有c个元素移动到正确位置上。当统计完一列之后复杂度是O(n),然后再进行n次循环进行ans = min(ans,i+n-step[i]) i:上升操作次数，n-step[i]改变次数，复杂度也是O(n...

MEX maximizing 题意 开始给一个空的数列，然后q次询问，每一次询问都会添加一个数，我们可以对当前的数列的任意非负数进行加减x，然后求出多种方案中未出现的最小非负整数中最大的是哪个。 分析 对添加的数进行对X取模，并进行记录取模后的值a，以及a出现的次数t，对于每次询问答案ans = a+x*tt和a都是最小的，t是主键，a是次键 代码 #include <iostream> #include <algorithm> #include <queue> using namespace std; const int maxn = 1e6+10; ty...

New Year Parties 题意 n个人分布在一维坐标上，每个人可以左走一步xi-1，右走一步xi+1，或者原地不动xi，求通过此操作，最少占用坐标的点数和最多占用的点数分别是多少？ 分析 求最小值： 因为最多只能将连续3个坐标的人，放在一个坐标上，所以从左往右扫描，如果i位置上有人，那么i,i+1,i+2就可以住一个房子，结果+1，然后i = i+3，继续同样的操作 求最大值： 从整体出发，先从左往右扫一遍，如果某个位置非空，但是左一个为空，就派一个人去占位，再从右往左扫描，如果某个位置非空，但是右边一个为空，就派一个人去占位。 所以整体上就形成了，整体尽量往左走一个，然后再整体尽量往...

Christmas Trees 题目描述 There are 𝑛n Christmas trees on an infinite number line. The 𝑖i-th tree grows at the position 𝑥𝑖xi. All 𝑥𝑖xi are guaranteed to be distinct. Each integer point can be either occupied by the Christmas tree, by the human or not occupied at all. Non-integer points cannot be oc...

Marvolo Gaunt's Ring Professor Dumbledore is helping Harry destroy the Horcruxes. He went to Gaunt Shack as he suspected a Horcrux to be present there. He saw Marvolo Gaunt's Ring and identified it as a Horcrux. Although he destroyed it, he is still affected by its curse. Professor Snape is helping ...

1275. 最大数 给定一个正整数数列 a1,a2,…,ana1,a2,…,an，每一个数都在 0∼p−1 之间。 可以对这列数进行两种操作： 添加操作：向序列后添加一个数，序列长度变成 n+1； 询问操作：询问这个序列中最后 L 个数中最大的数是多少。 程序运行的最开始，整数序列为空。 写一个程序，读入操作的序列，并输出询问操作的答案。 输入格式 第一行有两个正整数 m,p，意义如题目描述； 接下来 m 行，每一行表示一个操作。 如果该行的内容是 Q L，则表示这个操作是询问序列中最后 L 个数的最大数是多少； 如果是 A t，则表示向序列后面加一个数，加入的数是 (t+a) mod p...

Nearest Opposite Parity You are given an array 𝑎 consisting of 𝑛 integers. In one move, you can jump from the position 𝑖 to the position 𝑖−𝑎𝑖 (if 1≤𝑖−𝑎𝑖) or to the position 𝑖+𝑎𝑖 (if 𝑖+𝑎𝑖≤𝑛). For each position 𝑖 from 1 to 𝑛 you want to know the minimum the number of moves required t...