描述称某个序列 B={b1​,b2​,⋯,bn​} 是另一个序列 A={a1​,a2​,⋯,am​} 的拓展当且仅当存在正整数序列 L={l1​,l2​,⋯,lm​}，将 ai​ 替换为 li​ 个 ai​ 后得到序列 B。例如，{1,3,3,3,2,2,2} 是 {1,3,3,2} 的拓展，取 L={1,1,2,3} 或 {1,2,1,3}；而 {

计算复杂度复杂度在算法竞赛中对算法的选择有很大的帮助，利用复杂度可以简化思考，并帮助得到正确的算法。一般来讲，将基础的运算操作都当成常数复杂度即\(O(1)\)，所以实际上在考虑的问题就是这种基础运算操作在数据规模极大的情况下的运算次数。常见的复杂度有对数多项式，也就是常

E将所有的下标作为点，建一张无向图。当且仅当可以询问\([l,r]\)时，在点\(l\)和\(r+1\)之间连一条边。可以发现能求出\([L,R]\)的和等价于\(L\)与\(R+1\)连通，且最少询问次数等于两点间最短路径边数。具体实现是容易的。F边权很小，提示我们可以暴力枚举和替换边。开

题目链接P1119灾后重建先读题意，就是求在\(t\)时间时当前\(a\)到\(b\)的最短路，并且当前\(a\)和\(b\)村都必须重建完毕。即然一两点间距离。再看一眼数据范围，可以知道需要用到Floyd算法。比较暴力的，可能会用\(n\)次Floyd把每次时间的两点间距算出，但这样是\(O(n^

[HDK-NRC]SqenParadox题目描述给定一个长度为\(n\)的数列\(S\).询问在给定区间\([l,r]\)内最长的没有重复元素的区间长度.输入格式第一行两个整数\(n,m\).第二行\(n\)个整数，描述数列\(S\).随后\(m\)行，每行一个询问.输出格式\(m\)行，请你对每个询问操作输

异或最大值，考虑线性基；树上路径问题，考虑点分治于是不难得到，在某一次分治的时候，处理lca为当前根的所有询问。具体地，求出每个点到当前根的线性基，然后对于一对点，暴力合并两个线性基（也就是两个向量组的并集的极大无关组等于两个向量组的极大无关组的并集的极大无关组）即可这道题目显然

整体二分动态排名每次二分复杂度\(O(n\logV)\)，问题瓶颈在于有多次询问整体二分一种离线算法，将多个询问一起处理：条件问询可以二分修改之间互不影响修改对答案的贡献和判定次数，时间无关贡献满足结合律，交换律，可加性算法流程核心函数，处理一个区间的询问，他们的

题目描述亲爱的哥哥：你在那个城市里面过得好吗？我在家里面最近很开心呢。昨天晚上奶奶给我讲了那个叫「绝望」的大坏蛋的故事的说！它把人们的房子和田地搞坏，还有好多小朋友也被它杀掉了。我觉得把那么可怕的怪物召唤出来的那个坏蛋也很坏呢。不过奶奶说他是很难受的时候才做出这样

[Violet]蒲公英题目背景亲爱的哥哥：你在那个城市里面过得好吗？我在家里面最近很开心呢。昨天晚上奶奶给我讲了那个叫「绝望」的大坏蛋的故事的说！它把人们的房子和田地搞坏，还有好多小朋友也被它杀掉了。我觉得把那么可怕的怪物召唤出来的那个坏蛋也很坏呢。不过奶奶说他是很难受

简介：远看是莫队（\(r\)），近看是暴力（\(l\)，以及左右端点在同一块）。还记得普通莫队里面怎么说的吗？注意两个操作有时候会西掉一个，有时候还要在数据结构上操作，但这不在这篇文章的范围内。所以，这篇文章就会讲述如何应对“两个操作西掉一个”的情况。删除西掉了（更加常见）和正常莫队的排

主要思想：把多个询问一起解决（一次二分同时处理多个询问，确实顾名思义）记\([l,r]\)为答案的值域，\([L,R]\)为答案的定义域，\(mid=(l+r)/2\)。（也就是说求答案时仅考虑下标在\([L,R]\)内的操作和询问，这其中询问的答案在\([l,r]\)内）我们首先把所有操作按时间顺序存入数组中，然

原题链接题解莫队算法是局限性非常大的优化，离线+无修改，它通过邻近区间修改复杂度为\(O(1)\)的特性让区间排序，然后再做修改，排序的规则是按块排序，然后左端点\(l\)在一个块里的按右端点排序code#include<bits/stdc++.h>usingnamespacestd;inta[50005];structnode{

目录普通莫队初遇——从暴力谈起困境——乱跑的指针优化——顺路而为之带修莫队参考资料普通莫队初遇——从暴力谈起我们通过一道例题来讨论普通莫队。题目链接。观察数据范围，一个很直接的想法是：开一个数组\(cnt\)，\(cnt_i\)表示在询问的区间内数字\(i\)出现的次数。对于

来介绍一下整体二分。整体二分需要满足一下条件：问题之间独立可以离线具有单调性答案贡献可合并我们通过几个例子，通俗的理解这个算法。问题\(1\)给定\(n\)个数，求第\(k\)小。我们思考这个问题怎么做。不用排序，显然，答案具有单调性。那么，我们可以二分一个答案，判断

设区间端点为\(l,r\)，分点为\(lmid,rmid\)一个naive的做法是取三等分点，询问\(2n\)次区间长度变为\((\frac{2}{3})^{n}\)一个不那么naive的做法是取\(mid,mid+eps\)，询问\(2n\)次区间长度变为\((\frac{1}{2})^{n}\)。某些时候二分差分值更方便不妨设本轮迭代后区间变

[AirConditioner]题意简述题目链接。给定一个整数\(n\)，每秒钟可以选择使\(n\)增加\(1\)或减少\(1\)或不改变，有\(M\)个询问，对于第\(i\)个询问，给定\(t_i,l_i,r_i\)，表示询问在第\(t_i\)秒时，是否有\(n\in[l_i,r_i]\)。如果能满足所有的询问，输出YES，否则输出NO。

莫队个人理解：这是一种较为暴力的算法，适用于解决维护序列区间操作的问题。主要思想：把所有的操作离线，按某种方式重新排序。操作过程中不断转移当前区间的答案。(\([L,R]\Rightarrow[L\pm1,R\pm1]\))希望转移的复杂度尽量的小（\(O(n\sqrt{m})\)）01-普通的莫队（无修改

为什么QOJ上其他人都爆标还原了整颗树，而只有我傻傻改标算。是不是做这道题的除了我都有脑子。感觉像是完全对着硬idea出的，所以正常人做题想法根标方向完全不一样，但是涉及到的技巧都还是挺有用的哈！题意大概是有一颗\(2n\)个点的树，你得知了前\(n\)个点构成的虚树形态，然

有一次使用VSCode重命名一个Python文件时，VSCode询问“扩展‘Python’希望通过移动此文件来进行重构更改”。当时没有多想，选中“不再提问”之后就点了“确定”。结果后来后悔，觉得在进行更改之前应该先检查一下更改的内容。于是想要重置这个“不再询问”的选项。结果始终没有

2024-03-14Riddle继续做上次没做出来的题2-SAT限制是如果一个点不选，那么与它相连的所有点都必须选如果一个点选了，那么和他在同一个部分的所有点都不能选对于边的限制直接建但是“部分”的限制直接建图是\(O(n^2)\)的优化方法是前缀优化建图对于每一个部分，用\(a_i

题意给定\(N\)个二维平面上的点\((X_i,Y_i)\)与\(Q\)组询问，每组询问给出一条直线\(Y=A_iX+B_i\)，问有多少个点在直线上方（或者在直线上）。也就是询问有多少个\((X_i,Y_i)\)，满足\(Y_i\geA_j\timesX_i+B_j\)。题解首先这个式子是\(A\timesX+B\leY\)，移项

好题啊。题意给定\(n\)个二元组\((x_i,w_i)\)，保证\(x\)升序。有\(m\)个询问\([l,r]\)，对于每个询问求出：\[\min\limits_{l\lei<j\ler}(x_j-x_i)\cdot(w_i+w_j)\]题解一个精妙的结论：设\(L_i\)表示\(i\)左边第一个满足\(w_j\lew_i\)的\(j\)，\(R_

2.11ARC171E.Rookhopper'sTourtodo。2.14NFLS模拟.发讲义原题：UR#7.水题走四方。2.15NFLS模拟.达拉然的废墟题意：\(T\)次询问，每次给定正整数\(n,k\)，定义一个长为\(2n\)的排列\(p\)是好的，当且仅当\(p_2<p_4<\dots<p_{2n}\)。定义一个方案是将一个好的排列\(

\(\texttt{link}\)题意数轴上有\(n\)个点，每个点有属性\(a_i\)，在第\(i\)个点可以花费\(1\)的步数移动至\([i,i+a_i]\)中任意一个点。定义一次操作为选出一个\(i\)，使\(a_i\getsa_i+1\)。\(q\)组询问，每次给出\(l,r,k\)，求有\(k\)次操作机会时，从第\(l\)个点走到

这里会记一些不那么基础的RMQ算法，同时也会向外拓展到增量法规建笛卡尔树之类的东西。首先是基础的RMQ，静态可以用ST表做到\(O(n\logn)-O(1)\)，动态可以用线段树做到\(O(n)-O(\logn)\)，当然还有一些奇技淫巧可以用ST表维护特殊的动态RMQ。现在来看不基础的。询问区间定