现在是北京时间2022/7/27-21:20，距离比赛打完已经过去了2天，已经积累了牛客3还有杭电3没有写...明天又要打杭电4...这里就好像一个队列，当当前size==2就在push前pop队首一样。 比赛链接:"蔚来杯"2022牛客暑期多校训练营3 这一次在封榜后怒学一手后缀自动机(SAM)，然后套了自己线段树的板子怒交一发H竟然过了，解绑后来到了史无前例的rk115。 C.Concatenation（排序） 题意：给你$n(1\leq n\leq 2e6)$的字符串，总字符串长度不超过$2e7$，求将其拼接…
题意 给你一个字符串$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了，查询次数太多以及还有多组询问，所以需要用到线段…
题意 比赛链接：Problem - F - Codeforces 给你一个长度为$n(3\leq n\leq 2\times 10^5)$序列，问你是否能够将其分成三段使其满足如下条件：第一段Max=第二段Min=第三段Max，如果存在则输出"YES"和每段的长度，否则输出"NO"。 思路 看到这个数据我第一反应是双指针+贪心，但是wa2中的testcase721...最终放弃，去补题了，后来发现是自己贪心的方法不对，这里用二分+贪心过的。 这里枚举第一段的范围（时间复杂度$O(n)$），然后去二分第二个区间的长度…
写在前面 这是一次4.21的vjudge训练，打算认真做一次，出题还算可以不过有点慢，慢慢靠过题数达到了前方，E题我觉得是最难的但是20.12.31补过这个...我打算直接开F，没想到做了2h的F也没写出来，我用的双指针，指针移动的方式错误，我查不到数据，wa2的testcase721... 比赛链接：Dashboard - Codeforces Round #686 (Div. 3) - Codeforces A - Special Permutation（思维+构造） 题意 给你一个长度为$n$的序列，让你输出…
