E2. Rollbacks (Hard Version)题目翻译 初始有一个空的数组，我们需要对它进行q次操作，我们可以执行4种操作，操作+，添加一个元素x到数组后面。操作-，移除数组末尾的k个数字，操作！，撤回上一个操作，只会撤回+，-。操作？，输出数组种不同种类的数的个数。保证操作合法，hard版本要求强制在线。
思路 首先本题我们看见其回退操作自然考虑使用可持久化的数据结构进行维护，考虑可持久化线段树，发现我们可以维护一个权值线段树表示每个值得元素是否有贡献，添加操作实际上就是新版本新建一个单点处理，减去操作实际上就是创建一个当前版本的k级祖先的镜像版本，回退操作实际上就是直接删去一个版本即可。考虑如何快速回调k级版本的祖先，我们可以维护倍增，记录每个版本的父亲版本倍增状态。但这样写完之后我们发现会MLE，经过计算我们发现我们最多只有1.4e7的空间给可持久化线段树，这是不够的，考虑优化，我们只用标记某个值是否做了贡献，所以我们可以进行状态压缩，把所有长度为32的区间压缩到一个int里，这样我们线段树的值域范围可以/32，这样我们需要1.6e7的空间。我们发现还是不 ...
B. Brackets题目翻译 题目给我们一个长度为n的括号序列，该括号序列包含4种括号(), [], {}, <>。一个合法的括号序列的定义是LxR，L和R是同种类的括号的左右括号，x是一个合法的括号序列，x = y1y2，y1y2为两个合法的括号序列。题目还给我们m个子区间，我们需要计算这些子区间的括号序列进行两两匹配最多可以形成多少对合法的括号序列。(gym原题链接,复制粘贴前往 https://codeforces.com/gym/105588/problem/B)
思路 首先我们通过观察题目的合法括号序列的性质可以发现，对于一个合法的括号序列，如果我们将其拆分成两半，那么要么两半初始都是合法的，要么左半去掉已经匹配的可以缩成一系列的左括号，右半也是同理。考虑吧如何处理出每个区间是什么样的情况，我们继续观察发现对于左半的情况我们可以直接使用括号栈来维护前缀种待匹配的左括号，在每个右端点时考虑区间是否可以作为左半边，当出现无法匹配的位置时我们需要清空栈并且标记1到i（i为当前考虑的位置），这些位置均不可以作为区间的左端点。同时我们呢注意到对于产生匹配括号 ...
E. Unique Array题目翻译 题目给我们一个长度为n的数组，一个子段被称为独特的，当且仅当子段中存在一个元素只出现了一次。我们可以进行一种操作选择数组中的任意一个元素将其替换成任意数字。我们需要输出我们最少需要进行几次操作可以使得数组中的所有子段都是独特子段。
思路 首先我们容易想到一个O(n ^ 2 * lgn)的解法我们可以暴力的处理除所有不好的子段，根据我们操作的性质容易发现我们只要对子段中任意一个元素进行操作我们就一定可以使得包含这个元素的子段独特，于是问题转换成了一些区间，我们要选择最少数量的点，满足每个区间中至少包含一个节点。这是一个经典的贪心问题，我们直接按左端点或右端点排序，顺着贪心的取最边界的点即可。
我们发现实际上有效的区间数量实际上是不超过n个的，因为所有完全覆盖了某个区间的区间都是没有意义的，于是我们可以考虑处理出每个左端点对应的最小的不独特的区间，考虑如何处理出这些区间。我们可以对每个位置的数处理出其下一个相同的数的位置，我们枚举每个左端点，初始将所有的数的第一个进行区间[x, nxt[x] - 1] + 1的操作，这意味着从x到nxt[x] ...
E. Manhattan Triangle题目翻译 题目给我们n个二维平面上的不同的点，我们要挑出三个点使得这三个点构成一个等边三角形边长为d（保证d是偶数），注意这里等边的边长意义是在曼哈顿距离下的。输出挑选哪三个点，无解输出0，0，0。
思路 首先我们容易根据曼哈顿距离的定义发现对于某个点而言，距离它为d的点围成了一个菱形，同时因为三角形的性质，在曼哈顿意义下的等边三角形总有一条边是在斜率为1的线段上的（这里可以通过画图加以发现理解）。所以我们可以考虑枚举一个节点，然后考虑另外两个节点在斜率为1的线段上，我们x从小到大枚举，通过维护[x - d, x] 与 [x, x + d]的斜率为1或-1上的点来进行快速的判断是否存在我们当前点菱形四线段上间距为d的点对，这里只用考虑同一个线段上的点对即可，因为上面曼哈顿意义下等边的性质。具体维护我采用了map套set实现，标记线段归属的斜率和初相我使用x + y, x - y来进行标识。
代码12345678910111213141516171819202122232425262728293031323334353637383940414 ...
D - Insert XOR题目翻译 题目给我们一个长度为n的二进制字符串，我们要处理q次操作，每次操作给我们一个pos，我们会翻转s[pos]，我们每次操作后都要输出当前字符串的最小代价，操作是持久化的。一个二进制字符串的代价为需要的最小的初始字符串长度，使得我们可以通过对这个初始字符串进行若干次操作来得到当前字符串，我们可以进行的操作是选择两个相邻的字符元素，在其中间插入两个数异或的结果。
思路 我们考虑代价时从当前数组删减到最小的字符串长度来考虑会更容易，首先我们发现我们需要特判掉全部为1的情况，此时需要的初始字符串一定长度为n，然后剩余的情况我们可以进行的删减实际上就三种情况
1. 11 -> 1 (要求当前字符串中存在0) 2. 000 -> 00 (无要求) 3. 101 -> 1 (要求当前字符串除这个对还存在0)
我们考虑吧维护每个元素对答案减小的贡献，则此时cur[i] == 1 && cur[i - 1] == 1, 此时位置i贡献为1，cur[i] == ...
D2. XOR Break — Game Version题目翻译 题目给我们一个初始数字n，我们要和对手进行博弈，我们可以选择先后手，我们与对手进行的游戏是这样的，当前数字初始为p，当前回合的选手需要构造两个数字p1，p2，满足（0 < p1 < p, 0 < p2 < p, p1 ^ p2 == p)，若无法构造出p1，p2则当前回合玩家输，然后另一个人挑选其中任意一个数作为当前数字p，并开始它的回合。我们最多可以进行63次回合，需要保证必胜。初始数字n < 1e18。交互题，系统给出对面的操作。
思路 首先我们可以发现一个关键的边界条件，当初始数字中为1的位为1时我们无法对其进行拆解，此时是必败态。我们考虑如何让对手到达这个状态或是这个状态由和转移过来。一个简单的必胜态是有两位数的情况，此时我们拆成两个1位为1的位的数则必胜。继续推广我们发现通过构造所有的为1的位为偶数时都是必胜态，奇数都是必败态，具体证明如下，对于一个偶数个位为1的数我们一定可以把其拆成两个为1的位为奇数的数，而对于为1的位为偶数的数我们无论怎么拆都是一奇数位 ...
D. Turtle and Multiplication题目翻译 题目给我们一个数字n，我们需要构造一个长度为n的数组，满足以下条件，数组中的所有元素属于[1, 3e5]，数组中没有两个相邻的元素的乘积相同，数组中不同的数的种类是长度为n下所有合法数组中最小的。输出任意一个符合条件的解。
思路 首先考虑如何在保证没有相邻元素的乘积相同的同时使得数组中不同种类的数的个数最小，我们发现我们选择所有不同的素数来构成数组一定是最优的，因为素数的性质保证了只要相邻两个元素的组成不同乘积就不同，不会出现2 * 6 == 3 * 4这样的情况。x个数组可以组成 （x * (x + 1) ) / 2种不同的组合。我们发现如果从图论的角度抽象这个问题，把不同的两两组合看作两个节点之间的边，那么问题就变成了从这张图中找出一个长度为n的欧拉路，注意到当need（需要的最少素数个数）为奇数时，图一定存在欧拉回路，need为偶数时图中不存在走完所有边的欧拉路，此时我们最少要删除（need - 2）/ 2条边才可以得到一个可以走完所有边的欧拉路，这也就是need个素数时 ...
F2. Counting Is Not Fun (Hard Version)题目翻译 题目给我们一个数字n，代表一个有着n个好对的括号序列，一个好对（i, j) (i < j) 满足s[i] == ‘(‘, s[j] == ‘)’同时去掉i，j两个字符，区间内剩余的子串是一个合法的平衡括号字符串，可以证明对于一个长度位2 * n的括号序列一定有n个好对。题目依次给出n个好对，我们需要计算出前i个好对确定的情况下有多少种符号要求的合法括号字符串（i从0到n）。
思路 与easy版本不同的是hard版的数据到达了3e5，首先我们easy版计算长度为x的合法括号序列的复杂度我们就无法接受，考虑如何快速计算，这实际上就是卡特兰数，我们的平衡度总是大于等于0，最后等于0，相当于不穿过y = x，走到（x / 2， x / 2），我们可以世界使用卡特兰数的组合数学公式来快速计算。
接着考虑如何计算每个前缀好对的可能的括号序列数，注意到easy版我们对每个都进行了重新计算，这实际上没有必要，因为我们新加入一个好对 ...
F1. Counting Is Not Fun (Easy Version)题目翻译 题目给我们一个数字n，代表一个有着n个好对的括号序列，一个好对（i, j) (i < j) 满足s[i] == ‘(‘, s[j] == ‘)’同时去掉i，j两个字符，区间内剩余的子串是一个合法的平衡括号字符串，可以证明对于一个长度位2 * n的括号序列一定有n个好对。题目依次给出n个好对，我们需要计算出前i个好对确定的情况下有多少种符号要求的合法括号字符串（i从0到n）。
思路 首先我们根据题目的定义我们发现对于一个好对[l, r]其中l - 1， r - 1可以填任何合法的括号序列，所以我们需要预处理出长度x时的合法括号序列数，这可以通过dp[len] [diff]来n ^ 2的dp处理出来，状态表示长度为len时平衡度为diff的括号序列数量。然后考虑如何根据确定了的好对来计算可能的括号序列种类。我们发现一个好对就可以把其包含区间的种类给算出来，并且按照定义好对不会相交，只有可能包含，包含时我们可以用来填的空要是还没有确定的，也就是去掉包含的好对 ...
算法竞赛模板
未读123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178#ifdef ShadowDrunk//李超线段树实际上是维护在二维坐标系上插入线段，同时查询x == d时y最大的线段是哪个以及对应的值的变式线段 ...
