星星灰暗着。

星星灰暗着。

你所见的的确是一个NOIp退役OIer的博客。

[AH/HNOI2017]影魔

posted on 2018-04-12 11:00:11 | under 题解 |

感觉这题还挺有意思的,不过估计是HNOI2017第二容易的题目。
UPD:原来的解释有点错误,修正一下。
发现两个限制条件很麻烦,不妨先不考虑右端点元素,找到当前元素 $a[i]$ 的右方后继(可等于 $a[i]$ ) $a[k]$ 。则从 $[i,i+1]$ 到 $[i,k)$ 这些区间都满足p2的贡献要求,而 $[i,k]$ 则满足p1的贡献要求。而每次询问则要求当前区间所有子区间的答案,于是我们可以用线段树维护区间右端点的贡献,更新时将 $(i,k)$ 加上p2,将 $[k,k]$ 加上 $p1$ 就可以了。查询是可以直接查询 $(L+1,R)$ 的答案的。
但是这样还有些问题,我们可能会算入L左边区间的贡献。所以只需要将询问区间按L从大到小排序就可以了。计算后继可以用单调栈来维护,当然你也可以浪费一点复杂度来 $\rm lower\_bound$ 。
至于左边的区间怎么办?将区间和询问反向就可以了。注意反向后询问的变化。
但我们注意到右端点的值可能对答案有影响:比如 $[i,k]$ 这个区间在反向计算时是增加了p2的无意义贡献的。我们要在这里减掉。$
还有就是要开 $\rm long\ long$ 。

// luogu-judger-enable-o2
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cstring>
#define neko 200010
#define chkmax(a,b) ((a)>(b)?(a):(b))
#define f(i,a,b) for(register int i=(a);i<=(b);i=-(~i))
#define rf(i,a,b) for(register int i=(a);i>=(b);i=~(-i))
struct node
{
    int l,r,id;
}q[neko];
int n,m;
typedef long long ll;
ll p1,p2,a[neko],ans[neko],stk[neko],suc[neko],Sum[neko<<2],Add[neko<<2];
using namespace std;
namespace Seg
{
    #define ori tagl,tagr
    #define mid ((l+r)>>1)
    #define lson root<<1,l,mid
    #define rson root<<1|1,mid+1,r
    #define pushup(root) Sum[root]=Sum[root<<1]+Sum[root<<1|1]
    void pushdown(int root,int l,int r)
    {
        if(Add[root])
        {
            Sum[root<<1]+=1ll*(mid-l+1)*Add[root];
            Sum[root<<1|1]+=1ll*(r-mid)*Add[root];
            Add[root<<1]+=Add[root];
            Add[root<<1|1]+=Add[root];
            Add[root]=0;
        }
    }
    ll query(int root,int l,int r,int tagl,int tagr)
    {
        if(l>=tagl&&r<=tagr)return Sum[root];
        pushdown(root,l,r);
        ll tmp=0;
        if(tagl<=mid)tmp+=query(lson,ori);
        if(tagr>mid)tmp+=query(rson,ori);
        return tmp;
    }
    void update(int root,int l,int r,int tagl,int tagr,int x)
    {
        if(l>=tagl&&r<=tagr){Add[root]+=x,Sum[root]+=(r-l+1)*x;return;}
        pushdown(root,l,r);
        if(tagl<=mid)update(lson,ori,x);
        if(tagr>mid)update(rson,ori,x);
        pushup(root);
    }
    #undef ori
    #undef mid
    #undef lson
    #undef rson
}
namespace Cons
{
    using namespace Seg;
    bool cmp(node a,node b)
    {return a.l<b.l;}
    void init()
    {memset(Sum,0,sizeof(Sum)),memset(Add,0,sizeof(Add));}
    void calc()
    {
        int top=0,now=m;stk[0]=n+1;
        init();
        rf(i,n,1)
        {
            while(top&&a[stk[top]]<a[i])--top;
            suc[i]=stk[top];
            stk[++top]=i;
        }
        rf(i,n,1)
        {
            if(suc[i]>i)update(1,1,n+1,i+1,suc[i],p2),update(1,1,n+1,suc[i],suc[i],p1-2*p2);
            while(q[now].l==i)ans[q[now].id]+=query(1,1,n+1,i+1,q[now].r),--now;
        }
    }
}
using namespace Cons;
int main()
{
    scanf("%d%d%lld%lld",&n,&m,&p1,&p2);
    f(i,1,n)scanf("%lld",&a[i]);//a[n+1]=1e9;
    f(i,1,m)scanf("%d%d",&q[i].l,&q[i].r),q[i].id=i;
    sort(q+1,q+m+1,cmp),calc();
    reverse(a+1,a+n+1);
    f(i,1,m)swap(q[i].l,q[i].r),q[i].l=n-q[i].l+1,q[i].r=n-q[i].r+1;
    sort(q+1,q+m+1,cmp),calc();
    f(i,1,m)printf("%lld\n",ans[i]);return 0;
}