标签：扫描线，树状数组，单调栈

题目

题目传送门

题目描述

给定长度为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

输出样例#1

说明

1 <=N,Q <= 100000,|Ai| <= 10^9

题意

给出长度为N的序列和M次询问

每次询问给定两个端点L，R

询问L，R的子区间内最小值之和

分析

Way1

莫队+DP

枚举元素并计算贡献

设left表示左边第一个比x小的值的位置

所以向右拓展时新增的(r+1)-l+1个区间中

左 端 点 在 l e f t r + 1 + 1 ? > r + 1 区 间 内 的 价 值 都 是 a i + 1

$左端点在left_{r+1}+1->r+1区间内的价值都是a_{i+1}$

现 在 的 问 题 就 是 l ? > l e f t r + 1 区 间 的 贡 献 了

$现在的问题就是l->left_{r+1}区间的贡献了$

用DP

设f[i][j]表示i->j区间内所得到的贡献

f [i] [j] = f [i] [l e f t j] + (j ? l e f t j) ? a j

$f[i][j]=f[i][left_j] + (j-left_j) * a_{j}$

发现可以消掉一个维度

f [i] = f [l e f t i] + (i ? l e f t i) ? a i

$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;
}

洛谷3246 [HNOI2016]序列

题目