主题

主题

 
   

4540: [Hnoi2016]序列

原题:http://www.lydsy.com/JudgeOnline/problem.php?id=4540

Description

  给定长度为n的序列:a1,a2,…,an,记为a[1:n]。类似地,a[l:r](1≤l≤r≤N)是指序列:al,al+1,…,ar-1,ar。

若1≤l≤s≤t≤r≤n,则称a[s:t]是a[l:r]的子序列。

现在有q个询问,每个询问给定两个数l和r,1≤l≤r≤n,求a[l:r]的不同子序列的最小值之和。

例如,给定序列5,2,4,1,3,询问给定的两个数为1和3,那么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。

Input

  输入文件的第一行包含两个整数n和q,分别代表序列长度和询问数。接下来一行,包含n个整数,以空格隔开,第i个整数为ai,即序列第i个元素的值。接下来q行,每行包含两个整数l和r,代表一次询问。

Output

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

Sample Input

5 5

5 2 4 1 3

1 5

1 3

2 4

3 5

2 5

Sample Output

28

17 

11 

11 

17 

HINT

1 ≤N,Q ≤ 100000,|Ai| ≤ 10^9


个人解法:

回忆了一下之前的莫队做法。

直接搬LJH的博客好了……


博客原文:http://www.cnblogs.com/ljh2000-jump/p/6219889.html

然后自己推导了一下,其实情况大致是这样的:

同样拿右端点添加一个数字为例,:


对算法正确性的证明需要注意一些性质:

  1. p<=last[r]

  2. last[r]与p均为更新Sum的关键字


代码如下:

https://code.csdn.net/snippets/2307525


卡常问题:

如果需要莫队卡常,我们关注的应该是莫队转移的复杂度,而不是其他的预处理之类的……

比方说在转移的时候,计算len用len=floor(log2(r-l+1))就比较危险了。我们可以预处理出所有长度的floor(log2(x)),直接调用。

 
 
评论