题目描述给定一个长度为\(n\)的正整数数组\(A\)，其中所有数从左至右排成一排。你需要将\(A\)中的每个数染成红色或蓝色之一，然后按如下方式计算最终得分：设\(C\)为长度为\(n\)的整数数组，对于\(A\)中的每个数\(A_i\)（\(1\leqi\leqn\)）：如果\(A_i\)左侧没有与其同

Solution单次二分：二分时间，做这个时间前的所有操作，然后线性统计。注意到可以整体二分，直接整体二分是\(O(n\log^2n)\)。考虑扫描序列，用线段树维护每个时间段内该位置的增加值，差分一下可以实现。将这棵线段树持久化一下，一个国家所有位置同时二分即可\(O(n\logn)\)，可惜空间太

题目描述给定一个\(n\timesm\)的正整数矩阵，求其中最大的满足其中不存在两个位置数值相等的子矩阵大小。\(1\leqn,m\leq400\)。本题有多种做法，而你需要寻找常数最小的做法才能通过本题。solution链表+双指针枚举上边界，逐渐下移下边界，枚举左边界，尝试双指针获得右边界

对于这种树上路径统计问题，一个经典解法就是点分治。如果没有两个限制，还是很简单的，对于单个限制，使用树状数组来解决就行了。但是这道题目要求两个限制，有点像二维偏序，但不完全是。可以说是分成了几个段，每个段之间求二维偏序，而要求段内不能产生贡献。如果这么表述这个问题的话，那就

[ICPC2021NanjingR]AncientMagicCircleinTeyvat设\(f_x\)表示钦定至少有\(x\)条边的四元子图个数，由容斥我们有一条边都没有的子图个数是\(f_0-f_1+f_2-f_3+f_4-f_5+f_6\)，而所有边都有的个数就是\(f_6\)。作差之后只需要求\(f_0,f_1,f_2,f_3,f_4,f_5\)。子图计数只

[ICPC2021NanjingR]AncientMagicCircleinTeyvat设\(f_x\)表示钦定至少有\(x\)条边的四元子图个数，由容斥我们有一条边都没有的子图个数是\(f_0-f_1+f_2-f_3+f_4-f_5+f_6\)，而所有边都有的个数就是\(f_6\)。作差之后只需要求\(f_0,f_1,f_2,f_3,f_4,f_5\)。子图计数只

P5324[BJOI2019]删数转化条件+线段树由于值域不大，并且删数操作跟序列顺序无关，只和每个数的出现次数有关，考虑在值域上分析删数操作。发现对于每一个值\(i\)可以抽象为覆盖了\([i-buc_{i}+1,i]\)的区间。要使数列删空，就要让\([1,n]\)被填满。这样我们就会发现答案就是\([

题目链接点击打开链接题目解法首先只有在一个强联通分量里的点对才可能合法，因此我们这里说的图默认为强联通图但是上面的条件成立只需要满足\(k\gen\)，考虑用好\(k\)可以认为是极大的性质所以说我们可以通过图中所有的环\(+\)路径来凑出\(k\)不难发现，所有的环能构成的

其实这个想法早就有了,奈何应用实在不多.这个存图方法可以以较小的常数(自以为吧),达到约等于vector存图的访问连续性.使用了一些计数排序的思想.namespacegraph{usinge_ifo=int;int_buc[maxn],*buc=_buc+1;//if0indexstd::vector<std::pair<int,e_ifo>>H;e_ifoE[ma

题目描述你需要计算一个函数\(F(x,y)\)，其中\(x,y\)是两个正整数序列。boolF(std::vector<int>x,std::vector<int>y){if(W(x).size()!=W(y).size())returnfalse;if(W(x).size()==1)returntrue;returnF(p(x),p(y))&&F(s(x),s(y));}\(W

题如其名，确实挺经典的。我们称边权在输入中给定的边为特殊边，其它边为平凡边。称特殊边涉及到的点为特殊点，其它点为平凡点。显然，对于连续的若干平凡点\([l,r]\)，他们内部的最优连边方式就是连成一条链，花费\(r-l\)的代价。我们先把这样的代价加到答案中，然后将极长连续平凡点缩成

莫队板子。类似于小B的询问，在移动指针过程中，维护每个数出现次数\(cnt_i\)，同时维护\(\sum\binom{cnt_i}{3}\)即可。取序列分块块长\(B=\frac{n}{\sqrt{m}}\)，有最优

点分治适用于处理大规模的无修改的树上路径信息。钦定一个点作为根节点，路径有且仅有两种情况：1.经过根节点，即由两颗子树构成2.不经过根节点，即只在根节点的一颗子树之中

二维猫树分治版题考虑用一条切割线划分矩形，并统计经过该线的圈。假设线是竖着切的，那么只需分别统计左右两边匚的数量即可。记\(L_{i,j},R,U,D\)分别表示左/右/上/下

做题时间：2022.10.15\(【题目描述】\)给定一个长度为\(n(2\leqn\leq10^5)\)的序列，把他分成\(k(2\leqk\leq\min(n,20))\)个子段，每个子段的花费是其中相同元素的对

沝黑。首先这种统计路径的问题一般联想点分治，然后考虑如何处理经过一个点\(u\)的路径。考虑有一个点\(p\inu\)的子树，然后记录路径\(p\tou\)和路径\(u\top\)的