有一个长为$a$, 值域为$[1,k]$的序列

对于每个询问区间$[l,r]$

$$
\sum^k_{i=1}{c^2_i}
$$

其中$c_i$表示数字$i$在$[l,r]$中出现的次数

莫队是由前国家队队长莫涛发明的

莫队算法的精髓就是通过合理地对询问排序,然后以较优的顺序暴力回答每个询问。处理完一个询问后,可以使用它的信息得到下一个询问区间的答案。(两个边界瞎跳)

考虑这个问题:对于上面这道题,我们知道区间$[1,5]$的答案,就可以求出$[2,6]$每个数的数量

莫队提供了这样一个排序方案:将原序列以$\sqrt{n}$为一块进行分块(分块的大小也珂以调整),排序第一关键字是询问的左端点所在块的编号,第二关键字是询问的右端点本身的位置,都是升序。然后我们用上面提到的“移动当前区间左右端点”的方法,按顺序求每个询问区间的答案,移动每一个询问区间左右端点可以求出下一个区间的答案。

1
return pos[a.l] == pos[b.l] ? a.r < b.r : pos[a.l] < pos[b.l];

这道题目只要分块排序亿下之后

阅读全文

P1081

题目简述

有一排高低不同的城市 城市距离=高度差

A和B自左向右开车旅行(出发点可以变)

A、B的开车风格:

1.A会前往右边距他第二近的城市
2.B会前往右边最近的城市
3.A和B开过的总里程不超过$X$

询问:

1.给定一个$X$ 求出从哪个城市出发 $A$的路程/$B$的路程 最大

2.给定$X_i$和出发城市$S_i$ 求$A$和$B$分别开的距离数

倍增

在没有修改的RMQ问题(区间最值问题) 基于倍增的ST表可以做到$O(1)$查询和$O(nlogn)$预处理

拿最大值来说我们用$Max[i][j]$表示,从$i$位置开始的$2^j$个数中的最大值,例如$Max[i][1]$表示的是$i$位置和$i+1$位置中两个数的最大值(也就是说当前位置是被包含进$2^j$个数去的)

那么转移的时候我们可以把当前区间拆成两个区间并分别取最大值

比如

阅读全文

题目描述

渡渡鸟国的每位国民都有一个长度为 $n$ 的身份证号,身份证号的每一位为 $[1,k]$ 内的一个整数。渡渡鸟国现在要设立若干个服务站,每个服务站有一个长度为 $2$ 的编号,每一位也是 $[1,k]$ 内的一个整数。

对于一只渡渡鸟,设其身份证号为 $s$,其中 $s$ 是一个长度为 $n$ 的字符串。对于一个服务站,设其编号为 $t$,其中 $t$ 是一个长度为 $2$ 的字符串。当且仅当 $t$ 是 $s$ 的子序列时,这只渡渡鸟可以被这个服务站服务。比如 $s=123,t=13$ 时,渡渡鸟可以被服务;而$s=123,t=31$ 时,渡渡鸟不能被服务。

渡渡鸟国王希望建设一些服务站,使得任意一只渡渡鸟都可以被至少一个服务站服务。它想知道最少需要建造多少个服务站。

通过并查集 首先最后要分成(k-1)组 然后求步数即可

题目描述详见 luogu

题目可以说是非常的长,但是读懂之后概括一下大概就是找到一种填写01的方式,使得任意取两条合法(从$(1,1)$向右向下走到右下角)的路径, 右上路径经过的数字连接成的字符串字典序小。

然后就是漫长的手模+找规律

在模拟$3*3$时,第一次模拟出来的结果非常amazing,竟然有144种
在我的理解中,我认为只要是左下-右上走向的线上的数字不递增就可以了
如图

如图$4 \times 4 \times 3 \times 3=144$

但是显然 这是错误的

正确解法:

阅读全文

题目描述
春春幼儿园举办了一年一度的“积木大赛”。今年比赛的内容是搭建一座宽度为$n$的大厦,大厦可以看成由$n$块宽度为$1$的积木组成,第i块积木的最终高度需要是$h_i$
在搭建开始之前,没有任何积木(可以看成nn块高度为$0$的积木)。接下来每次操作,小朋友们可以选择一段连续区间$[l,r]$,然后将第第$L$块到第 $R$ 块之间(含第$L$ 块和第 $R$块)所有积木的高度分别增加$1$。

小MM是个聪明的小朋友,她很快想出了建造大厦的最佳策略,使得建造所需的操作次数最少。但她不是一个勤于动手的孩子,所以想请你帮忙实现这个策略,并求出最少的操作次数。

阅读全文

题目链接

题目描述

小凯手中有两种面值的金币,两种面值均为正整数且彼此互素。每种金币小凯都有 无数个。在不找零的情况下,仅凭这两种金币,有些物品他是无法准确支付的。现在小 凯想知道在无法准确支付的物品中,最贵的价值是多少金币?注意:输入数据保证存在 小凯无法准确支付的商品。

阅读全文