当前位置:首页 > 莫队 > 正文
洛谷P8078秃子酋长[WC2022]
161+

题目大意:给一个长为 $n$ 的排列 $a_1,\dots, a_n$,有 $m$ 次询问,每次询问区间 $[l, r]$ 内,排序后相邻的数在原序列中的位置的差的绝对值之和。

题目背景

5s 512M -O2

题目描述

传说在明斯克航空航天局中,有一名强大的秃子酋长。

秃子酋长法力无边,他的头上没有头发,而且头特别硬,跑得还不慢。

这一天,豌豆射手来到了明斯克航空航天局。

秃子酋长为了考验这一位新人,给他出了这样一道题:

给一个长为 $n$ 的排列 $a_1,\dots, a_n$,有 $m$ 次询问,每次询问区间 $[l, r]$ 内,排序后相邻的数在原序列中的位置的差的绝对值之和。

输入输出格式

输入格式

第一行两个数表示 $n, m$;

之后一行 $n$ 个数依次表示序列 $a$ 中的元素;

之后 $m$ 行,每行两个数 $l, r$ 表示一次查询。

输出格式

对于每次询问,输出一行一个数表示答案。

输入输出样例

输入样例 #1

5 2
5 4 2 3 1
3 4
2 5

输出样例 #1

1
5

说明

**【样例解释】**

第一个询问,$2,3$ 排序后为 $2,3$,在原序列中的位置为 $3,4$,相邻元素在原序列中位置差的绝对值之和为 $|3 – 4| = 1$。

第二个询问,$4, 2, 3, 1$ 排序后为 $1, 2, 3, 4$,在原序列中的位置为 $5, 3, 4, 2$,相邻元素在原序列中位置差的绝对值之和为 $|5 – 3| + |3 – 4| + |4 – 2| = 5$。

**【数据范围】**

对 $10\%$ 的数据,$n, m \leq 10^3$;
对另外 $10\%$ 的数据,$n, m \leq 5 \times 10^4$;
对另外 $10\%$ 的数据,$n, m \leq 10^5$;
对另外 $10\%$ 的数据,$n, m \leq 2 \times 10^5$;
对另外 $20\%$ 的数据,$|a_i – i| \leq 10$;
对另外 $20\%$ 的数据,$m=\dfrac{n(n-1)}{2}$;
对其余数据,无特殊限制。

对于 $100\%$ 的数据,满足 $1 \leq n, m \leq 5\times 10^5$,$1 \leq a_i \leq n$,$a_i$ 互不相同,$1 \leq l \leq r \leq n$,所有数值为整数。

解题思路

莫队:将区间的数字逐个放入set中,边插入边维护答案。新增的数字在两端,只需要增加差值;否则,需要先减少两边数字差值,再加上自己与两边数字的差值之和,时间复杂度$O(n\sqrt{n}log_2n)$。

回滚莫队:数组插入是O(n)的,但是删除是O(1)的,我们可以尝试将插入操作改为删除操作。预处理好[1, n]的答案,对于每一种块,左端点的移动是根号的,右端点的移动我们让他递减,这样就可以实现右端点删除之和为O(n)。左端点删除和回滚都是根号的,执行至多m次。遇到新的块根号次,初始化每次O(n),用内存函数速度稍快。总的时间复杂度是$O(n\sqrt{n}+m\sqrt{n})$。

程序实现

洛谷P8078秃子酋长[WC2022]:等您坐沙发呢!

发表评论

您必须 [ 登录 ] 才能发表留言!