AC. 梦想

frank_c1

[HNOI 2016] 序列

发布于2016年04月20日 | 暂无评论 | 1,003阅读 | 莫队算法

题目描述

给定长度为n的序列:a_1,a_2,...,a_n,记为a[1:n]。类似地,a[l:r] \; (1 \le l \le r \le n)是指序列:a_l,a_{l+1},...,a_{r-1},a_r。若1 \le l \le s \le t \le r \le n,则称a[s:t]a[l:r]的子序列。现在有q个询问,每个询问给定两个数lr(1 \le l \le r \le n),求a[l:r]的不同子序列的最小值之和。例如,给定序列5,2,4,1,3,询问给定的两个数为13,那么a[1:3]6个子序列a[1:1],a[2:2],a[3:3],a[1:2],a[2:3],a[1:3],这6个子序列的最小值之和为5+2+4+2+2+2=17

输入格式

输入文件的第一行包含两个整数nq,分别代表序列长度和询问数。

接下来一行,包含n个整数,以空格隔开,第i个整数为a_i,即序列第i个元素的值。

接下来q行,每行包含两个整数lr,代表一次询问。

1 \le n,q \le 100000,|a_i| \le 10^9

输出格式

对于每次询问,输出一行,代表询问的答案。

题目解析

可以采用莫队算法。我们先考虑怎样从[l,r]转移到[l-1,r]

我们只需要求出左端点为l,右端点在[l,r]的所有子序列的最小值之和。考虑将答案的贡献分类。对于一段区间l,r的询问,若a[p][l,r]中的最小值,则对于任意i \in [p,r]\min{a[l:i]} = p,即对答案的贡献为a[p] \times (r-p+1)

现在还需要求出[l,p)的贡献。我们找到l右边第一个比它小的位置k_1,对于任意i \in [l,k_1),有a[l:i]的最小值是a[l];再找到k_1右边第一个比它小的位置k_2,对于任意i \in [k1,k2),有a[l:i]的最小值是a[k_1]……如此迭代,直到k_i = p。注意到每一段的贡献就是a[k_i] \times (k_{i+1} - k_i)

如果每次询问暴力计算肯定TLE。若每个位置向右边第一个比它小的位置连一条边(不存在就连向root),边权为这一段的贡献,那么就构成了一棵带权有根树。[l,p)的答案就是dist(root,l) - dist(root,p),预处理后可以单次询问O(1)。至于p,可以用RMQO(1)求出。

其它三种转移都是类似的,不再赘述。

RMQ预处理O(n \log n),莫队O(n \sqrt{n}),总时间复杂度O(n \sqrt{n})