题意 题目链接Codeforces Round #813 (Div. 2) - D. Empty Graph 给你一个长度为$n$的序列，以及一个整数k，这是一个无向完全图，两点(l,r)之间的路径长度为 $$ dis(l,r)\ =\ min\lbrace a[l],a[l+1],\cdots,a[r-1],a[r]\rbrace $$ 你可以将一个点的权值求改为小于等于1e9的任意值，可以修改最多k个点。 求图的直径的最大值。 图的直径：任意两点(u,v)之间最短距离的最大值 思路 先来看任意两个点(i,j)之…
题意 给你一个字符串$s$，有$q$次询问，每次询问格式有两种： 1) 1 pos c：将字符串中位置为pos的字符改为c 2） 2 x y：询问区间$[x,y]$中有多少个不一样的字符 数据范围： $|s|\leq 10^5,q\leq 10^5$ 思路 我是先会做了另外一道线段树的题（线段树-单点修改+区间求最大连续子段和 - CarryNotKarry）才会秒这个题的。 这个题很明显是单点修改，然后区间查询，这里设置一个结构体，有普通的存当前结点的l,r以及如果是叶子节点的字符ch，也存上一个num[26]数…
题意 给定长度为 N 的数列 A，以及 M 条指令，每条指令可能是以下两种之一： 1. 1 x y,查询区间$[x,y]$种的最大连续子段和，即 $$ \max {x \leq l \leq r \leq y}\lbrace \sum{i=l}^{r} A[i] \rbrace $$ 2 x y,把$A[x]$改成$y$ 对于每一个查询指令，输出一个整数表示答案。 题目来源于AcWing245，245. 你能回答这些问题吗 - AcWing题库 思路 以前我的线段树都是封装的，但是对于这样的询问需要返回不止一个值，…
题意 题目链接：Mayor's posters - POJ 2528 - Virtual Judge (vjudge.net) 有$T$组数据，每次有$n$个区间，第$i$个区间将会把$[l_i,r_i]$染成$i$颜色，最后从上往下看有多少种不同的颜色？ 数据范围 $1\leq n\leq 10000$ $1\leq l_i\leq r_i\leq 10^7$ 思路 区间太大，肯定不能用这么大的数组（$O(nlogn)$），又注意到$n$比较小，所以要用到离散化。 比如这个样例： 7 11 7 8 10 11 那…
题意 题目链接：Problem - 3874 (hdu.edu.cn) 给你一个长度为$n(1\leq n \leq 50000)$的数组，以及$q(1\leq q\leq 200000)$次询问，每次询问有两个数字$x,y$，询问区间$[x,y]$的漂亮值是多少，漂亮值定义如下：对于区间$[x,y]$内所有不同元素的和，例如区间内有$3,5,5$，那么值就是$3+5=8$。 思路 显然是RMQ问题，但是这个不重复的数字很麻烦，我迅速敲了一个莫队上去，果不其然TLE了，查询次数太多以及还有多组询问，所以需要用到线段…
题目 2022年天梯赛决赛的前一晚，来几道二叉树的题目(RP++) 给你一个完美二叉树的前N项的后序遍历，求它的层序遍历 我的思考 我的思路是根据每个点往下有多少个子结点，因为给我的最后一个肯定是根，然后递归往下找。 我用一个我自己的样例，就是上图的10个 10 91 83 71 14 2 34 10 15 55 18 这个18肯定是根，前一个肯定是它的右结点，但是每一个数的前一个不一定是右结点，因为有可能不存在，所以我们判断一下： inline void dfs(int x,int p) { if (p<=…
题意 比赛链接：Problem - F - Codeforces 给你一个长度为$n(3\leq n\leq 2\times 10^5)$序列，问你是否能够将其分成三段使其满足如下条件：第一段Max=第二段Min=第三段Max，如果存在则输出"YES"和每段的长度，否则输出"NO"。 思路 看到这个数据我第一反应是双指针+贪心，但是wa2中的testcase721...最终放弃，去补题了，后来发现是自己贪心的方法不对，这里用二分+贪心过的。 这里枚举第一段的范围（时间复杂度$O(n)$），然后去二分第二个区间的长度…
题意 给定一个长度为 $N$ 的数组 $A=[A_1,A_2,⋅⋅⋅,A_N]$，数组中有可能有重复出现的整数。 现在小明要按以下方法将其修改为没有重复整数的数组。 小明会依次修改 $A_2,A_3,⋅⋅⋅,A_N$。 当修改 $A_i$ 时，小明会检查 $A_i$ 是否在 $A_1∼A_{i−1}$ 中出现过。 如果出现过，则小明会给 $A_i$ 加上 $1$；如果新的 $A_i$ 仍在之前出现过，小明会持续给 $A_i$ 加 $1$，直到 $A_i$ 没有在 $A_1∼A_{i−1}$ 中出现过。 当 $A_N…
