P3722 [AHOI2017/HNOI2017]影魔

2018-10-10 15:48:15


题意:给出一个 $1$ 到 $n$ 的排列 $a$ ,对于一对 $i,j(1<=i<j<=n)$ ,

若对于任意 $i<k<j$ ,都有 $a[k]<min(a[i],a[j])$ ,那么价值为 $p1$

令 $c=max\left\{a_k,k∈(i,j)\right\}$ ,若 $min(a_i,a_j)<c<max(a_i,a_j)$ ,那么价值为 $p2$

多组询问所有满足 $l<=i<j<=r$ 的 $(i,j)$ 的价值之和


树状数组(线段树)

离线处理

首先预处理出 $i$ 左边右边第一个大于 $a_i$ 的位置

分别记为 $L_i,R_i$

这个可以用单调栈实现

那么可以发现 $i$ 的贡献:

  • 对于左端点在 $L_i$ ,右端点在 $R_i$ 的区间,有 $p1$ 的贡献

  • 对于左端点在 $[L_i+1,i-1]$ ,右端点在 $R_i$ 的区间,有 $p2$ 的贡献

  • 对于左端点在 $L_i$ ,右端点在 $[i+1,R_i-1]$ 的区间,有 $p2$ 的贡献

把询问排好序, $i$ 从 $1$ 到 $n$ 扫

  • 扫到 $L_i$ 时,统计区间 $[i+1,R_i-1]$ 的贡献

  • 扫到 $R_i$ 时,统计 $L_i$ 和区间 $[L_i+1,i-1]$ 的贡献

处理询问的时候用双指针,边修改边统计

对于一个询问的区间 $[l,r]$ ,在扫到 $l-1$ 时记录这个区间的贡献 $sum1$ ,扫到 $r$ 时记录这个区间的贡献 $sum2$ ,那么答案就是 $sum2-sum1$ 了

#include<cstdio>
#include<cstring>
#include<cctype>
#include<algorithm>
#define reg register
using namespace std;
typedef long long ll;
const int N=2e5+5;
struct Q
{
    int l,r,x,id,val;
    inline friend bool operator < (Q a,Q b) {return a.x<b.x;}
}q[N<<1],p[N*3];
int n,m,p1,p2,cnt,a[N],stack[N],top,L[N],R[N];
ll c1[N],c2[N],ans[N];
inline int read()
{
    int x=0,w=1;
    char c=getchar();
    while (!isdigit(c)&&c!='-') c=getchar();
    if (c=='-') c=getchar(),w=-1;
    while (isdigit(c))
    {
        x=(x<<1)+(x<<3)+c-'0';
        c=getchar();
    }
    return x*w;
}
inline int lowbit(int x){return x&(-x);}
inline void add(int x,ll k){for (reg int i=x;i<=n;i+=lowbit(i)) c1[i]+=k,c2[i]+=(ll)x*k;}
inline ll query(int x,ll res=0){for (reg int i=x;i;i-=lowbit(i)) res+=(ll)(x+1)*c1[i]-c2[i]; return res;}
int main()
{
    n=read(),m=read(),p1=read(),p2=read();
    for (reg int i=1;i<=n;a[i++]=read());
    a[0]=a[n+1]=n+1; stack[++top]=0;
    for (reg int i=1;i<=n+1;i++)
    {
        while (top&&a[stack[top]]<a[i]) R[stack[top--]]=i;
        L[i]=stack[top]; stack[++top]=i;
    }
    for (reg int i=1;i<=m;i++)
    {
        int l=read(),r=read(); ans[i]=1ll*p1*(r-l);
        q[i]=(Q){l,r,l-1,i,-1}; q[i+m]=(Q){l,r,r,i,1};
    }
    sort(q+1,q+2*m+1);
    for (reg int i=1;i<=n;i++)
    {
        if (L[i]&&R[i]<=n) p[++cnt]=(Q){L[i],L[i],R[i],cnt,p1};
        if (L[i]<i-1&&R[i]<=n) p[++cnt]=(Q){L[i]+1,i-1,R[i],cnt,p2};
        if (L[i]&&R[i]>i+1) p[++cnt]=(Q){i+1,R[i]-1,L[i],cnt,p2};
    }
    sort(p+1,p+cnt+1); int now1=1,now2=1;
    while (!q[now1].x) ++now1; m<<=1;
    for (reg int i=1;i<=n,now1<=m;i++)
    {
        while (now2<=cnt&&p[now2].x==i)
        {
            add(p[now2].l,p[now2].val);
            add(p[now2].r+1,-p[now2].val); ++now2;
        }
        while (now1<=m&&q[now1].x==i)
        {
            ans[q[now1].id]+=q[now1].val*(query(q[now1].r)-query(q[now1].l-1));
            ++now1;
        }
    }
    for (reg int i=1;i<=(m>>1);i++) printf("%lld\n",ans[i]);
    return 0;
}