[HNOI2017]影魔

[Luogu3722] [BZOJ4826]

感谢Brave赐予我勇气

给定n个数的排列，m次询问，每次询问询问一个区间内所有子区间的贡献。
每个区间如果两个端点分别是最大值和次大值，我们就算P1的贡献。
如果两个端点一个是最大值，一个不是次大值，我们就算P2的贡献。

因为要处理两个端点的值， 所以我们钦定某一个端点为最大值（这里钦定右端点），同时处理另一个端点的情况。

那么如果要计算左端点是最大值，那么只要把序列反转然后重新计算一次。

考虑计算一个点的值。如果某个点是从右端点出发的当前的最大值。
那么这个点x要和右端点计算P1的贡献。这个点之前到上个最大点之后的点全部计算P2的贡献。
这个可以用个单调栈来维护。

最后还有一部分细节： 在单调栈弹完的时候，必须要把之前的弹出的没处理的元素加上P2的贡献。

\(1.\)转化题意,很多时候可以用单调栈维护区间的信息

\(2.\)一定要分类清楚,单调栈记得最后还要处理一次

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<vector>
#include<stack>
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define Debug(x) cout<<#x<<"="<<x<<endl
using namespace std;
typedef long long LL;
const int INF=1e9+7;
typedef pair<int,int> pii;
inline LL read(){
    register LL x=0,f=1;register char c=getchar();
    while(c<48||c>57){if(c=='-')f=-1;c=getchar();}
    while(c>=48&&c<=57)x=(x<<3)+(x<<1)+(c&15),c=getchar();
    return f*x;
}

const int MAXN=2e5+5;

int a[MAXN];LL ans[MAXN];
int n,m,p1,p2;
pii Q[MAXN];
vector <pii> q[MAXN];

struct SGT{
    LL val[MAXN<<2],add[MAXN<<2];
    inline void init(){
        memset(val,0,sizeof val);
        memset(add,0,sizeof add);
    }
#define ls (rt<<1)
#define rs (rt<<1|1)
    inline void pushup(int rt){
        val[rt]=val[ls]+val[rs];
    }
    inline void pushdown(int rt,int l,int r,int mid){
        if(!add[rt]) return;
        add[ls]+=add[rt],val[ls]+=add[rt]*(mid-l+1);
        add[rs]+=add[rt],val[rs]+=add[rt]*(r-mid);
        add[rt]=0;
    }
    inline void modify(int rt,int l,int r,int x,int y,LL z){
        if(x>y) return;
        if(l>=x&&r<=y){
            val[rt]+=z*(r-l+1);
            add[rt]+=z;
            return;
        }
        int mid=(l+r)>>1;
        pushdown(rt,l,r,mid);
        if(x<=mid) modify(ls,l,mid,x,y,z);
        if(mid<y) modify(rs,mid+1,r,x,y,z);
        pushup(rt);
    }
    inline LL query(int rt,int l,int r,int x,int y){
        if(x>y) return 0;
        if(l>=x&&r<=y) return val[rt];
        LL res=0;int mid=(l+r)>>1;
        pushdown(rt,l,r,mid);
        if(x<=mid) res+=query(ls,l,mid,x,y);
        if(mid<y) res+=query(rs,mid+1,r,x,y);
        return res;
    }
#undef ls
#undef rs
}T;

inline void init(){
    n=read(),m=read(),p1=read(),p2=read();
    for(int i=1;i<=n;i++) a[i]=read();
    for(int i=1;i<=m;i++){
        int x=read(),y=read();
        Q[i]=pii(x,y);
    }
}

inline void duce(){
    stack <int> s;
    T.init();
    for(int i=1;i<=n;i++){
        int last=i;
        while(!s.empty()&&a[i]>=a[s.top()]){
            if(s.top()+1<last) T.modify(1,1,n,s.top()+1,last-1,p2);//最大值和非次大值
            T.modify(1,1,n,s.top(),s.top(),p1);//最大值和次大值
            last=s.top();s.pop();
        }
        if(s.empty()) T.modify(1,1,n,1,last-1,p2);
        else T.modify(1,1,n,s.top()+1,last-1,p2);//最后还要处理一次!!
        s.push(i);  
        for(int j=0;j<q[i].size();j++)
            ans[q[i][j].second]+=T.query(1,1,n,q[i][j].first,i);//处理到右端点了就可以统计答案了
    }
}

inline void solve(){
    for(int i=1;i<=m;i++) q[Q[i].second].push_back(pii(Q[i].first,i));
    for(int i=1;i<=n;i++) sort(q[i].begin(),q[i].end());
    duce();
    for(int i=1;i<=n;i++) q[i].clear();
    for(int i=1;i<=m;i++) q[n-Q[i].first+1].push_back(pii(n-Q[i].second+1,i));//以右端点和左端点分别做一次,转化为单调性的问题
    for(int i=1;i<=n;i++) sort(q[i].begin(),q[i].end());
    reverse(a+1,a+n+1);
    duce();
    for(int i=1;i<=m;i++) printf("%lld\n",ans[i]);
}

int main(){ 
//  freopen("asd.in","r",stdin);
    init();
    solve();
}

[HNOI2017]影魔

原文：https://www.cnblogs.com/lizehon/p/10532793.html