bzoj4540: [Hnoi2016]序列

4540: [Hnoi2016]序列

Time Limit: 20 Sec  Memory Limit: 512 MB
Submit: 1266  Solved: 594
[Submit][Status][Discuss]

Description

　　给定长度为n的序列：a1,a2,…,an，记为a[1:n]。类似地，a[l:r]（1≤l≤r≤N）是指序列：a_l,a_l+1,…,a_r-
1,a_r。若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

 

题解

　　这题一直没过今天发现单调栈写错了……

　　首先我们找出L[i],R[i]表示[L[i],i]和[i,R[i]都是比a[i]大的数，且a[L[i]-1]和a[R[i]+1]都要比a[i]大，这样左端点在[L[i],i],右端点在[i,R[i]]的区间都是以a[i]为最小值。也就是可以认为在二维平面上x坐标是[L[i],i]y坐标是[i,R[i]]的点权值都是a[i],而我们查询的实际上就是二维平面上[l,r][l,r]的矩形权值和。

　　L[i]和R[i]可以一遍单调栈轻松求出来。这样剩下的就是一个矩形加矩形求和的问题了，当然可以主席树来搞，但是觉得写的麻烦的我用了奇怪的办法……

　　首先把询问拆成在(r处询问(l,r)）-(l-1处询问(l,r))，这样询问就是两个求前缀和的操作。用一条扫描线扫过去，矩形拆成加入和删除的删除(l1,l2,r2,+w),(r1+1,l2,r2,-w)。用一颗线段树(sum1)维护当前扫描线上的权值，假如当前扫描线在i的位置，有询问(l,r)，那么首先计算x=sum1(L,R)*(i+1)的值，但是我们发现这样的话，假如矩形加事件发生在l1那么就会多算(1,l1)的部分。同时，如果一个矩形已经结束，我们会少算（l1,r1）的部分。这样我们可以再维护一颗线段树，事件(pos,l,r,w),每次加的权值是pos*w，最后把x-sum2（L,R）就行了。

　　代码比较丑……主要是这个思想对吧……

　　

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#define inf 1000000001
using namespace std;
const int N=200085;
long long F[4*N],Tag[4*N],f[4*N],tag[4*N];
long long  ans[N];
long long  a[N],st[N],L[N],R[N];
struct opr{int id,l,r,ps,dd;}op[2*N];
struct mar{int l,r,dd,ps;long long w;}data[2*N];
int n,m,l,r,tt,tot;
inline long long  read()
{
    int x=0,f=1;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;
}
bool cmp1(mar a,mar b)
{
    return a.ps<b.ps;
}
bool cmp2(opr a,opr b)
{
    return a.ps<b.ps;
}
void INS(int i,int l,int r,int ll,int rr,long long w)
{
    if((ll<=l)&&(r<=rr))
    {
        Tag[i]+=w;F[i]+=w*(long long)(r-l+1);return;
    }
    int mid=(l+r)/2;
    if(ll<=mid)INS(i*2,l,mid,ll,rr,w);if(mid+1<=rr)INS(i*2+1,mid+1,r,ll,rr,w);
    F[i]=Tag[i]*(long long)(r-l+1)+F[i*2]+F[i*2+1];
}
void ins(int i,int l,int r,int ll,int rr,long long w)
{
    if((ll<=l)&&(r<=rr))
    {
        tag[i]+=w;f[i]+=w*(long long)(r-l+1);return;
    }
    int mid=(l+r)/2;
    if(ll<=mid)ins(i*2,l,mid,ll,rr,w);if(mid+1<=rr)ins(i*2+1,mid+1,r,ll,rr,w);
    f[i]=tag[i]*(long long)(r-l+1)+f[i*2]+f[i*2+1];
}
long long ASK(int i,int l,int r,int ll,int rr)
{
    if((ll<=l)&&(r<=rr))return F[i];
    int mid=(l+r)/2;long long tmp=Tag[i]*(long long)(min(rr,r)-max(ll,l)+1);
    if(ll<=mid)tmp+=ASK(i*2,l,mid,ll,rr);if(mid+1<=rr)tmp+=ASK(i*2+1,mid+1,r,ll,rr);
    return tmp;
}
long long ask(int i,int l,int r,int ll,int rr)
{
    if((ll<=l)&&(r<=rr))return f[i];
    int mid=(l+r)/2;long long tmp=tag[i]*(long long)(min(rr,r)-max(ll,l)+1);
    if(ll<=mid)tmp+=ask(i*2,l,mid,ll,rr);if(mid+1<=rr)tmp+=ask(i*2+1,mid+1,r,ll,rr);
    return tmp;
}
int main()
{
    int n=read(),m=read();
    for(int i=1;i<=n;i++)a[i]=read();
    a[0]=-inf;
    int top=0;st[0]=0;
    for(int i=1;i<=n;i++)
    {
        while(a[st[top]]>=a[i]){L[st[top]]=st[top-1]+1;R[st[top]]=i-1;top--;}
        st[++top]=i;
    }
    while(top){L[st[top]]=st[top-1]+1;R[st[top]]=n;top--;}
    for(int i=1;i<=n;i++)
    {
        if(L[i]<=R[i])
        {
            data[++tt].w=a[i];data[tt].l=L[i];data[tt].r=i;data[tt].ps=i;data[tt].dd=1;
            data[++tt].w=a[i];data[tt].l=L[i];data[tt].r=i;data[tt].ps=R[i]+1;data[tt].dd=-1;
        }
    }
    sort(data+1,data+tt+1,cmp1);
    for(int i=1;i<=m;i++)
    {
        l=read();r=read();
        op[++tot].id=i;op[tot].l=l;op[tot].r=r;op[tot].ps=r;op[tot].dd=1;
        op[++tot].id=i;op[tot].l=l;op[tot].r=r;op[tot].ps=l-1;op[tot].dd=-1;
    }
    sort(op+1,op+tot+1,cmp2);int j=1;
    for(int i=1;i<=tot;i++)
    {
        while((data[j].ps<=op[i].ps)&&(j<=tt))
        {
            long long now=data[j].ps;long long w=now*(long long)data[j].w;
            INS(1,1,n,data[j].l,data[j].r,w*data[j].dd);
            ins(1,1,n,data[j].l,data[j].r,data[j].w*data[j].dd);
            j++;
        }
        long long w;
        w=ask(1,1,n,op[i].l,op[i].r)*(long long)(op[i].ps+1);
        w=w-ASK(1,1,n,op[i].l,op[i].r);
        ans[op[i].id]+=w*op[i].dd;
    }
    for(int i=1;i<=m;i++)printf("%lld
",ans[i]);
    return 0;
}