P7549 题解

· · 题解

前言：前几天学会块状链表之后被同学 热情推荐 的 好题。结果过了之后发现题解区块状链表题解又少又难懂，所以决定自己写一篇。

首先考虑的是两种查询操作如何做。区间极差的最大值，也就是该区间内的最大值减最小值，这个是容易发现的（因为大值变大优，小值变小优）。然后考虑区间极差的最小值，发现区间扩展之后极差肯定不降，所以直接考虑所有长度为 2 的子区间即可。

结果你发现最大值和最小值数据结构随便维护，这个“长度为 2 的区间的内部差的最小值”好像很难做，因为你有增加和删除（合并的本质也就是增 1 删 2）。

于是考虑暴力数据结构。显然朴素的分块不好处理增加和删除操作，因此考虑块状链表。

确定了数据结构就考虑在块状链表的每个节点上维护什么。根据刚才的讨论，我们维护最大值最小值还有那个长度为 2 的区间内部差最小值就都行了。设每一个块的数组大小为 len，这三个东西都容易在块内暴力地 O(len) 维护（插入记得分裂）。然后你查询的时候，max 询问就一块一块扫过去就行了，但是 min 操作由于区间之间位置的特殊性你必须把空节点都从链表里扔掉。

于是你就做好了。复杂度 O(M\times \max (len,\ \dfrac{n}{len}))，取 len=\sqrt{n} 可达最优复杂度，我取的 len 是 1000。

tips：封装会好写一点。

代码如下：

#include <bits/stdc++.h>
using namespace std;
const int N=1e3+5,inf=0x3f3f3f3f;
struct node{
    int pre,nxt,sz,maxi,mini,minc,num[N<<1];
    inline int lc(){return num[0];}
    inline int rc(){return num[sz-1];}
    inline void maintain(){
        maxi=mini=num[0],minc=inf;
        for(int i(1);i<sz;++i) minc=min(minc,abs(num[i]-num[i-1])),mini=min(mini,num[i]),maxi=max(maxi,num[i]);
    }
    inline void insert(int k,int bfr){
        num[sz++]=k;
        int p(sz-1);
        while(p>bfr) swap(num[p],num[p-1]),--p;
        maintain();
    }
    inline void erase(int k){
        int p(--k);
        while(p<sz) swap(num[p],num[p+1]),++p;
        --sz,maintain();
    }
    inline int query_maxi(int L,int R){
        int res(0);
        for(int i(L);i<=R;++i) res=max(res,num[i]);
        return res;
    }
    inline int query_mini(int L,int R){
        int res(inf);
        for(int i(L);i<=R;++i) res=min(res,num[i]);
        return res;
    }
    inline int query_minc(int L,int R){
        int res(inf);
        for(int i(L+1);i<=R;++i) res=min(res,abs(num[i]-num[i-1]));
        return res;
    }
};
int n,m,x,e,cnt,tot;
node lst[N];
string opt;
inline void split(int pr,int nt,int x){
    lst[pr].nxt=x,lst[nt].pre=x;
    lst[x].pre=pr,lst[x].nxt=nt;
    int mid(lst[pr].sz>>1);
    for(int i(mid);i<lst[pr].sz;++i) lst[x].num[i-mid]=lst[pr].num[i];
    lst[x].sz=lst[pr].sz-mid,lst[pr].sz>>=1;
    lst[pr].maintain(),lst[x].maintain();
}
inline void insert(int k,int bfr){
    if(!cnt){
        lst[++tot].insert(k,bfr),lst[0].pre=lst[0].nxt=tot,lst[tot].pre=lst[tot].nxt=0;
        lst[tot].maxi=lst[tot].mini=k,lst[tot].sz=1,lst[tot].minc=inf,++cnt;
        return;
    }
    int p(lst[0].nxt),cnt(0);
    for(;p;p=lst[p].nxt){
        if(cnt+lst[p].sz>=bfr){
            lst[p].insert(k,bfr-cnt);
            if(lst[p].sz>=2e3) split(p,lst[p].nxt,++tot),++cnt;
            return;
        }
        cnt+=lst[p].sz;
    }
}
inline void merge(int pr,int nt){lst[pr].nxt=nt,lst[nt].pre=pr;}
inline void erase(int x){
    int p(lst[0].nxt),cnt(0);
    for(;p;p=lst[p].nxt){
        if(cnt+lst[p].sz>=x){
            lst[p].erase(x-cnt);
            if(!lst[p].sz) merge(lst[p].pre,lst[p].nxt),--cnt;
            return;
        }
        cnt+=lst[p].sz;
    }
}
inline void chg(int k,int bfr){insert(k,bfr+1),erase(bfr),erase(bfr);}
inline int solve_max(int L,int R){
    --L,--R;
    int maxi(0),mini(inf),p(lst[0].nxt),cnt(0);
    for(;p;p=lst[p].nxt){
        if(cnt<=L&&R<cnt+lst[p].sz){maxi=max(maxi,lst[p].query_maxi(L-cnt,R-cnt)),mini=min(mini,lst[p].query_mini(L-cnt,R-cnt));return maxi-mini;}
        else if(cnt<=L&&L<cnt+lst[p].sz) maxi=max(maxi,lst[p].query_maxi(L-cnt,lst[p].sz-1)),mini=min(mini,lst[p].query_mini(L-cnt,lst[p].sz-1));
        else if(cnt<=R&&R<cnt+lst[p].sz) maxi=max(maxi,lst[p].query_maxi(0,R-cnt)),mini=min(mini,lst[p].query_mini(0,R-cnt));
        else if(L<=cnt&&cnt+lst[p].sz-1<=R) maxi=max(maxi,lst[p].maxi),mini=min(mini,lst[p].mini);
        else if(R<cnt) return maxi-mini;
        cnt+=lst[p].sz;
    }
    return maxi-mini;
}
inline int solve_min(int L,int R){
    --L,--R;
    int minc(inf),p(lst[0].nxt),cnt(0),rc;
    for(;p;p=lst[p].nxt){
        if(cnt<=L&&R<cnt+lst[p].sz){minc=min(minc,lst[p].query_minc(L-cnt,R-cnt));return minc;}
        else if(cnt<=L&&L<cnt+lst[p].sz) minc=min(minc,lst[p].query_minc(L-cnt,lst[p].sz-1)),rc=lst[p].rc();
        else if(cnt<=R&&R<cnt+lst[p].sz){
            minc=min(minc,lst[p].query_minc(0,R-cnt));
            minc=min(minc,abs(rc-lst[p].lc()));
            rc=lst[p].rc();
        }
        else if(L<=cnt&&cnt+lst[p].sz-1<=R){
            minc=min(minc,lst[p].minc);
            minc=min(minc,abs(rc-lst[p].lc()));
            rc=lst[p].rc();
        }
        else if(R<cnt) return minc;
        cnt+=lst[p].sz;
    }
    return minc;
}
int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin >> n >> m;
    for(int i(1);i<=n;++i) cin >> e,insert(e,i-1);
    while(m--){
        cin >> opt >> x >> e;
        if(opt=="merge") chg(e,x);
        else if(opt=="insert") insert(e,x);
        else if(opt=="max") cout << solve_max(x,e) << '\n';
        else cout << solve_min(x,e) << '\n';
    }
    return 0;
}