洛谷题面T1,T2,T4没什么价值，建议跳过，在此不提供T1,T2题解，套题T5,T7较为精彩，个人安利一下T3题面翻译给定 n个人做 m个题的时间分布情况，每题得一分，每题的完成时间是这道题的罚时，排名按照得分为第一关键字升序，罚时为第二关键字降序，计算在所有人都按最优顺序做题的情况下，第 1个

联考看到T1就知道一定是简单计数题然后发现\(O(n)\)可以过于是就大概写了写式子就开写。写的过程中犯了一些低级错误，代码重构了一次才过。耽误的时间比较久。然后开T2，一眼有一个\(O(n^2)\)的dp。然后考虑优化，但是记录下标必须再带一个信息所以无论怎么优化都不能到\(O(n

前置指使：可持久化线段树题解：P4137RmqProblem/mex有一个长度为\(n\)的数组\(\{a_1,a_2,...,a_n\}\)。\(m\)次询问，每次询问一个区间内最小没有出现过的自然数。Input第一行，两个正整数\(n,m\)。第二行，\(n\)个非负整数\(a_1,a_2,...,a_n\)。接下来\(m\)行，每

1.函数---x对应唯一的y,类似y=x^2,x2+y2=1,属于方程但不属于函数2.周期函数-x缩扩几倍,周期扩缩相同倍数3.奇偶函数--定义域一定关于原点对称4.函数增减性5.函数有界/无界--无界,任给M,Ex0,|f(x0)|>M有界,对于所有x,|f(x)|<=M6.上界和下界,M1

T1：每次找到最小的堆，与次小的合并即可T2：简单题，直接口胡了考虑转化成几个大小关系然后只要每次将队列首插入堆中即可T3：显然字典序满足贪心性质每次用堆来维护没被取的最大值，然后取出它再在后面的元素上打一个懒标记视为已去过，用链表来维护该元素后面一个元素即可T4：呃呃呃

比赛在这里呢填算符下发题解说的神马东西，赛时根本想不到讲一个赛时想得到的\(O(n\log值域)\)的思路，很好理解我们处理出二进制下每一位上的1的最后一次出现的位置，将第\(i\(i\in[0,60])\)位上的1最后一次出现的位置记作\(pos_i\)同时我们设\(H=n-k-1\)为总共有的

NOIP2024集训Day57哈希A.[CF213E]TwoPermutations考虑到都是排列，值域连续，于是\(a\)都加\(x\)之后相当于在值域上平移了一段，也是连续的。由于要进行比较，个很容易想到哈希。\(a\)的哈希值很好维护，每次平移一位加上\(\sumbase^i\)即可。考虑如何快速取出\(b\)中在

【20省选十联测day10】EasyWin题意原题链接有\(n\)堆石子，\(n\le5\times10^5\)，每堆石子有\(a_i\)个，\(a_i\len\)。Alice和Bob每次可以从，某一堆取至少\(1\)颗、至多\(x\)颗石子，不能取的失败。Alice先手，问对于所有\(1\lex\len\)，问谁胜利。思路对于一堆石子，计

非持久化数据结构一般需要维护数据集最新状态，而可持久化要求查询历史状态。可持久化Trie树朴素：每次修改重新存一遍\(->MLE\)。正解：只存被修改部分，其余不变，即第\(i\)次修改后，树变为第\(i\)次修改产生新的部分加上前\(i-1\)次修改产生部分。增长同规模。用普通线段树维

权值线段树（维护一段值域）用线段树维护桶实质上是维护一段值域中数字出现次数例：\(1,5,4,6,7,3,8,4,5,6\)；根：\(1-8\)；左儿子：\(1-4\)；右儿子：\(5-8\)；询问目前出现第\(k\)小数字从根节点出发，如果根节点权值\(>k\)则证明存在第\(k\)小；以此类推问：如果值域很大，线段树炸了怎

决定写写Ynoi。P4119[Ynoi2018]未来日记最初分块。也是第一次品尝的Ynoi大分块。1lrxy将\([l,r]\)区间内的\(x\)全部变成\(y\)。2lrk查询\([l,r]\)区间内的第\(k\)小值。查询第\(k\)小看起来是个非常复杂的操作，一般来说看到这个想到的是二分

KLC数点由KLC大神在模拟赛中发明。其算法复杂度与答案值域大小挂钩。其能解决的问题一般有着如下的特点：给定一个序列，每次询问一个区间有多少个子区间满足什么性质，数据随机生成。其算法流程为：通过某种方法预处理出所有满足性质的子区间将得到的区间表示在二维平面上

\(\text{polylog}\)的感觉太难写了，那么考虑分块，先记询问的序列限制为\([l,r]\)，值域限制为\([x,y]\)，一个支配对为两个部分。散块内部。散块对散块。整块内部。整块对整块。散块对整块。同样是\(5\)种贡献。可以发现贡献\(2,5\)的序列不交，且两个部分一定有一个的长

SparkSpecialdottle_dpnote解决问题：分析问题性质转化问题用熟悉方法解决要记住OI不是要你发明算法，只是要找方法！"让我们揭露dp的本质"1容斥容斥是一种很重要的思想，容斥的目标是转化问题。虽然，我们看似将问题转化复杂了，但是每一个子集的计算却变简单了（不必

倍增值域分块CF702FT-Shirts考虑将\(q_i\)从大到小排序，将\(a_i\)从小到大排序，并维护一个\(b_i\)数组表示答案，我们遍历\(q_j\)数组，每次是将\(a_i\)数组中\(a_i\geqc_j\)的全部减\(c_i\)，然后\(b_i\)加1。考虑用平衡树维护\(a_i\)，split一下，右区间树

值域分块Q给定一个序列，实现单点修改\(O(1)\)，以及区间查询\(O(\sqrtn)\)A考虑设\(block_i\)表示块\(i\)的和，那么修改便是\(O(1)\)全局查询时，整块调用\(block\)，散块暴力即可\(O(\sqrtn)\)还有一些常见的例子，比如配合莫队代替主席树（区间mex）莫队二次离线普通莫队

给出\(\{a_{1\dotsn}\}\)，找出一个子集和为\(0\)。这是NPC的，当\(|a_i|\leqn\)的时候可以\(n^3\)背包，当然地可以使用bitset压位至\(\frac{n^3}w\)。值域还是太难受了，考虑怎么压下来值域，因为和为\(0\)，值域又是\(n\)，通过调整顺序总是存在一种方案使得值域在\([-

最近准备学数据结构乱搞，接下来学k-dtree大致介绍可以使用整体二分解决的题目需要满足以下性质：1.询问的答案具有可二分性2.修改对判定答案的贡献互相独立，修改之间互不影响效果3.修改如果对判定答案有贡献，则贡献为一确定的与判定标准无关的值4.贡献满足交换律，结合律，具有可加

函数及其表达方式哎，真是没想到上上周的数学课的总结会拖得那么久。表达方式：自变量&因变量在函数\(f(x)=x+1\)中，\(f(x)\)是因变量，\(x\)是自变量。定义域定义域的意思若有集合\(J\)使\(\forallx\inJ\)，则称\(J\)是\(f(x)\)的定义域。求定义域的方法1.分式函数（分母不能

最初分块先考虑怎么用分块维护区间第\(k\)小。首先肯定想到二分区间第\(k\)小，然后查询区间有多少个数小于等于\(x\)。但这样时间复杂度是\(\operatorname{O}(n\sqrt{n}\log^2n)\)的，无法通过此题。考虑这样一个事情，我们可以暴力枚举区间第\(k\)小，然后查询区间内有多

一.整体二分概念整体二分的主体思路就是把多个查询一起解决，是一个离线算法。其要求：询问的答案具有可二分性修改对判定答案的贡献互相独立，修改之间互不影响效果修改如果对判定答案有贡献，则贡献为一确定的与判定标准无关的值贡献满足交换律，结合律，具有可加性题目允

题目链接：来者不拒，去者不追直接在线查询题目所给的式子是很困难的，我们考虑单点考察贡献。对于一个已经确定的式子，我们发现加入一个数或者删除一个数的贡献如图所示：如图所示，在原有的序列为\((1,2,3)\)当中，我们加入新的\(2\)进去，我们观察到每个数的贡献的变化是这样，比\(2\)

写一点。数列分块入门6，主要是定期重构，如果数列的形态改变的话，那么设定阈值为每至少\(\sqrtn\)次操作做一次重构，时间复杂度是直接根号的。数列分块入门8，主要是势能分析（好像是），统计一个区间的最大值和最小值，这个是容易统计的，然后你考虑一个区间询问有多少个相同的，对于最大值和最

SDUT校赛题目Description给定正整数\(n\)，计算\(n\)个元素的集合\(\{1,2,\cdots,n\}\)，所有非空子集和的乘积取模\(998\,244\,353\)后的结果。Input一个正整数\(n\)\((1\len\le200)\)，代表集合大小。例如\(3\)个元素的集合有\(7\)个非空子集，分别为\(\{1\},\{

传送门description用一下方式生成一个序列：初始序列里有一个数，是什么无所谓。给定\(n\)个整数，对第\(i\)个整数\(d_i\)，若\(d_i\ge0\)，重复\(d_i\)次加入一个值比序列里最后一个值大1的数；若\(d_i<0\)，重复\(-d_i\)次加入一个值比序列里最后一个值小1的数。求该序列