真心巧妙,不看题解准做不出 (之前题解都看不懂 QwQ)

这道题貌似有许多的做法,都不费,主席树的话不知道怎么搞,于是建了 $3$ 棵线段树,实测是不会炸的。

30 分做法:


小学生都能轻易想出来的解法,对于一个询问的区间,暴力枚举其子区间,然后按照题面的要求算贡献,区间最大值可以用 $ST$ 表预处理,复杂度爆炸,但是仍然可以拿到 $30$ 暴力分。

#include<cmath>
#include<queue>
#include<cstdio>
#include<string>
#include<cstring>
#include<iostream>

#define max(x,y) ((x)>(y)?(x):(y))
#define min(x,y) ((x)<(y)?(x):(y))

const int N=1e5+2;
const int LogN=23;
const int inf=1e9+9; 

int v[N],n,m,p1,p2;

struct ST{
    int logs[N],f[N][LogN+2];
    inline void make(){
        logs[0]=-1;
        for(int i=1;i<=n;++i)
            f[i][0]=v[i],logs[i]=logs[i>>1]+1;
        for(int j=1;j<=LogN;++j)
            for(int i=1;i+(1<<j)-1<=n;++i)
                f[i][j]=max(f[i][j-1],f[i+(1<<(j-1))][j-1]);
    }
    inline int query(int x,int y){
        int ans=logs[y-x+1];
        return max(f[x][ans],f[y-(1<<ans)+1][ans]);
    }
}T;

template <typename _Tp> inline void IN(_Tp&x){
    char ch;bool flag=0;x=0;
    while(ch=getchar(),!isdigit(ch))if(ch=='-')flag=1;
    while(isdigit(ch))x=x*10+ch-'0',ch=getchar();
    if(flag)x=-x;
} 

int main(){
    IN(n),IN(m),IN(p1),IN(p2);
    for(int i=1;i<=n;++i)IN(v[i]);
    T.make();
    for(int i=1;i<=m;++i){
        int l,r,ans=0;
        IN(l),IN(r);
        for(int a=l;a<=r;++a)
            for(int b=a+2;b<=r;++b){
                int sum=T.query(a+1,b-1);
                if(v[a]>=sum&&v[b]>=sum)ans+=p1;
                if((v[a]<sum&&sum<v[b])||(v[b]<sum&&sum<v[a]))ans+=p2;
            }
        printf("%d\n",ans+(r-l)*p1);
    }
    return 0;
}

100 分做法


对于一个点 $i$ ,我们设 $lmax[i]$ 为 $i$ 向左走遇到的第一个大于自己的数(没有的话为 $0$) ,同样的,设 $rmax[i]$ 为 $i$ 向右走遇到的第一个大于自己的数(没有的话为 $n+1$) 。这两个数组比较容易求出,搞个单调栈求就好。

top=0,stack[0]=0;
for(int i=1;i<=n;++i){
    while(top&&k[stack[top]]<k[i])--top;
    lmax[i]=stack[top],stack[++top]=i;
}
top=0,stack[0]=n+1;
for(int i=n;i>=1;--i){
    while(top&&k[stack[top]]<k[i])--top;
    rmax[i]=stack[top],stack[++top]=i;
}

然后可以发现,如果枚举点 $i$ 的话,有了上面的两个数组后有关 $i$ 的贡献就好求些了,首先我们可以知道 $i$ 是区间 $[lmax[i]+1,rmax[i]-1]$ 的最大值,那么对于每种贡献:

  • 如果 $lmax[i]$ 和 $rmax[i]$ 都在当前询问区间内,那么就可以做出 $p_1$ 的贡献。
  • 如果 $lmax[i]$ 在当前询问区间中,那么显然 $lmax[i]$ 为区间 $[lmax[i],rmax[i]-1]$ 的最大值,这个时候右端点如果在 $[i+1,rmax[i]-1]$ 区间中,那么可以保证右端点不是 $[lmax[i],rmax[i]-1]$ 的次大值,这个时候可以产生多个 $p_2$ 的贡献。
  • 如果 $rmax[i]$ 在当前询问区间中,那么显然当左端点为 $[lmax[i]+1,i-1]$ 的时候该子区间均能产生 $p_2$ 的贡献,原因跟上面一样的。

但是这样的话复杂度依旧是 $O(n^2)$ 的,所以还要优化。

考虑用线段树维护,我们离线处理询问,把每个询问按左端点排个序,然后反着扫一遍,如果遇到了一个点 $x$ ,它是 某个点/某些点 的 $lmax$ ,假设 $x$ 是 $i$ 的 $lmax$ ,那么我们依次在第一颗线段树中实现区间加:将 $[i+1,rmax[i]-1]$ 区间正题加上 $p_2$ ,因为当前的左端点为 $x$ ,这个时候我们将要计算的是所有的左端点为 $x$ 的区间对答案的贡献,因为对于 $i$ 来说右端点的范围就是 $[i+1,rmax[i]-1]$,这些区间均可以做出贡献,于是都在线段树中加上。当然在做贡献的之前不要忘记判断 $i+1<rmax[i]$ ,如果不满足的话就没有右端点了……

