洛谷P3722 影魔 [AH2017/HNOI2017] 线段树+扫描线

时间：2021-07-19 18:48:20

正解:线段树+扫描线

解题报告:

传送门!

先理解一下这道题,大概是这样儿的:

对于一个点对,如果他们的两端是这段区间的最大值和次大值,那么他们会有p1的贡献

如果他们的两端是最大值和一个非次大值,那么他们会有p2的贡献

问[a,b]内部的点对贡献之和

首先考虑到,两种贡献都要有一个共同点——有最大值

那看到最大值就应该想到单调栈嘛,然后就可以想到,能不能在维护单调栈的时候顺便把答案求出来了 ?

显然是可以的嘛QwQ

那就大力分类讨论一波咯

首先对询问离线,按照右端点排序,然后就直接加入

设现在加入的数是i,对于栈中的第j个元素,有这么几种可能

1)ai>aj

考虑到这是一个单调减的栈,显然这个情况下,点对(i,j)的贡献为p1(它们内部的点对会在后面讨论的不要管QAQ

2)ai<aj

内部又要分类讨论昂

首先如果ai<aj+1

依然是(i,j)的贡献为p1

然后就考虑计算内部的贡献

对于内部的贡献,看到前面的第一种情况,发现对于j之后的单调栈上的点都已经计算过了,贡献为p1,所以就是j点之后的非栈中的点会和i有p2的贡献

那如果ai>aj+1呢

那就从j到其之后的所有点对都会和它有p2的贡献

再仔细思考一下,对于第一种情况,单点修改就好,对于第二种情况的第二小点,区间修改就好

但是对于第二种情况的第一小点,操作起来就很麻烦,还要搞484栈中的点之类的玩意儿,就很麻烦

所以不难想到直接在第一种情况中把贡献改成p1-p2,这样第二种情况中的第一小点就能直接做了,全部加上就好

然后就做完辣!

#include<bits/stdc++.h>

using namespace std;

#define il inline

#define rg register

#define gc getchar()

#define ll long long

#define ls(x) (x<<1)

#define rs(x) ((x<<1)|1)

#define rp(i,x,y) for(rg ll i=x;i<=y;++i)

const ll N=+;

ll n,m,a[N],top,stck[N],p1,p2,as[N];

struct node{ll l,r,id;}ques[N];

il ll read()

{

    rg char ch=gc;rg ll x=;rg bool y=;

    while(ch!='-' && (ch>'' || ch<''))ch=gc;

    if(ch=='-')ch=gc,y=;

    while(ch>='' && ch<='')x=(x<<)+(x<<)+(ch^''),ch=gc;

    return y?x:-x;

}

struct tree

{

    ll tr[N<<],ad[N<<];

    il void pushdown(ll x,ll l,ll r,ll mid){if(ad[x])tr[ls(x)]+=(ll)(mid-l+)*ad[x],ad[ls(x)]+=ad[x];tr[rs(x)]+=(r-mid)*ad[x],ad[rs(x)]+=ad[x],ad[x]=;}

    il void pushup(ll x){tr[x]=tr[ls(x)]+tr[rs(x)];}

    void modify(ll x,ll l,ll r,ll to_l,ll to_r,ll dat)

        {

            if(to_l<=l && r<=to_r){tr[x]+=(ll)dat*(r-l+);ad[x]+=dat;return;}

            ll mid=(l+r)>>;pushdown(x,l,r,mid);

            if(mid>=to_l)modify(ls(x),l,mid,to_l,to_r,dat);if(mid<to_r)modify(rs(x),mid+,r,to_l,to_r,dat);pushup(x);

        }

    ll query(ll x,ll l,ll r,ll to_l,ll to_r)

        {

            if(to_l<=l && r<=to_r)return tr[x];

            ll mid=(l+r)>>,ret=;pushdown(x,l,r,mid);

            if(mid>=to_l)ret+=query(ls(x),l,mid,to_l,to_r);

            if(mid<to_r)ret+=query(rs(x),mid+,r,to_l,to_r);

            return ret;

        }

    il void clr(ll x,ll l,ll r,ll to)

        {

            if(l==r)return void(tr[x]=ad[x]=);

            ll mid=(l+r)>>;pushdown(x,l,r,mid);if(mid>=to)clr(ls(x),l,mid,to);else clr(rs(x),mid+,r,to);pushup(x);

        }

}instck,notin;

il bool cmp(node gd,node gs){return gd.r<gs.r;}

int main()

{

    freopen("ym.in","r",stdin);freopen("ym.out","w",stdout);

    n=read();m=read();p1=read();p2=read();rp(i,,n)a[i]=read();rp(i,,m)ques[i].l=read(),ques[i].r=read(),ques[i].id=i;sort(ques+,ques++m,cmp);

    rp(i,,m)

    {

        while(ques[i-].r<ques[i].r)

        {

            ++ques[i-].r;

            while(top && a[ques[i-].r]>a[stck[top]])notin.modify(,,n,stck[top],stck[top],instck.query(,,n,top,top)+p1-p2),instck.clr(,,n,top--);

            if(top)instck.modify(,,n,top,top,p1-p2),instck.modify(,,n,,top,p2);

            if(stck[top]+<=ques[i-].r)notin.modify(,,n,stck[top]+,ques[i-].r-,p2);stck[++top]=ques[i-].r;

        }

        as[ques[i].id]=notin.query(,,n,ques[i].l,ques[i].r)+instck.query(,,n,lower_bound(stck+,stck+top+,ques[i].l)-stck,top);

    }

    rp(i,,m)printf("%lld\n",as[i]);

    return ;

}

//看起来并不多的样子,,,其实打死我了TT

然后我一边觉得这题好实现一边花式打错魔改了3h,,,心态崩了TT真实想死了TT

相关文章