题解：P16446 [XJTUPC 2026] 修罗指数

Karmallis · 2026-05-11 19:04:55 · 题解

竟敢卡我常？？？？

注意到我们是对一个前后缀的 chkmin / chkmax，所以我们的映射应当形成一个凸包，上面的顶点最多被加入一次 / 去掉一次，所以我们直接用两个单调 map 去维护就可以。

然后我们会发现由于 A 和 B 在有些地方相交，有些地方不相交，我们进行区间求和的时候贡献在不同地方是不同的。

不过我们发现由于每一个端点在值域上的移动是单调的，所以其贡献最多被反转一次，所以我们可以直接用一个 set 去记录一下有哪些位置的贡献尚未被反转，然后让每个点被反转的时候在 set 中刚好被删除。

这同时要求我们的区间求和线段树维护具体有哪些存在的值，具体地，我们使用四棵线段树，分别维护未反转的 A 数列贡献，未反转的 B 数列贡献，反转过的 A 数列贡献，以及反转过的 B 数列贡献。

然后我们考虑我们更新的时候具体应当怎么做。

对于 AB 数列自身，我们在 chkmin / chkmax 的时候会对一个区间设为某个值，所以对应到线段树上的操作就是区间赋值。

而对于贡献的反转，我们需要求操作中新增的 AB 交区间。这个交区间会由当前的操作数产生，我们再加两个单调 map 对于数列 A 和数列 B 分别维护前缀值域所能对应的极右端点和后缀值域所能对应的极左端点即可。每次我们加一个数一定是找到极长的这样一个区间尝试反转贡献。

然后我们发现我们十分不意外地被卡常了。所以我们索性把之前的单调 map 扬了换成树状数组，把 set 扬了换成线段树，然后就能过了。

::::sucess[AC Code]

#include<bits/stdc++.h>
using namespace std;using ll=long long;using ull=unsigned long long;using uint=unsigned int;mt19937_64 rnd(time(0));
#define lowbit(x) ((x)&-(x))

template<int N> struct rarsq_segment_tree{
    static constexpr int M=1<<__lg(N)+1,K=M<<1;
    struct node{
        ll val;
        int tag,sz;
        bool flag;
    }a[K];
    inline void maketag(int x,int k){
        a[x].flag=1,a[x].tag=k,a[x].val=(ll)k*a[x].sz;
    }
    inline void pushdown(int x){
        if(!a[x].flag) return;
        a[x].flag=0;
        maketag(x<<1,a[x].tag);
        maketag(x<<1|1,a[x].tag);
    }
    inline void pushup(int x){
        if(a[x].flag) return;
        a[x].sz=a[x<<1].sz+a[x<<1|1].sz;
        a[x].val=a[x<<1].val+a[x<<1|1].val;
    }
    void set(int x,int y,int z){ //val, sz
        x+=M;
        for(int i=__lg(N);i;i--) pushdown(x>>i);
        a[x].val=y,a[x].sz=z,a[x].tag=y,a[x].flag=0;;
        while(x>>=1) pushup(x);
    }
    void ra(int l,int r,int k){
        l+=M,r+=M;
        for(int i=__lg(N);i;i--) pushdown(l>>i),pushdown(r>>i);
        for(int i=l,j;i<=r;i+=1<<j) maketag(i>>(j=__builtin_ctz(i|1<<__lg(r+1-i))),k);
        while(l>>=1,r>>=1) pushup(r),pushup(l);
    }
    ll sum(int l,int r){
        l+=M,r+=M;
        ll res=0;
        for(int i=__lg(N);i;i--) pushdown(l>>i),pushdown(r>>i);
        for(int i=l,j;i<=r;i+=1<<j) res+=a[i>>(j=__builtin_ctz(i|1<<__lg(r+1-i)))].val;
        return res;
    }
};

template<int N> struct smroq_segment_tree{
    static constexpr int M=1<<__lg(N)+1,K=M<<1;
    bitset<K> a;
    void build(){
        a.set();
    }
    int find(int x){
        while(x<M) x=x<<1|a[x<<1|1];
        return x-M;
    }
    int find(int l,int r){
        l+=M,r+=M;
        for(int i=l,j;i<=r;i+=1<<j){
            j=__builtin_ctz(i|1<<__lg(r+1-i));
            if(a[i>>j]) return find(i>>j);
        }
        return -1;
    }
    void set(int x,bool k){
        a[x+=M]=k;
        while(x>>=1) a[x]=a[x<<1]|a[x<<1|1];
    }
};

