4540: [Hnoi2016]序列
Time Limit: 20 Sec Memory Limit: 512 MB
Submit: 1567 Solved: 718
[Submit][Status][Discuss]
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
Sample Output
HINT
1 ≤N,Q ≤ 100000,|Ai| ≤ 10^9
分析：
也许是我比较傻吧， 我把分块那里block[i] = i / tot +1打成了 block[i] = block[i] / tot + 1，超时了半天，调不出来……
题目又是没有修改，只有查询，可以联想到莫队算法。
题目要求是求一个大区间内，每个子区间最小值之和。我们可以看一下，如果已知一个区间[l，r]，那么如果要得到[l，r + 1]，我们会把[r + 1]的数添加进来。当这个数添加进来会多产生r - l + 2个子区间，那么如何处理这个子区间呢，就算是用st表 暴力去查询 这 r - l + 2个区间复杂度结合每一次也是很高的。
我们可以分析一下：如果我们找到[l，r + 1]里面的最小值，它所在位置为k。那么[l，k]这段区间的点为左端点和[r +1]所产生的 k - l + 1个区间都是以[k]所在数为最小值，那么贡献为（k - l + 1） * a[k]，剩下的就是[k + 1，r + 1]这段区间了。
当我们知道一个数i左边第一个小于等于它的数的下标lm[i]，所以[lm[i] + 1，i - 1]中间的值都是大于[i]的数的。所以以[lm[i] +1，i]的数都以[i]的数为最小值。设sumr[i]表示以i为右端点的合法区间的答案，那么sumr[i] = sumr[lm[i]] + （i - lm[i]） * a[i]。发现我们的sumr数组是类似于前缀和的形式，最后我们用sum[r +1] - sum[k]就为[k + 1，r + 1]这段区间答案。
最终一个区间答案为ans = （k - l + 1） * a[k] + sumr[r +1] - sum[k]。
删除同理，在左端点处添加删除只需维护rm[i]和suml[i]。求区间最小值的位置可以用st表，o（nlogn）的转移，o(1）的查询。求一个数左右第一个不大于它的数可以用单调队列，当一个数被另一个数踢出时，这个数离它最近的相应方向上的第一个不大于它的数就为另一个数。再加上莫队算法（nsqrt（n））总时间复制度为o（nlogn + nsqrt（n））
ST表：
类似于动态转移的思想，我们知道区间[l，r]的最小值，就可以推出区间[l，r + 1]的最小值，但是st表运用了倍增的思想（类似lca）。
我们知道了每个数向右2^（j - 1） 的最小值，就能拓展到每个数向右2 ^ j 的最小值。
转移方程为
st[i][j] = min（st[i][j - 1],st[i + (1 << j - 1)][j - 1]）；
具体详见代码
附上AC代码：
# include <iostream>
# include <cmath>
# include <cstdio>
# include <cstring>
# include <algorithm>
using namespace std;
const int N = 2e5 + ;
int block[N],tot,n,m;
struct data{
int l,r,id;
bool operator <(const data & other)const{
if(block[l] == block[other.l])return r < other.r;
return block[l] < block[other.l];
}
}q[N];
int st[N][],a[N],mn[N];
int stack[N],cnt;
int lm[N],rm[N];
long long suml[N],sumr[N],num,ans[N];
int query(int x,int y){
return a[x] < a[y] ? x : y;
}
int Rmq(int L,int R)
{ if(L > R)swap(L,R);
int k = mn[R - L + ];
return query(st[L][k],st[R - ( << k) + ][k]);
}
void updatal(int x,int y,int z){
int pos = Rmq(x,y);
num +=(1ll * (y - pos + ) * a[pos] + sumr[x] - sumr[pos]) * z;
};
void updatar(int x,int y,int z){
int pos = Rmq(x,y);
num +=(1LL * (pos - x + ) * a[pos] + suml[y] - suml[pos]) * z;
};
void Modui(){
int L = ,R = ; num = ;
for (int i = ;i <= m;++i){
while (R < q[i].r) updatar(L,R + ,),R++;
while (L > q[i].l) updatal(L - ,R,),L--;
while (R > q[i].r) updatar(L,R,-),R--;
while (L < q[i].l) updatal(L,R,-),L++;
ans[q[i].id] = num;
}
}
void work(){
cnt = ;
for(int i = ;i <= n;i++){
while(cnt && a[stack[cnt]] >= a[i])rm[stack[cnt--]] = i;
stack[++cnt] = i;
}
while(cnt)rm[stack[cnt--]] = n + ;
for(int i = n;i >= ;i--){
while(cnt && a[stack[cnt]] >= a[i])lm[stack[cnt--]] = i;
stack[++cnt] = i;
}
for(int i = ;i <= n;i++){
suml[i] = suml[lm[i]] + 1LL * (i - lm[i]) * a[i];
} for(int i = n;i >= ;i--){
sumr[i] = sumr[rm[i]] + 1LL * (rm[i] - i) * a[i];
}
}
void init(){
mn[] = -;
for(int i = ;i <= n;i++){
mn[i]=((i & (i-))==) ? mn[i-]+ : mn[i-];
st[i][] = i;
}
for (int j = ;j <= mn[n];j++){
for (int i = ;i + ( << j) - <= n;i++){
st[i][j] = query(st[i][j - ],st[i + ( << j - )][j - ]);
}
}
work();
}
int main(){
scanf("%d %d",&n,&m);tot = sqrt(n);
for(int i = ;i <= n;i++){
scanf("%d",&a[i]);block[i] = i / tot + ;
}
init();
for(int i = ;i <= m;i++){
scanf("%d %d",&q[i].l,&q[i].r);
q[i].id = i;
}
sort(q + ,q + m + );
Modui();
for(int i = ;i <= m;i++){
printf("%lld\n",ans[i]);
}
return ;
}