那么接下来讨论怎么计算 $p_1$ 的贡献,对于询问区间来说,现在我们确定了左端点为 $x$ ,这个时候当右端点落在 $[rmax[i],n+1]$ 的时候询问区间都可以算上 $[lmax[i],rmax[i]]$ 区间的贡献,也就是 $p_1$ 的贡献,于是我们可以在另一个线段树中将 $[rmax[i],n+1]$ 全都加上 $p_1$ 即可。

按照上面的方法,再正着扫一遍计算 $rmax$ 的情况就好,当然反着扫的时候就不要算 $p_1$ 的贡献了,不然就会重复了,想想就可以明白。最后就是一定要开 $longlong$ 。

Code:

#include<cmath>
#include<queue>
#include<cstdio>
#include<string>
#include<cstring>
#include<iostream>
#include<algorithm>

#define max(x,y) ((x)>(y)?(x):(y))
#define min(x,y) ((x)<(y)?(x):(y))
#define swap(x,y) ((x)^=(y)^=(x)^=(y))
typedef long long ll;

const int N=2e5+2;
const int inf=1e9+9;

template <typename _Tp> inline void IN(_Tp&x){
    char ch;bool flag=0;x=0;
    while(ch=getchar(),!isdigit(ch))if(ch=='-')flag=1;
    while(isdigit(ch))x=x*10+ch-'0',ch=getchar();
    if(flag)x=-x;
} 

struct Seg_Tree{//线段树板子
    #define mid ((l+r)>>1)
    ll v[N<<2];int tag[N<<2];
    inline void pushdown(int x,int l,int r){
        if(tag[x]){
            tag[x<<1]+=tag[x],tag[x<<1|1]+=tag[x];
            v[x<<1]+=tag[x]*(mid-l+1),v[x<<1|1]+=tag[x]*(r-mid);
        }tag[x]=0;return;
    }   
    inline void updata(int x,int l,int r,int L,int R){
        if(L<=l&&r<=R){v[x]+=r-l+1,++tag[x];return;}
        pushdown(x,l,r);
        if(L<=mid)updata(x<<1,l,mid,L,R);
        if(R>mid)updata(x<<1|1,mid+1,r,L,R);
        v[x]=v[x<<1]+v[x<<1|1];
    }
    inline ll query(int x,int l,int r,int L,int R){
        if(L<=l&&r<=R)return v[x];
        pushdown(x,l,r);
        ll ans=0;
        if(L<=mid)ans+=query(x<<1,l,mid,L,R);
        if(R>mid)ans+=query(x<<1|1,mid+1,r,L,R);
        return ans;
    }
}st1,st2,st3;//三棵线段树 [滑稽]

int n,m,k[N];ll p1,p2;
struct Query{int l,r;ll ans;}q[N];
int lmax[N],rmax[N],stack[N],top;
std::vector<int> li[N],ri[N],lq[N],rq[N];

inline void _Pre_lmax_rmax(){
    top=0,stack[0]=0;
    for(int i=1;i<=n;++i){
        while(top&&k[stack[top]]<k[i])--top;
        lmax[i]=stack[top],li[stack[top]].push_back(i);//统计上文中的 x
        stack[++top]=i;
    }
    top=0,stack[0]=n+1;
    for(int i=n;i>=1;--i){
        while(top&&k[stack[top]]<k[i])--top;
        rmax[i]=stack[top],ri[stack[top]].push_back(i);
        stack[++top]=i;
    }
}

int main(){
    //freopen("code.in","r",stdin);
    IN(n),IN(m),IN(p1),IN(p2);
    for(int i=1;i<=n;++i)IN(k[i]);
    _Pre_lmax_rmax();
    for(int i=1;i<=m;++i){
        IN(q[i].l),lq[q[i].l].push_back(i);
        IN(q[i].r),rq[q[i].r].push_back(i);
    }
    for(int i=n;i>=1;--i){
        for(int j=0;j<li[i].size();++j){//计算左端点在 i 的区间的贡献
            if(li[i][j]+1<rmax[li[i][j]])
                st1.updata(1,0,n+1,li[i][j]+1,rmax[li[i][j]]-1);
            st3.updata(1,0,n+1,rmax[li[i][j]],n+1);
        }
        for(int j=0;j<lq[i].size();++j){//统计左端点在 i 的询问区间的答案
            q[lq[i][j]].ans+=st1.query(1,0,n+1,i,q[lq[i][j]].r)*p2;
            q[lq[i][j]].ans+=st3.query(1,0,n+1,q[lq[i][j]].r,q[lq[i][j]].r)*p1;
        }
    }
    for(int i=1;i<=n;++i){
        for(int j=0;j<ri[i].size();++j)
            if(ri[i][j]-1>lmax[ri[i][j]])
                st2.updata(1,0,n+1,lmax[ri[i][j]]+1,ri[i][j]-1);
        for(int j=0;j<rq[i].size();++j)
            q[rq[i][j]].ans+=st2.query(1,0,n+1,q[rq[i][j]].l,i)*p2;
    }
    for(int i=1;i<=m;++i)//输出答案,不要忘了漏统计的长度为 2 的区间
        printf("%lld\n",q[i].ans+1ll*(q[i].r-q[i].l)*p1);
    return 0;
}
分类: 文章

Qiuly

井戸の底の空にはまだかすかな希望の光がある……

发表评论

电子邮件地址不会被公开。 必填项已用*标注