[HNOI2017]影魔

题目大意

给定一个长度为 n 的排列，对于一个区间，如果两个端点分别是这个区间的最大值和次大值，有p1的贡献，否则如果其中一个端点是这个区间的最大值，有 p2 的贡献。

现在给你 q 个询问，每次询问一个区间[L,R]，问所有被区间完全包含的区间的贡献和。

1≤n,q≤2×105,1≤p1,p2≤103

题目分析

首先，我们可以考虑把 p1 这种贡献先算在 p2 里面，具体是怎么样呢？

我们将贡献 p2 重定义为：一个区间，如果它有一个端点比这个区间内除了端点的数都大，那么对答案就有一个 p2 的贡献，注意，左端点和右端点可能都对答案有贡献。

这个怎么计算呢？显然我们要正着做一遍反着做一遍来把左右端点的贡献都给求出来，这里只讨论正着做，反着的话你把数组reverse一下，把询问区间翻转一下就一样了。

首先我们用单调栈处理出一个点后面的第一个比它大的数的位置，记为 ri 。然后我们把询问都按照左端点排序，然后从右到左扫描线。扫到一个位置，现在线段树 [i+1,ri] 位置区间加上 p2 ，然后处理挂在这个左端点的所有询问，左端点对于这个询问的贡献就是线段树上 [1,R] （ R 是查询的右端）的和。

这样做，我们能把所有p2都很好地求出来，可是 p1 都被我们当成了两倍的 p2 ，怎么办呢？可以发现，我们枚举作为次大值的左/右端点，那这种区间只会有一个，就是 [i,ri] ，因此我们在做上面扫描线过程中，除了区间加之外，还给位置 ri 单点减去 p1−2p2 就好了。

时间复杂度 O(qlogn) 。

代码实现

#include <algorithm>
#include <iostream>
#include <cstdio>
#include <cctype>

using namespace std;

typedef long long LL;

int read()
{
    int x=,f=;
    char ch=getchar();
    while (!isdigit(ch)) f=ch=='-'?-:f,ch=getchar();
    while (isdigit(ch)) x=x*+ch-'0',ch=getchar();
    return x*f;
}

int buf[];

void write(LL x)
{
    if (x<) putchar('-'),x=-x;
    for (;x;x/=) buf[++buf[]]=x%;
    if (!buf[]) buf[++buf[]]=;
    for (;buf[];putchar('0'+buf[buf[]--]));
}

const int N=;
const int Q=;

struct segment_tree
{
    LL tag[N<<],sum[N<<];
    int size[N<<];

    void ADD(int x,LL delta){sum[x]+=l*delta*size[x],tag[x]+=delta;}

    void clear(int x,int l,int r)
    {
        if (tag[x])
        {
            if (l!=r) ADD(x<<,tag[x]),ADD(x<<|,tag[x]);
            tag[x]=;
        }
    }

    void update(int x){size[x]=size[x<<]+size[x<<|],sum[x]=sum[x<<]+sum[x<<|];}

    void modify(int x,int st,int en,int l,int r,int delta)
    {
        clear(x,l,r);
        if (st==l&&en==r)
        {
            ADD(x,delta),clear(x,l,r);
            return;
        }
        int mid=l+r>>;
        if (en<=mid) modify(x<<,st,en,l,mid,delta);
        else if (mid+<=st) modify(x<<|,st,en,mid+,r,delta);
        else modify(x<<,st,mid,l,mid,delta),modify(x<<|,mid+,en,mid+,r,delta);
        update(x);
    }

    LL query(int x,int st,int en,int l,int r)
    {
        clear(x,l,r);
        if (st==l&&en==r) return sum[x];
        int mid=l+r>>;
        if (en<=mid) return query(x<<,st,en,l,mid);
        else if (mid+<=st) return query(x<<|,st,en,mid+,r);
        else return query(x<<,st,mid,l,mid)+query(x<<|,mid+,en,mid+,r);
    }

    void build(int x,int l,int r)
    {
        tag[x]=;
        if (l==r)
        {
            sum[x]=,size[x]=;
            return;
        }
        int mid=l+r>>;
        build(x<<,l,mid),build(x<<|,mid+,r),update(x);
    }
}t;

LL res[Q];
int stack[N],a[N],R[N];
int top,n,q,p1,p2;

struct qy
{
    int l,r,id;

    bool operator<(qy const x)const{return l<x.l;}
}ask[Q];

void calc()
{
    t.build(,,n+),sort(ask+,ask++q),a[stack[top=]=n+]=n+;
    for (int i=n;i>=;--i)
    {
        for (;top&&a[stack[top]]<a[i];--top);
        R[i]=stack[top],stack[++top]=i;
    }
    for (int i=n,cur=q;i>=;--i)
    {
        t.modify(,i+,R[i],,n+,p2),t.modify(,R[i],R[i],,n+,p1-*p2);
        for (;cur&&ask[cur].l==i;--cur) res[ask[cur].id]+=t.query(,,ask[cur].r,,n+);
    }
}

int main()
{
    freopen("sf.in","r",stdin),freopen("sf.out","w",stdout);
    n=read(),q=read(),p1=read(),p2=read();
    for (int i=;i<=n;++i) a[i]=read();
    for (int i=;i<=q;++i) ask[i].l=read(),ask[i].r=read(),ask[i].id=i;
    calc(),reverse(a+,a++n);
    for (int i=;i<=q;++i) ask[i].l=n+-ask[i].l,ask[i].r=n+-ask[i].r,swap(ask[i].l,ask[i].r);
    calc();
    for (int i=;i<=q;++i) write(res[i]),putchar('\n');
    fclose(stdin),fclose(stdout);
    return ;
}