洛谷3246 [hnoi2016]序列

HNOI套路题/数据结构题

阅读全文大概需要 1分钟
本文总阅读量
Posted by yjjr's blog on February 27, 2018

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

题目

题目传送门

题目描述

给定长度为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;
}
本文可以转载,但必须附上原文链接,否则你会终生找不到妹子!!!欢迎关注我的CSDN: ahyjjr