template<int N> struct fenwick_map{
    int tr[N];
    int dt[N];
    bitset<N> flag;
    void insert(int x,int k){
        dt[x]=k;
        if(flag[x]||!x) return;
        flag[x]=1;
        for(;x<N;x+=lowbit(x)) tr[x]++;
    }
    void erase(int x){
        dt[x]=0;
        flag[x]=0;
        if(!x) return;
        for(;x<N;x+=lowbit(x)) tr[x]--;
    }
    int sum(int x){
        int res=0;
        for(;x;x-=lowbit(x)) res+=tr[x];
        return res;
    }
    int kth(int k){ //1-indexed
        if(!k) return 0;
        int res=0;
        for(int i=1<<__lg(N);i;i>>=1){
            int nxt=res|i;
            if(nxt>=N) continue;
            if(tr[nxt]>=k) continue;
            res=nxt;
            k-=tr[res];
        }
        return res+1;
    }
    int getprev(int x){ //prev(upper_bound(x))
        if(flag[x]) return x;
        return kth(sum(x));
    }
    int getnext(int x){ //lower_bound(x)
        if(flag[x]) return x;
        return kth(sum(x)+1);
    }
    inline int& operator[] (int x){
        return dt[x];
    }
};

constexpr int N=5e5+9,inf=0x3f3f3f3f;
int n,m,fa,fb;
rarsq_segment_tree<N> tsal,tsar,tsbl,tsbr;
smroq_segment_tree<N> nst;
fenwick_map<N> tra,trb; //a,b: prefix min, suffix max; c,d: prefix max, suffix min

struct odt{ //prefix max
    map<int,int> tr;
    odt(){
        tr={{-inf,-inf},{inf,inf}};
    }
    void insert(int x,int y){
        auto it=prev(tr.upper_bound(x));
        if(it->second>=y) return;
        for(it++;it->second<=y;it=tr.erase(it));
        tr[x]=y;
    }
    int q(int x){
        return prev(tr.upper_bound(x))->second;
    }
    void ipmx(int x,int y){insert(x,y);}
    void ipmi(int x,int y){insert(x,-y);}
    void ismx(int x,int y){insert(-x,y);}
    void ismi(int x,int y){insert(-x,-y);}
    int qpmx(int x){return q(x);}
    int qpmi(int x){return -q(x);}
    int qsmx(int x){return q(-x);}
    int qsmi(int x){return -q(-x);}
}trc,trd;

bool chkmove(int l,int r){
    int x=nst.find(l,r),k;
    if(x==-1) return 0;
    //have to move both on tree a and tree b
    //move on tree a
    k=tsal.sum(x,x);
    tsal.set(x,0,0);
    tsar.set(x,k,1);
    //move on tree b
    k=tsbl.sum(x,x);
    tsbl.set(x,0,0);
    tsbr.set(x,k,1);
    //remove from nst
    nst.set(x,0);
    return 1;
}

signed main(){
    cin.tie(0)->sync_with_stdio(0);
    cin>>n>>fa>>fb>>m;
    tra.insert(0,-inf);
    tra.insert(n,fa);
    trb.insert(n+1,inf);
    trb.insert(1,fb);
    trc.ipmx(fa,n);
    trd.ismi(fb,1);
    if(fa<=fb){ //special case
        for(int i=1;i<=n;i++) tsar.set(i,fa,1),tsbr.set(i,fb,1);
    }
    else{ //normal initialize
        nst.build();
        for(int i=1;i<=n;i++) tsal.set(i,fa,1),tsbl.set(i,fb,1);
    }
    while(m--){
        ll opt,x,y;
        cin>>opt>>x>>y;
        switch(opt){
            case 1:{ //prefix chkmin
                int p=tra.getnext(x);
                if(tra[p]<=y) break;
                int fi=x;
                p=tra.getprev(p-1);
                while(1){
                    fi=p+1;
                    if(tra[p]<y) break;
                    tra.erase(p);
                    p=tra.getprev(p);
                }
                tra.insert(x,y);
                tsal.ra(fi,x,y);
                tsar.ra(fi,x,y);
                trc.ipmx(y,x);
                int lp=trd.qsmi(y);
                if(lp>x) break;
                while(chkmove(lp,x));
                break;
            }
            case 2:{
                int p=trb.getprev(x);
                if(trb[p]>=y) break;
                int fi=x;
                p=trb.getnext(p+1);
                while(1){
                    fi=p-1;
                    if(trb[p]>y) break;
                    trb.erase(p);
                    p=trb.getnext(p);
                }
                trb.insert(x,y);
                tsbl.ra(x,fi,y);
                tsbr.ra(x,fi,y);
                trd.ismi(y,x);
                int rp=trc.qpmx(y);
                if(rp<x) break;
                while(chkmove(x,rp));
                break;
            }
            case 3:{
                ll res=0;
                res+=tsal.sum(x,y)-tsbl.sum(x,y);
                res+=tsbr.sum(x,y)-tsar.sum(x,y);
                cout<<res<<'\n';
                break;
            }
        }
    }
    return 0;
}

::::