zcmimi's blog
avatar
zc
2020-09-07 16:56:00
  • 本文总阅读量
查看原题

点击跳转

可以离线处理,按照左右端点排序

考虑每个点的贡献?

记录左边(L_i)/右边(R_i)第一个比它大的地方

  1. 对于区间[L_i,R_i],它有p_1的贡献
  2. 对于区间[l,R_i],l\in [L_i+1,i-1],它有p_2的贡献
  3. 对于区间[L_i,r],r\in [i+1,R_i-1],它有p_2的贡献

每个询问[l,r]可以转化为r的答案减去l-1的答案

把转化后的询问和每个点的贡献区间按位置排序

对于1,我们在扫到R_i时,更新点L_i的贡献

对于2,我们在扫到R_i时,更新区间L_i+1i-1的贡献

对于3,我们在扫到L_i时,更新区间i+1到R_i-1的贡献

#include<bits/stdc++.h>
const int N=200011;
typedef long long ll;
int n,m,a[N],p1,p2,L[N],R[N],sta[N],tp;ll ans[N];
struct node{
    int l,r,x,id,v;
    bool operator<(const node&t)const{return x<t.x;}
}p[N*2],q[N*2];
struct bitseg{
    int s[N];ll S[N];
    void add(int x,int v){
        if(x)for(int i=x;i<=n;i+=i&-i)
            s[i]+=v,S[i]+=1ll*x*v;
    }
    ll ask(int x){
        ll res=0;
        for(int i=x++;i;i-=i&-i)
            res+=1ll*s[i]*x-S[i];
        return res;
    }
    void add(int l,int r,int v){add(l,v),add(r+1,-v);}
    ll ask(int l,int r){return ask(r)-ask(l-1);}
}T;
int main(){
    scanf("%d%d%d%d",&n,&m,&p1,&p2);
    for(int i=1;i<=n;++i)scanf("%d",a+i);
    a[n+1]=n+1;
    for(int i=1;i<=n+1;++i){
        while(tp&&a[i]>a[sta[tp]])R[sta[tp--]]=i;
        L[i]=sta[tp];
        sta[++tp]=i;
    }
    int l,r;
    for(int i=1;i<=m;++i){
        scanf("%d%d",&l,&r);
        ans[i]+=1ll*(r-l)*p1;
        p[i]=(node){l,r,l-1,i,-1};
        p[i+m]=(node){l,r,r,i,1};
    }
    std::sort(p+1,p+m+m+1);
    int tt=0;
    for(int i=1;i<=n;++i){
        if(1<=L[i]&&R[i]<=n)
            q[++tt]=(node){L[i],L[i],R[i],0,p1};
        if(1<=L[i]&&R[i]>i+1)
            q[++tt]=(node){i+1,R[i]-1,L[i],0,p2};
        if(L[i]+1<i&&R[i]<=n)
            q[++tt]=(node){L[i]+1,i-1,R[i],0,p2};
    }
    std::sort(q+1,q+tt+1);
    int n1=1,n2=1;
    while(!p[n1].x)++n1;
    for(int i=1;i<=n&&n1<=m+m;++i){
        for(;n2<=tt&q[n2].x==i;++n2)
            T.add(q[n2].l,q[n2].r,q[n2].v);
        for(;n1<=m+m&&p[n1].x==i;++n1)
            ans[p[n1].id]+=p[n1].v*(T.ask(p[n1].l,p[n1].r));
    }
    for(int i=1;i<=m;++i)printf("%lld\n",ans[i]);
}
LG 3722 [AH2017-HNOI2017]影魔
comment评论
Search
search