题目链接
bzoj4540
题目描述
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
题解
这里提供一种 nn√ 的做法。
我们考虑使用莫队算法，当左右端点移动时，只会增加或删除以某个元素开头或结尾的子串。这里我们考虑右端点右移至 r 。那么新增的子串为s[i...r]（l<=i<=r）。我们考虑 l 至r中的最小值 p ，假设他的位置是k，则它对答案的贡献为 (k−l+1)∗p 。我们记 ls[i] 表示 i 的左边第一个比i小的元素的位置。然后我们发现第 r 个元素对答案的贡献是(i−ls[i])∗a[i]，i至 ls[i]+1 中的元素对答案没有贡献。第 ls[i] 个元素对答案的贡献是 (ls[i]−ls[ls[i]])∗a[ls[i]] ，依次列推直到 p 。这样我们可以预处理一个类似前缀和的数组，然后通过rmq可以求出p，这样就可以 O(1) 实现转移了。
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<queue>
#include<vector>
using namespace std;
const int N=;
int stk[N],a[N],rmq[N][],r[N],l[N],Log[N],top,S,n,m,x,y;
long long ans[N],dl[N],dr[N],now;
struct query{
int l,r,id;
friend bool operator <(const query &a,const query &b){
if(a.l/S==b.l/S) return a.r<b.r;
return a.l/S<b.l/S;
}
}q[N];
inline void Read(int &x){
static char c;
int f=;
for(c=getchar();c<'0'||c>'9';c=getchar()) if(c=='-') f=-;
for(x=;c>='0'&&c<='9';c=getchar()) x=x*+c-'0';
x=x*f;
}
int query(int l,int r){
int tmp=Log[r-l+];
if(a[rmq[l][tmp]]<a[rmq[r-(<<tmp)+][tmp]])
return rmq[l][tmp];
else return rmq[r-(<<tmp)+][tmp];
}
void changel(int l,int r,long long k){
int tmp=query(l,r);
now+=k*a[tmp]*(r-tmp+);
now+=k*(dr[l]-dr[tmp]);
}
void changer(int l,int r,long long k){
int tmp=query(l,r);
now+=k*a[tmp]*(tmp-l+);
now+=k*(dl[r]-dl[tmp]);
}
void pretreat(){
for(int i=;i<=n;i++) Log[i]=(int)log2(i);
for(int i=;i<=n;i++){
while(top&&a[stk[top]]>a[i]) r[stk[top--]]=i;
l[i]=a[stk[top]]==a[i]?l[stk[top]]:stk[top];
stk[++top]=i;
}
while(top) r[stk[top--]]=n+;
for(int i=;i<=n;i++) dl[i]=dl[l[i]]+l*(i-l[i])*a[i];
for(int i=n;i;i--) dr[i]=dr[r[i]]+l*(r[i]-i)*a[i];
for(int i=;i<=n;i++) rmq[i][]=i;
for(int i=;(<<i)<=n;i++)
for(int j=;j<=n-(<<i)+;j++)
if(a[rmq[j][i-]]<a[rmq[j+(<<(i-))][i-]])
rmq[j][i]=rmq[j][i-];
else rmq[j][i]=rmq[j+(<<(i-))][i-];
}
int main(){
Read(n); Read(m);
S=(int)sqrt(n);
for(int i=;i<=n;i++) Read(a[i]);
pretreat();
for(int i=;i<=m;i++){
Read(q[i].l); Read(q[i].r);
q[i].id=i;
}
sort(q+,q++m);
x=y=; now=a[];
for(int i=;i<=m;i++){
if(q[i].r>y) while(y!=q[i].r) y++,changer(x,y,);
if(q[i].l>x) while(x!=q[i].l) changel(x,y,-),x++;
if(q[i].l<x) while(x!=q[i].l) x--,changel(x,y,);
if(q[i].r<y) while(y!=q[i].r) changer(x,y,-),y--;
ans[q[i].id]=now;
}
for(int i=;i<=m;i++) printf("%lld\n",ans[i]);
return ;
}