当前位置: 代码迷 >> 综合 >> 洛谷3246 [HNOI2016]序列
  详细解决方案

洛谷3246 [HNOI2016]序列

热度:39   发布时间:2023-12-14 16:38:44.0

标签:扫描线,树状数组,单调栈

题目

题目传送门

题目描述

给定长度为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个区间中

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

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

用DP

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

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

发现可以消掉一个维度

f[i]=f[lefti]+(i?lefti)?ai f [ i ] = f [ l e f t i ] + ( i ? l e f t 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;
}