标签：扫描线，树状数组，单调栈
题目
题目描述
给定长度为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。
输入输出格式
输入格式
输入文件的第一行包含两个整数n和q，分别代表序列长度和询问数。接下来一行，包含n个整数，以空格隔开,第i个整数为ai，即序列第i个元素的值。接下来q行，每行包含两个整数l和r，代表一次询问。
输出格式
对于每次询问，输出一行，代表询问的答案。
输入输出样例
输入样例#1
5 5
5 2 4 1 3
1 5
1 3
2 4
3 5
2 5
输出样例#1
28
17
11
11
17
说明
| 1 <=N,Q <= 100000, | Ai | <= 10^9 |
题意
给出长度为N的序列和M次询问
每次询问给定两个端点L，R
询问L，R的子区间内最小值之和
分析
Way1
莫队+DP
枚举元素并计算贡献
设left表示左边第一个比x小的值的位置
所以向右拓展时新增的(r+1)-l+1个区间中
\[左端点在left_{r+1}+1->r+1区间内的价值都是a_{i+1}\] \[现在的问题就是l->left_{r+1}区间的贡献了\]用DP
设f[i][j]表示i->j区间内所得到的贡献
\[f[i][j]=f[i][left_j] + (j-left_j) * a_{j}\]发现可以消掉一个维度
\[f[i] = f[left_i] + (i - left_i)*a_{i}\]然后查询区间的时候取出f[r]-f[l-1]就好了
Way2
扫描线大法吼！我用扫描线写的，因为HNOI2017的影魔也是扫描线，感觉两道题都是同一个套路，我这题就用的这种写法
预处理每个a[i]数作为最左的最小值向左右延伸到的位置Le[i],Ri[i]，则l=Le[i]..i,r=i..Ri[i]的区间的最小值为a[i]
将(l,r)放到二维平面上去，那么询问转化为求一个矩形内部的和
然后就扫描线+树状数组维护即可，常数较大
code
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<algorithm>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define dep(i,a,b) for(int i=a;i>=b;i--)
#define ll long long
#define mem(x,num) memset(x,num,sizeof x)
#define reg(x) for(int i=last[x];i;i=e[i].next)
using namespace std;
inline ll read()
{
ll f=1,x=0;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
const int maxn=1e5+7;
int n,m,a[maxn],Stack[maxn],top=0,le[maxn],ri[maxn],ep=0,p=0;
ll ans[maxn],ks[2][maxn],bs[2][maxn];
void modify(ll*f1,ll*f2,int x,ll f){
if(!x)return;
for(int w=x;w;w-=w&-w)f1[w]+=f;f*=x;
for(int w=x;w<=n;w+=w&-w)f2[w]+=f;
}
inline ll query(ll*f1,ll*f2,int x){
if(!x)return 0;ll re=0;
for(int w=x;w<=n;w+=w&-w)re+=f1[w];re*=x;
for(int w=x-1;w;w-=w&-w)re+=f2[w];
return re;
}
struct ASK{
int l,r,id;
void run(){ans[id]=query(ks[0],ks[1],r)*l+query(bs[0],bs[1],r);}
}qs[maxn];
struct node{
int l,r1,r2;ll k,b;
void run(){
modify(ks[0],ks[1],r2,k),modify(ks[0],ks[1],r1-1,-k);
modify(bs[0],bs[1],r2,b),modify(bs[0],bs[1],r1-1,-b);
}
}sq[maxn<<1];
inline bool operator < (node a,node b){return a.l>b.l;}
inline bool operator < (ASK a,ASK b){return a.l>b.l;}
int main(){
n=read(),m=read();rep(i,1,n)a[i]=read();
rep(i,1,n){
while(top&&a[Stack[top]]>a[i])ri[Stack[top--]]=i-1;
Stack[++top]=i;
}
while(top)ri[Stack[top--]]=n;
dep(i,n,1){
while(top&&a[Stack[top]]>=a[i])le[Stack[top--]]=i+1;
Stack[++top]=i;
}
while(top)le[Stack[top--]]=1;
rep(i,1,n){
sq[ep++]=(node){i+1,i,ri[i],-a[i],1LL*(i+1)*a[i]};
sq[ep++]=(node){le[i],i,ri[i],a[i],1LL*(-le[i])*a[i]};
}
sort(sq,sq+ep);
rep(i,0,m-1)qs[i].l=read(),qs[i].r=read(),qs[i].id=i;
sort(qs,qs+m);
rep(i,0,m-1){
while(p<ep&&sq[p].l>=qs[i].l)sq[p++].run();
qs[i].run();
}
rep(i,0,m-1)printf("%lld\n",ans[i]);
return 0;
}
