竞赛讨论区 > T4 题解
头像
King942
发布于 2022-10-05 15:32 浙江
+ 关注

T4 题解

我们发现

也就是说,在某个位置执行 等价于把其后的所有 min 和 max 操作的权值减去 ,所有 min 和 max 执行完后再加上 。因此 是分段函数且分成三段。
于是我们用树状数组维护的是所有加法操作权值的前缀和,用线段树维护 min 和 max 操作(区间加法全局求 min/max)。验题人则直接把三个操作写在了一棵线段树里面,不需要繁琐的区间加。

合并信息时,注意信息合并的本质是两个分段函数的复合,而不是简单的区间交(我按照区间交写挂了好久才想到是 pushup 的锅)

Rg un(const Rg& a,const Rg& b){
    return Rg(max(min(a.l,b.r),b.l),max(min(a.r,b.r),b.l));
}

完整代码:

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <set>

using namespace std;
typedef long long ll;
const ll inf=1145****19810000;
#define il inline
#define SET
#define TO =

const int N=100005;
int n;

struct Rg{
    ll l,r;bool ls;    // 0->min 1->max
    Rg(ll l=-inf,ll r=inf,bool ls=0):l(l),r(r){}
    ll operator()(ll a){if(ls==0) return min(max(a,l),r); else return max(min(a,r),l); }
    Rg operator+(const ll& o){ return Rg(l+o,r+o); }
};
Rg un(const Rg& a,const Rg& b){
    return Rg(max(min(a.l,b.r),b.l),max(min(a.r,b.r),b.l),b.ls);
}
const Rg I(-inf,inf);

Rg v[N<<1];ll tg[N<<1];int ch[N<<1][2];int tp=0;
#define ls ch[u][0]
#define rs ch[u][1]
void pushup(int u){ v[u]=un(v[ls],v[rs]); }
void apply(int u,ll t){ v[u].l+=t;v[u].r+=t;tg[u]+=t; }
void pushdown(int u){
    if(tg[u]){
        if(ls) apply(ls,tg[u]);
        if(rs) apply(rs,tg[u]);
        tg[u]=0;
    }
}
int build(Rg a[],int l,int r){
    if(l==r){ v[++tp]=a[l];return tp; }
    else{
        int mid=(l+r)/2,u=++tp;
        ls=build(a,l,mid);
        rs=build(a,mid+1,r);
        pushup(u);
        return u;
    }
}
void add(int L,int R,ll t,int u,int l,int r){
    pushdown(u);
    if(L<=l && r<=R){ apply(u,t); }
    else{
        int mid=(l+r)/2;
        if(L<=mid){ add(L,R,t,ls,l,mid); }
        if(R>mid){ add(L,R,t,rs,mid+1,r); }
        pushup(u);
    }
}
void upd(int P,Rg t,int u,int l,int r){
    pushdown(u);
    if(l==r) v[u]=t;
    else{
        int mid=(l+r)/2;
        if(P<=mid) upd(P,t,ls,l,mid);
        else upd(P,t,rs,mid+1,r);
        pushup(u);
    }
}

Rg a[N];ll ad[N];

ll sb[N];
void adds(int u,ll t){ while(u<=n){ sb[u]+=t;u+=(u&(-u)); } }
ll querys(int u){ ll t=0;while(u){ t+=sb[u];u-=(u&(-u)); }return t; }

int main(){

    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);

    cin>>n;
    for(int i=1;i<=n;i++){
        int op;ll v;cin>>op>>v;
        if(op==1){ a[i]=I;ad[i]=v; }
        if(op==2){ a[i]=Rg(-inf,v);ad[i]=0; }
        if(op==3){ a[i]=Rg(v,inf,1);ad[i]=0; }
        adds(i,ad[i]);
    }
    int Rt=build(a,1,n);
    for(int i=1;i<=n;i++){
        add(i,n,-ad[i],Rt,1,n);
    }

    int q;
    cin>>q;
    // Seg[i] -> a[i] - Sum[i]
    for(int _=1;_<=q;_++){
        int op;cin>>op;
        if(op==1){
            int p;ll v;cin>>p>>v;
            // ad[p] -> v;
            add(p,n,-v+ad[p],Rt,1,n);
            adds(p,v-ad[p]);
            SET ad[p] TO v;
            // a[p] -> I;
            SET a[p] TO I;
            upd(p,I,Rt,1,n);
        }else if(op==2){
            int p;ll v;cin>>p>>v;
            // ad[p] -> 0
            add(p,n,ad[p],Rt,1,n);
            adds(p,-ad[p]);
            SET ad[p] TO 0;
            // a[p] -> Rg(-inf,v)
            SET a[p] TO Rg(-inf,v);
            upd(p,a[p]+(-querys(p)),Rt,1,n);
        }else if(op==3){
            int p;ll v;cin>>p>>v;
            // ad[p] -> 0
            add(p,n,ad[p],Rt,1,n);
            adds(p,-ad[p]);
            SET ad[p] TO 0;
            // a[p] -> Rg(v,inf)
            SET a[p] TO Rg(v,inf,1);
            upd(p,a[p]+(-querys(p)),Rt,1,n);
        }else{
            ll x;cin>>x;
            Rg res=v[Rt];
            cout<<res(x)+querys(n)<<"\n";
        }
    }

    return 0;
}

全部评论

(0) 回帖
加载中...
话题 回帖

等你来战

查看全部

热门推荐