题解：P10639 BZOJ4695 最佳女选手

· · 题解

势能线段树入门题，但是非常的码农。

题意

给定一个序列，让我们实现 6 种操作。

  1. 区间 [l, r] 加 x。
  2. 区间 [l, r] 里小于 x 的数变成 x。
  3. 区间 [l, r] 里大于 x 的数变成 x。
  4. 区间 [l, r] 求和。
  5. 区间 [l, r] 求 \max。
  6. 区间 [l, r] 求 \min。

思路

看到操作 2 和 操作 3 就不难想到势能线段树。

首先我们来思考如何维护操作 3。

区间对 x 取 \min 意味着只对大于 x 的数有效。我们对于每个区间维护两个信息 \text{Max} 和 \text{Max2}，即最大值与次大值。

操作 2 同理。

对于本题我们依旧沿用这个思路，同时根据操作需求，我们维护：最大、次大、最大个数、最小、次小、最小个数、区间和，这几个信息；同时维护区间最大，区间最小，区间和这几个 \text{lazytag}。

时间复杂度可以证明是 O(n\log^2 n) 的。

实现

注意 \text{lazytag} 下传的优先级。本题可能略微卡常，建议使用结构体封装一下。

#include<bits/stdc++.h>
using namespace std;
#define int long long
inline int read(){
   int s=0,w=1;
   char ch=getchar();
   while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
   while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
   return s*w;
}
inline void write(int x){
    if(x==0){putchar('0');return;}
    int len=0,k1=x,c[10005];
    if(k1<0)k1=-k1,putchar('-');
    while(k1)c[len++]=k1%10+'0',k1/=10;
    while(len--)putchar(c[len]);
}
const int N=5e5+10;
int a[N];
struct SGT{
    int mx[N<<2],mx2[N<<2],mn[N<<2],mn2[N<<2],smx[N<<2],smn[N<<2];
    int add[N<<2],tr[N<<2],tmx[N<<2],tmn[N<<2];
    int ls(int p){return p<<1;}
    int rs(int p){return p<<1|1;}
    void push_up(int p){
        tr[p]=tr[ls(p)]+tr[rs(p)];
        if(mx[ls(p)]==mx[rs(p)]){
            mx[p]=mx[ls(p)],smx[p]=smx[ls(p)]+smx[rs(p)];
            mx2[p]=max(mx2[ls(p)],mx2[rs(p)]);
        }
        else if(mx[ls(p)]>mx[rs(p)]){
            mx[p]=mx[ls(p)],smx[p]=smx[ls(p)];
            mx2[p]=max(mx2[ls(p)],mx[rs(p)]);
        }
        else{
            mx[p]=mx[rs(p)],smx[p]=smx[rs(p)];
            mx2[p]=max(mx2[rs(p)],mx[ls(p)]);
        }
        if(mn[ls(p)]==mn[rs(p)]){
            mn[p]=mn[ls(p)],smn[p]=smn[ls(p)]+smn[rs(p)];
            mn2[p]=min(mn2[ls(p)],mn2[rs(p)]);
        }
        else if(mn[ls(p)]<mn[rs(p)]){
            mn[p]=mn[ls(p)],smn[p]=smn[ls(p)];
            mn2[p]=min(mn2[ls(p)],mn[rs(p)]);
        }
        else{
            mn[p]=mn[rs(p)],smn[p]=smn[rs(p)];
            mn2[p]=min(mn2[rs(p)],mn[ls(p)]);
        }
    }
    void build(int p,int pl,int pr){
        tmn[p]=INT_MAX,tmx[p]=INT_MIN;
        if(pl==pr){
            tr[p]=mn[p]=mx[p]=a[pl];
            mn2[p]=INT_MAX,mx2[p]=INT_MIN;
            smx[p]=smn[p]=1;
            return ;
        }
        int mid=(pl+pr)>>1;
        build(ls(p),pl,mid);
        build(rs(p),mid+1,pr);
        push_up(p);
    }
    void add_tag(int p,int pl,int pr,int d){
        mx[p]+=d,mn[p]+=d,add[p]+=d;
        tr[p]+=d*(pr-pl+1);
        if(mx2[p]!=INT_MIN)mx2[p]+=d;
        if(mn2[p]!=INT_MAX)mn2[p]+=d;
        if(tmn[p]!=INT_MAX)tmn[p]+=d;
        if(tmx[p]!=INT_MIN)tmx[p]+=d; 
    }
    void max_tag(int p,int d){
        if(mn[p]>d)return ;
        tr[p]+=(d-mn[p])*smn[p];
        if(mx[p]==mn[p])mx[p]=d;
        if(mx2[p]==mn[p])mx2[p]=d;
        if(tmn[p]<d)tmn[p]=d;
        mn[p]=d,tmx[p]=d;
    }
    void min_tag(int p,int d){
        if(mx[p]<=d)return ;
        tr[p]+=(d-mx[p])*smx[p];
        if(mn[p]==mx[p])mn[p]=d;
        if(mn2[p]==mx[p])mn2[p]=d;
        if(tmx[p]>d)tmx[p]=d;
        mx[p]=d,tmn[p]=d;
    }  
    void push_down(int p,int pl,int pr){
        if(add[p]){
            int mid=(pl+pr)>>1;
            add_tag(ls(p),pl,mid,add[p]);
            add_tag(rs(p),mid+1,pr,add[p]);
            add[p]=0;
        }
        if(tmx[p]!=INT_MIN){
            max_tag(ls(p),tmx[p]);
            max_tag(rs(p),tmx[p]);
            tmx[p]=INT_MIN;
        }
        if(tmn[p]!=INT_MAX){
            min_tag(ls(p),tmn[p]);
            min_tag(rs(p),tmn[p]);
            tmn[p]=INT_MAX;
        }
    }
    void Add(int l,int r,int p,int pl,int pr,int d){
        if(l<=pl&&pr<=r){
            add_tag(p,pl,pr,d);
            return ;
        }
        int mid=(pl+pr)>>1;
        push_down(p,pl,pr);
        if(l<=mid)Add(l,r,ls(p),pl,mid,d);
        if(r>mid)Add(l,r,rs(p),mid+1,pr,d);
        push_up(p);
    }
    void Mmax(int l,int r,int p,int pl,int pr,int d){
        if(mn[p]>=d)return ;
        if(l<=pl&&pr<=r&&mn2[p]>d){
            max_tag(p,d);
            return ;
        }
        int mid=(pl+pr)>>1;
        push_down(p,pl,pr);
        if(l<=mid)Mmax(l,r,ls(p),pl,mid,d);
        if(r>mid)Mmax(l,r,rs(p),mid+1,pr,d);
        push_up(p);
    }
    void Mmin(int l,int r,int p,int pl,int pr,int d){
        if(mx[p]<=d)return ;
        if(l<=pl&&pr<=r&&mx2[p]<d){
            min_tag(p,d);
            return ;
        }
        int mid=(pl+pr)>>1;
        push_down(p,pl,pr);
        if(l<=mid)Mmin(l,r,ls(p),pl,mid,d);
        if(r>mid)Mmin(l,r,rs(p),mid+1,pr,d);
        push_up(p);
    }
    int Qsum(int l,int r,int p,int pl,int pr){
        if(l<=pl&&pr<=r)return tr[p];
        push_down(p,pl,pr);
        int res=0,mid=(pl+pr)>>1;
        if(l<=mid)res+=Qsum(l,r,ls(p),pl,mid);
        if(r>mid)res+=Qsum(l,r,rs(p),mid+1,pr);
        return res;
    }
    int Qmax(int l,int r,int p,int pl,int pr){
        if(l<=pl&&pr<=r)return mx[p];
        push_down(p,pl,pr);
        int res=INT_MIN,mid=(pl+pr)>>1;
        if(l<=mid)res=max(Qmax(l,r,ls(p),pl,mid),res);
        if(r>mid)res=max(Qmax(l,r,rs(p),mid+1,pr),res);
        return res;
    }
    int Qmin(int l,int r,int p,int pl,int pr){
        if(l<=pl&&pr<=r)return mn[p];
        push_down(p,pl,pr);
        int res=INT_MAX,mid=(pl+pr)>>1;
        if(l<=mid)res=min(Qmin(l,r,ls(p),pl,mid),res);
        if(r>mid)res=min(Qmin(l,r,rs(p),mid+1,pr),res);
        return res;
    }
}sgt;
signed main(){
    int n=read();
    for(int i=1;i<=n;i++)a[i]=read();
    sgt.build(1,1,n);
    int m=read();
    while(m--){
        int op=read(),l=read(),r=read();
        if(op==1){
            int x=read();
            sgt.Add(l,r,1,1,n,x);
        }
        else if(op==2){
            int x=read();
            sgt.Mmax(l,r,1,1,n,x);
        }
        else if(op==3){
            int x=read();
            sgt.Mmin(l,r,1,1,n,x);
        }
        else if(op==4)write(sgt.Qsum(l,r,1,1,n)),puts("");
        else if(op==5)write(sgt.Qmax(l,r,1,1,n)),puts("");
        else write(sgt.Qmin(l,r,1,1,n)),puts("");
    }
    return 0;
}

后记

这道题目是我期末考完试数据结构康复训练时写的。当时已经基本不会码代码了。大概断断续续写和调了 4 天。

期间发生的垃圾错误包括但不限于：

数组开成了 N>>2，max 打成了 min，mx 打成了 tmx，res 没有初始化。

写这道题为了我的码力带来了极大的提升。故写此题解以祭之。

最后附上我的提交记录