【拾题杂谈】LuoguP3709 [AHOI2013] 作业
题面：[AHOI2013] 作业题目描述此时己是凌晨两点，刚刚做了 Codeforces 的小 A 掏出了英语试卷。英语作业其实不算多，一个小时刚好可以做完。然后是一个小时可以做完的数学作业，接下来是分别都是一个小时可以做完的化学，物理，语文……小 A 压力巨大。
这时小 A 碰见了一道非常恶心的数学题，给定了一个长度为 $n$ 的数列和若干个询问，每个询问是关于数列的区间表示数列的第 $l$ 个数到第 $r$ 个数)，首先你要统计该区间内大于等于 $a$，小于等于 $b$ 的数的个数，其次是所有大于等于 $a$，小于等于 $b$ 的，且在该区间中出现过的数值的个数。
小 A 望着那数万的数据规模几乎绝望，只能向大神您求救，请您帮帮他吧。
输入格式第一行两个整数 $n,m$
接下来 $n$ 个不超过 $10^5$ 的正整数表示数列
接下来 $m$ 行，每行四个整数 $l,r,a,b$，具体含义参见题意。
输出格式输出 $m$ 行，分别对应每个询问，输出两个数，分别为在 $l$ 到 $r$ 这段区间中大小在 $[a,b]$ 中的数的个数，以及大于等于 $a$，小于等于 $b$ 的，且在该 ...
【拾题杂谈】LuoguP3709 大爷的字符串题
题面：大爷的字符串题大秦为你打开题目传送门
题目背景在那遥远的西南有一所学校，
/*被和谐部分*/
然后去参加该省省选虐场，
然后某蒟蒻不会做，所以也出了一个字符串题：
题目描述给你一个字符串 $a$，每次询问一段区间的贡献。
贡献定义：
每次从这个区间中拿出一个字符 $x$ ，然后把 $x$ 从这个区间中删除，直到区间为空。你要维护一个集合 $S$。
如果 $S$ 为空，你 rp 减 $1$。
如果 $S$ 中有一个元素不小于 $x$，则你 rp 减 $1$，清空 $S$。
之后将 $x$ 插入 $S$。
由于你是大爷，平时做过的题考试都会考到，所以每次询问你搞完这段区间的字符之后最多还有多少 rp？rp 初始为 $0$。
询问之间不互相影响~
输入格式第一行两个整数 $n$，$m$，表示字符串长度与询问次数。
之后一行 $n$ 个数，第 $i$ 个整数表示给出的字符串的第 $i$ 个字符 $x_i$。
接下来 $m$ 行，每行两个整数 $l, r$，表示一次询问的区间。
输出格式对于每次询问，输出一行一个整数表示答案。
样例 #1样例输入 #1123453 33 3 33 ...
【拾题杂谈】LuoguP1494 [国家集训队] 小 Z 的袜子
题面：[国家集训队] 小 Z 的袜子大秦为你打开题目传送门
题目描述upd on 2020.6.10 ：更新了时限。
作为一个生活散漫的人，小 Z 每天早上都要耗费很久从一堆五颜六色的袜子中找出一双来穿。终于有一天，小 Z 再也无法忍受这恼人的找袜子过程，于是他决定听天由命……
具体来说，小 Z 把这 $N$ 只袜子从 $1$ 到 $N$ 编号，然后从编号 $L$ 到 $R$ 的袜子中随机选出两只来穿。尽管小 Z 并不在意两只袜子是不是完整的一双，他却很在意袜子的颜色，毕竟穿两只不同色的袜子会很尴尬。
你的任务便是告诉小 Z，他有多大的概率抽到两只颜色相同的袜子。当然，小 Z 希望这个概率尽量高，所以他可能会询问多个 $(L,R)$ 以方便自己选择。
然而数据中有 $L=R$ 的情况，请特判这种情况，输出0/1。
输入格式输入文件第一行包含两个正整数 $N$ 和 $M$。$N$ 为袜子的数量，$M$ 为小 Z 所提的询问的数量。接下来一行包含 $N$ 个正整数 $C_i$，其中 $C_i$ 表示第 $i$ 只袜子的颜色，相同的颜色用相同的数字表示。再接下来 $M$ 行，每行两个正整数 ...
【算法介绍】基础莫队
算法简介：赤沙的归嗣莫队算法是由莫涛提出的算法。在莫涛提出莫队算法之前，莫队算法已经在 Codeforces 的高手圈里小范围流传，但是莫涛是第一个对莫队算法进行详细归纳总结的人。莫涛提出莫队算法时，只分析了普通莫队算法，但是经过 OIer 和 ACMer 的集体智慧改造，莫队有了多种扩展版本。莫队算法之所以叫做莫队算法，是因为莫涛是当时的国家队队长，至今莫队算法依然被称为 Mo's Algorithm 。
莫队算法可以解决一类离线区间询问问题，适用性极为广泛。同时将其加以扩展，便能轻松处理树上路径询问以及支持修改操作。
算法试用：贯月的耀锋算法推导：织狩的奉祀莫队算法是一种基于分块的算法。其原理在于对于所有的询问离线，而离线后我们对于每一个询问所在的左右端点的位置进行分块，首先对于左端点排序，如果不在同一个块，我们就可以比较左端点，如果在一起，我们就要看左端点所在块的奇偶性。如果块是奇数，r 按从小到大排序，如果块是偶数，r 从大到小排序，这样我们的 r 指针在处理完这个奇数块的问题后，将在返回的途中处理偶数块的问题，再向 n 移动处理下一个奇数块的问题，优化了 r 指针的移 ...
原神立绘透明png下载方式
《原神》官方网站-全新5.1版本「命定将焚的虹光」上线！
来此网站查看相关角色立绘，右键即可下载png高清图片。
【拾题杂谈】LuoguP4168 [Violet] 蒲公英
题面：[Violet] 蒲公英题目背景亲爱的哥哥：
你在那个城市里面过得好吗？
我在家里面最近很开心呢。昨天晚上奶奶给我讲了那个叫「绝望」的大坏蛋的故事的说！它把人们的房子和田地搞坏，还有好多小朋友也被它杀掉了。我觉得把那么可怕的怪物召唤出来的那个坏蛋也很坏呢。不过奶奶说他是很难受的时候才做出这样的事的……
最近村子里长出了一大片一大片的蒲公英。一刮风，这些蒲公英就能飘到好远的地方了呢。我觉得要是它们能飘到那个城市里面，让哥哥看看就好了呢！
哥哥你要快点回来哦！
爱你的妹妹 Violet
Azure 读完这封信之后微笑了一下。
“蒲公英吗……”
题目描述在乡下的小路旁种着许多蒲公英，而我们的问题正是与这些蒲公英有关。
为了简化起见，我们把所有的蒲公英看成一个长度为 $n$ 的序列 $\{a_1,a_2..a_n\}$，其中 $a_i$ 为一个正整数，表示第 $i$ 棵蒲公英的种类编号。
而每次询问一个区间 $[l, r]$，你需要回答区间里出现次数最多的是哪种蒲公英，如果有若干种蒲公英出现次数相同，则输出种类编号最小的那个。
注意，你的算法必须是在线的。
输入格式第一行有两个整数，分别 ...
【算法介绍】分块思想
算法简介：舍径求真分块思想，是一种把数据分为若干个块，以比正解略劣的复杂度通过题目的思想。适用于一些树形结构可以处理的区间类问题，比如说线段树之类的，分块可以做到基本平替。分块思想主要分为两个部分，完整块和边角块。对于查询的区间，肯定会有边角的至多两个块是不完整的，而不完整的块我们可以尝试暴力，完整的块我们也可以一块一块的数。这样几乎完全暴力的做法，就是分块的优势。
算法试用：忘形炼智算法推导：漫行灵圃那么继续上面的简介内容，我们不难想到，想要让边角小块的暴力与内部整块的枚举达到某种平衡，最为方便的，就是把每个块的大小设为 $\sqrt n$ 。这样就可以保证块的大小以及块的数量都是 $\sqrt n$ ，总体的复杂度自然也是 $O(n\sqrt n)$ 。
那么口说无凭，我们就以动态区间和这道线段树或者树状数组的模板题举例。
首先给出一个序列 $a$ 表示被操作的数组。数组长度为 11 。
a = \big[1,2,-3,4,8,9,-2,3,0,-1,5\big]那么按照上面说的取根号作为块的大小，我们会得到下面的分块情况。每一个下标对应块的起始位置和终止位置一般是 $\left ...
【拾题杂谈】关于一道博弈类双变量贪心题及其思考
题面小A和小B又在通过游戏决一胜负了。
今天他们玩的游戏是这样的，小A拿出了张卡片，每张卡片上都写了一个数 $a$ 。他们每个人轮流交替取走一张卡片，直到取完，小A先取。
记小A取走的卡片的权值和为 $A$ ，小B取走的卡片的权值和为 $B$ ，则小A最终得分为 $|A|-|B|$ 。小A自然希望自己的得分最大，小B则希望其得分最小。
优策略的情况下，小A的最终得分是多少？
$n\le 1e5$
思路不难发现，这就是一道非常经典的博弈类型的贪心题。这里有两个人，小A和小B，他们分别有着自己的决策 $A,B$ ，得分的表现形式为 $|A|-|B|$ ，所以说这是一道双变量的博弈。而处理这种问题的方法之一，就是把双变量转化为单变量。而想要把双变量转化为单变量，我们需要找到不变量。
观察题目，不难发现不变量就是所有元素之和。我们记 $sum = \sum\limits_{i=1}^n a_i$ 。那么当小A取得行动得分 $|A|$ 时，小B的分数自然是 $|sum-A|$ 。最后的答案就等价于 $|A|-|sum-A|$ 。如果我们用函数 $f(A)$ 表示结果，我们可以得到函数 $f(A) ...
【技能演示】和式交换
概念：和式交换所谓和式交换的概念，大家一定都不陌生。小学就学过加法交换律，带符号搬家之说。和式交换就是基于这样的一个原理进行的一个数学技巧。
使用：数学及动规其实数学上的做法大家一定都不陌生，再动态规划上，我们可以使用和式交换的方式优化复杂度。其表现大概为，把一种递推的分组替换为另一种较少的分组用一些和形式的优化使得复杂度降低。
这里以一道题目来看看他的具体用法。
例题：魔法门*来源 MX
给出一个 $n$ 个点，每个点有一个点权 $a_i$ 。任意两个点 $i,j$（ $i<j$ ）之间存在魔法门共 $f(a_i \& a_j)$ 个，$f(x)$ 表示数字 $x$ 在二进制下 $1$ 的数量，$\&$ 表示按位与操作。问从 $1$ 到 $n$ 的方案数量，答案对 $998244353$ 取模。
这个题目首先一定会做的是 $O(n^2)$ 的算法。我们可以设置起点为 $i$ 终点为 $j$ ，写出状态 $dp[i]$ 表示从 $1$ 到 $i$ 的方案数。写出如下代码：
12345for(int i = 1; i <= n; i++) { ...
【拾题杂谈】LuoguP6329 震波
题面大秦为你打开题目传送门
题目背景模板题，没有 $rap$ 。
题目描述在一片土地上有 $n$ 个城市，通过 $n-1$ 条无向边互相连接，形成一棵树的结构，相邻两个城市的距离为 $1$，其中第 $i$ 个城市的价值为 $value_i$。
不幸的是，这片土地常常发生地震，并且随着时代的发展，城市的价值也往往会发生变动。
接下来你需要在线处理 $m$ 次操作：
0 x k 表示发生了一次地震，震中城市为 $x$，影响范围为 $k$，所有与 $x$ 距离不超过 $k$ 的城市都将受到影响，该次地震造成的经济损失为所有受影响城市的价值和。
1 x y 表示第 $x$ 个城市的价值变成了 $y$ 。
为了体现程序的在线性，操作中的 $x$、$y$、$k$ 都需要异或你程序上一次的输出来解密，如果之前没有输出，则默认上一次的输出为 $0$ 。
输入格式第一行包含两个正整数 $n$ 和 $m$ 。
第二行包含 $n$ 个正整数，第 $i$ 个数表示 $value_i$ 。
接下来 $n-1$ 行，每行包含两个正整数 $u$、$v$，表示 $u$ 和 $v$ 之间有一条无向边。
接下来 $m$ ...
