线段树分治可以将“一段时间”的条件统筹处理。一种理解方法是考虑暴力，在每个时间点将当前状态调整出来，线段树分治做的事情相当于将一段时间内都有效的信息统一处理，当这个信息不再满足的时候就撤销。具体地，若一个条件（通常是可以用并查集维护的）在时间\([l,r]\)内有效，我们可以对

水群时看到了，记一下。形式地，设查询的信息构成半群。分块，将信息分成\(B\)块，则每块长度为\(\dfrac{n}{B}\)。考虑暴力处理每块的前缀、后缀答案，暴力处理每个整块间的答案，取\(B=O(\sqrt{n})\)，预处理复杂度是\(O(n)\)的。现在，对于跨越整块的询问，我们可以\(O(1)\)查询，但是，

CF2037E题解题意给定一个长度为\(n\)的\(01\)串，定义\(f(l,r)\)为\(l\)到\(r\)区间内\(01\)子序列的数量，通过最多\(n\)次交互，确定这个\(01\)串的构成。分析可以从莫队的思想，也就是增量，来思考如何解决。如果说我们已经知道了\(f(l,r)=ans\)，接下来我们询问

做题P4775一道用线段树合并处理直径的题目。一个小技巧就是树上线段树先合并再插入常数会小很多。P10831最开始信息：通过Ramsey引理知6点必有询问出0或3，以这三点\(A,B,C\)为基础构造。如何求一边是否存在？预处理\(i\toA,B,C,\foralli\)的信息之后直接询问即可。考

Problem给出1~n每个数2个，共2n个，然后拿走3个不相等的数，可以进行最多150次询问，可以得到值为l-r的所有数的异或和，请你最后给出这3个数。其中\(3\len\le10^{18}\)Solve不建议做法：分治，不断给1~n区间分块原因：需要进行的询问在不优化的情况下能达到200左右，需要不断找地方优化，且

阶段1考虑我们每次随机删除两个然后询问，若中位数为\(\frac{n}{2},\frac{n}{2}+1\)称被删除的两个为基准数，用\(v_1,v_2\)代表。每次询问得到解的概率约为\(\frac{1}{2}\)。发现基准数一定一个\(<\frac{n}{2}\)一个\(>\frac{n}{2}+1\)，且对于一次四个数的询问\(x

Lightswitches*2600tag：暴力枚举，meetinmiddle题目描述有\(n(1\le1000)\)盏灯和\(s(1\les\le30)\)个开关，每个开关能控制一些灯，并改变这些灯的状态。接下来有\(d(1\led\le1000)\)次询问，每次询问给出\(k_i\)盏亮着的灯，询问将所有灯全部熄灭最少需要按几次开关。

有很多数数题都可以转化为二维数点模型。将一些二元信息视作平面上的若干个点，查询即数一个矩形中有多少个点/点的权值之和等信息。那么这很明显是DS题（或者至少要上DS优化一下）。我们来想想怎么处理矩阵查询。离线离线的时候做法很多。但基本都有一个共性：把询问差分，转化为前缀信

20240923分块莫队专题回滚莫队回滚莫队适用于添加与删除中有一种较为困难的情况。大致思想如下：对原序列分块，将询问按左端点所在块编号排序，同一块内按右端点排序。对每个块，视情况初始化左右指针，扫一遍询问。先移动右指针到询问右端点，记录当前状态的答案，再将左指针移到询问左端

前几天看到一个看起来挺牛的数据随机下区间点对最优化的做法，没想到还真用上了。好像和官方题解不太一样，先记录一下。题意是区间查询平面最近哈密顿距离点对。先考虑一下全局查询怎么做。我们充分发扬人类智慧，每个点按\(a\)排序，然后从小到大枚举每个点，找下标距离它不超过\(B\)

比赛链接Solved：4/7Upsolved：5/7Rank：447（rated343）D2.Asesino（HardVersion）题意：有n个人，除了一个卧底以外，其他人或者只会说真话，或者只会说谎，且他们知道彼此的身份。卧底只会说谎，但其他人都认为他只会说真话。现在你可以进行若干次询问，每次询问形如问第i个人第j个人是什么

OI记录（持续更新P2568GCD题意：给定正整数\(n\)，求\(1\lex,y\len\)且\(\gcd(x,y)\)为素数的数对\((x,y)\)有多少对(\(n\leq10^7\))题解：注意，可以不用莫比乌斯反演，单纯的欧拉函数便可以解决，首先列出式子：\[\sum_{p\inprime}\sum_{i=1}^{n}\sum_{j=1}^{n}(gcd(i,j)=p)\]

P1972[SDOI2009]HH的项链我知道这是很典的题，但是看提交记录发现我是今年1月做的，居然一点印象也没有。看题解（洛谷第一篇）居然看懂了，比较开心。之前都是随便看看然后就开始贺题解，感觉思考的比较少，这次是看着推导过程写出来了。思路：对于询问多个区间[L,R]中出现不同数字个数，

A大家使用了整体二分+可撤销并查集，倍增等方法...考虑线段树合并。在跑Kruskal时，如果一个询问的两个点在同一个连通块内，那么这个询问就是可回答的，但是可回答不一定要回答，因为如果此后加的边权相同那么其实里面的点还能再往外走。所以在加边时如果新加的边权大于连通块边权，那

学习目标：提升英语口语水平学习内容：英语口语总结练习例如：以下是100句日常交流口语：一、问候与介绍Hello!/你好！（最常见的打招呼用语）Hi!/嗨！（比较随意的打招呼）Goodmorning!/早上好！（上午问候）Goodafternoon!/下午好！（下午问候）Goodevening!/晚上好！（晚上问候）Niceto

题目大意：题目传送门共\(T\)组测试数据，每组数据给定一个字符串\(s\)和\(Q\)次询问，按照特定的赋值方式，每次询问\(l\)到\(r\)间按这样的赋值方式的总和是多少。赋值方式如下：P可得3分p可得2分G可得1分其余字符不得分题目分析：前置知识：前缀和。（没有学过的可以先

TopCoderSRM616ColorfulCoins题意给一套货币，保证任意两种货币存在倍数关系且颜色互不相同。已知货币的币值集合，每次可以询问一个金额，给出货币张数最小的表示方案。问最小的询问次数，使得通过已知信息可以对应货币面值和颜色。分析最大的面值问一个\(\inf\)即可。这时只需要

中山市选2011杀人游戏一个环上的点可以通过询问环上任意一点来确定整个环的状态，有入度的点可以通过询问它之前的点来确定。所以我们先缩点。需要统计出所有入度为\(0\)的强连通分量的个数。注意一个特殊情况，若存在一个强连通分量满足它大小为\(1\)，且它连接到的点的入度都不

MSIAhgdAHAGOOOOAybcsiQOSDhsm.[ARC154D]A+B>C?先看看什么是我们容易得到的：排列的边界情况要么是\(1\)要么是\(n\)，对于\(n\)，我们并不能方便的找到什么性质，但是对于\(1\)，\(1+1=2\not>\operatorname{others}\)，而且\(1\)容易和大于号联系起来。再观察一下询问：可以

nf#34A定义两个长度相等的数列相似，当且仅当每个下标对应值在两个数列中的排名相等。对于一个长\(n\)的排列，定义\(f(A,k)\)表示有多少长\(k\)的排列和\(A\)的至少一个子序列相似。排列\(A\)的值是\(\sum_{k=1}^n[f(A,k)=C_n^k]\)。给出一个排列，有若干位置待定，求值

国庆集训Day12024年10月1日Status:CLOSED\(\def\EZ{\textcolor{#51af44}{\text{EZ}}}\EZ\)表示简单，10分钟内就能想到。\(\def\HD{\textcolor{#3173b3}{\text{HD}}}\HD\)表示中等，能独立想出\(\def\IN{\textcolor{#be2d23}{\text{IN}}}\IN\)表示困难，独立思考能想到

思路设答案为\(a\)，第一次异或的数为\(b\)，第二次异或的数为\(c\)，则可以通过两次询问知道\(a\oplusb\)和\(a\oplusc\)，所以\(b\oplusc=(a\oplusb)\oplus(a\oplusc)\)。因为范围为\([0,2^{14}-1]\)，且每次询问只有\(100\)次，所以可以让第一次询问\(\{1,2,\cdots

Description这是一道交互题。有一棵\(n\)个节点的树，现在要求你通过若干次询问得到这棵树的每一条边连接哪两个点。每次询问你需要指定\(n\)个整数\(d_1,d_2,\ldots,d_n\)，满足\(-1\leqd_i\leqn\)，其中\(1\leqi\leqn\)。每次询问交互库会返回给你一个长度为\(n\)的

23上午whk。辅助角公式。诱导公式。23下午莫队：原序列分块。询问排序：第一关键字为左端点所在块的编号，第二关键字为右端点编号。回滚莫队：适用于增加或删除操作其中一个复杂度较大，但另一个较小的情况。可以做到只使用一种操作。排序后按照左端点的块编号一块一块做。排完

T1我的做法：合并->并查集。类似建Kruskal重构树。询问跑LCA。注意并查集合并要把两个根都变成一个新点的儿子，而不是把一个作为另一个的儿子。（可能类似建[边]（？）Kruskal重构树）要特判询问时\(x=y\)的情况（好像是输出\(0\)）。lzh的做法：连出一棵树，边的边权是