支配点对小记

Eterna · 2025-09-16 19:58:09 · 算法·理论

支配点对

例题 1

给定一棵 n 个结点的树，有边权。有 m 次询问，每次询问求有几个不同的 \mathrm{dep}(\mathrm{LCA}(x,y))，其中 l \le x,y \le r。

看起来是一个非常难的问题。

对于相同 \mathrm{LCA}(x,y) 对应的 \mathrm{dep}(\mathrm{LCA(x,y)}) 肯定一样，我们先考虑计数不同 \mathrm{LCA}(x,y)。

对于两个点对 (a,b),(x,y)，其中 x \le a \le b \le y,\mathrm{LCA}(a,b)=\mathrm{LCA}(x,y)，我们称 (x,y) 支配了 (a,b)。可以发现被其他点对支配的点对一定对答案没有贡献。因为它们的 \mathrm{LCA} 一样，而且当我们询问到 (a,b) 就一定可以询问到 (x,y)。

我们称没有被其他点对支配的点对为支配对。则我们只需要考虑支配对的贡献。

考虑如何找支配对。

我们钦定一个 k，考虑怎样的两个点 x,y 对应的 \mathrm{LCA}(x,y)=k。

容易发现当 x,y 在 k 的不同子树中，它们的 \mathrm{LCA}(x,y) 一定为 k。否则它们的 \mathrm{LCA}(x,y) 一定不为 k。

依次枚举 k 的某一子树，将前面算过的子树中的结点插入到一个 set 里。若 x 在这一子树，我们只需要在 set 中找前驱后继就是支配对。

但是这样复杂度是 \mathcal {O}(n^2 \log n)。

考虑 k 由下至上枚举，然后处理 \mathrm{LCA}(x,y)=k 的情况是 set 直接从重儿子继承过来，这样整个重儿子的结点都不需要重新加入 set。

对于一个结点，因为重儿子子树结点数大于所有轻儿子，依次合并轻儿子的过程相当于启发式合并。轻儿子中所有结点所处集合的大小至少翻倍，故对于每一个结点，我们最多合并 \mathcal{O}(\log n) 次。

这也说明了支配对的数量是 \mathcal {O}(n \log n) 的。

对于每个支配对及其贡献 (x,y,t)，我们按 x 排序。对于每一组询问 (l,r)，我们按 l 排序。然后从 n 到 1 扫描线，插入 x=i 的贡献，计算 l=i 的询问。当然上述过程可以全部反着来。

我们希望 l \le x \le y \le r，对于 l \le x 显然一定满足。考虑 y \le r，因为我们是在数颜色，所以只需要找最小的 y 考虑。

维护每种 t 对应的最小的 y，插入到树状数组即可快速查询。对于 \mathrm{dep}(\mathrm{LCA}(x,y))，简单替换贡献即可。另外本题需要对 \mathrm{dep}(x) 离散化。

复杂度是 \mathcal {O}(n \log^2 n + m \log n)。

#include<bits/stdc++.h>
#define int long long
#define rd read()
#define gc pa == pb && (pb = (pa = buf) + fread(buf, 1, 100000, stdin), pa == pb) ? EOF : *pa++
using namespace std;
static char buf[100000], * pa(buf), * pb(buf);
inline int read()
{
    register int x=0,ss=1,s=gc;
    while(!isdigit(s)&&s!='-')s=gc;
    if(s=='-')ss=-1,s=gc;
    while(isdigit(s))x=(x<<1)+(x<<3)+(s^48),s=gc;
    return ss*x;
}
const int N=100005,M=500005;
int n,m,ans[M],son[N],siz[N],dep[N],pos[N];
map<int,int> mp;
vector<pair<int,int> > v[N],p[N],q[N];
//p存下所有支配对
set<int> s;
struct BIT
{
    int c[N];
    inline void add(int x,int y){while(x<=n+3)c[x]+=y,x+=(x&-x);}
    inline int ask(int x){int s=0;while(x)s+=c[x],x^=(x&-x);return s;}
}T;
inline void get(int x,int w)
{
    auto i=s.lower_bound(x);
    if(i!=s.end())p[x].push_back({*i,w});
    if(i!=s.begin())--i,p[*i].push_back({x,w});
}
inline void find(int x,int f,int w){get(x,w);for(auto [i,j]:v[x])if(i!=f)find(i,x,w);}
inline void add(int x,int f){s.insert(x);for(auto [i,j]:v[x])if(i!=f)add(i,x);}
inline void dfs(int x,int f)
{
    siz[x]=1;
    for(auto [i,j]:v[x])if(i!=f)
    {
        dep[i]=dep[x]+j,dfs(i,x),siz[x]+=siz[i];
        if(siz[son[x]]<siz[i])son[x]=i;
    }
}
inline void sol(int x,int f)
{
    for(auto [i,j]:v[x])if(i!=f&&i!=son[x])sol(i,x),s.clear();  
    if(son[x])sol(son[x],x);
    s.insert(x),p[x].push_back({x,dep[x]});
    for(auto [i,j]:v[x])if(i!=f&&i!=son[x])find(i,x,dep[x]),add(i,x);
}
signed main()
{
    n=rd,m=rd;
    for(int i=1,x,y,w;i<n;i++)
    {
        x=rd,y=rd,w=rd;
        v[x].push_back({y,w});
        v[y].push_back({x,w});
    }
    dfs(1,0);
    int cnt=0;
    for(int i=1;i<=n;i++)
    {
        if(!mp[dep[i]])mp[dep[i]]=++cnt;
        dep[i]=mp[dep[i]];
    }
    for(int i=1;i<=cnt;i++)pos[i]=n+1;
    sol(1,0);
    for(int i=1,l;i<=m;i++)l=rd,q[l].push_back({rd,i});
    for(int i=n;i>=1;i--)
    {
        for(auto [j,k]:p[i])T.add(pos[k],-1),pos[k]=min(pos[k],j),T.add(pos[k],1);
        for(auto [j,k]:q[i])ans[k]=T.ask(j);
    }
    for(int i=1;i<=m;i++)cout<<ans[i]<<'\n';
    return 0;
}

*例题 2

给定一棵 n 个结点的树，有 m 次询问，每次询问有多少个二元组 \mathrm{L},\mathrm{R}，满足 l\le \mathrm{L}\le \mathrm{R}\le r，且对任意 \mathrm{L}\le a_x\le a_y\le \mathrm{R}，有 x,y 在树上的最近公共祖先 z 满足 \mathrm{L}\le a_z\le \mathrm{R}。

考虑单个点对 (x,y) 使得那些区间不合法。

设 z=\mathrm{LCA}(x,y)，考虑以下情况：

1.对于 a_x \le a_y \le a_z，不合法的区间包含 a_x,a_y，而不包含 a_z。故不合法的区间 [l,r] 满足 l \le a_x,r \in [a_y,a_z)。

2.对于 a_x \le a_z \le a_y，它对于所有区间都不存在约束。

3.对于 a_z \le a_x \le a_y，易知 l \in (a_z,a_x],r \ge a_y。

然后将所有点对拿下来做扫描线是 \mathcal {O}(n^2 \log n) 的。

继续考虑哪些点对没有用。钦定一个 z，然后 a_z 不变，x,y 分别在 z 的两个不同子树。

可以发现对于一个 x，只有最小的 a_y \ge a_x 和最大的 a_y \le a_x 的 y 有用。我们将 a_i 丢到 set 里找前驱后继即可，启发式合并复杂度正确。可以发现支配对的数量是 \mathcal {O}(n \log n)。

然后将每个支配对对应的 r 挂在序列上，相当于区间加，区间历史 0 的数量。

维护区间最小值 x，最小值出现次数 y，历史 0 出现次数 z。

每经过一个时刻，对于 x=0 的结点 z \gets y+z。

然后复杂度是 \mathcal {O}(n \log^2 n + m \log n)。

#include<bits/stdc++.h>
#define ll long long
#define rd read()
#define gc pa == pb && (pb = (pa = buf) + fread(buf, 1, 100000, stdin), pa == pb) ? EOF : *pa++
using namespace std;
static char buf[100000], * pa(buf), * pb(buf);
inline int read()
{
    unsigned register int x=0,s=gc;
    while(!isdigit(s))s=gc;
    while(isdigit(s))x=(x<<1)+(x<<3)+(s^48),s=gc;
    return x;
}
const int N=200005;
int n,m,a[N],son[N],siz[N];
ll ans[N];
struct node{int x,y,z;};
vector<node> k[N];
vector<pair<int,int> > q[N];
vector<int> v[N];
set<int> s;
inline void insert(int x,int y,int z)
{
    if(y<z)k[y].push_back({1,x,1}),k[z].push_back({1,x,-1});
    if(z<x)k[y].push_back({z+1,x,1});
}
inline void dfs(int x,int f)
{
    siz[x]=1;
    for(int i:v[x])if(i!=f)
    {
        dfs(i,x),siz[x]+=siz[i];
        if(siz[son[x]]<siz[i])son[x]=i;
    }
}
inline void get(int x,int z)
{
    auto i=s.lower_bound(x);
    if(i!=s.end())insert(x,*i,z);
    if(i!=s.begin())--i,insert(*i,x,z);
}
inline void find(int x,int f,int w){get(a[x],w);for(int i:v[x])if(i!=f)find(i,x,w);}
inline void add(int x,int f){s.insert(a[x]);for(int i:v[x])if(i!=f)add(i,x);}
inline void sol(int x,int f)
{
    for(int i:v[x])if(i!=f&&i!=son[x])sol(i,x),s.clear();
    if(son[x])sol(son[x],x);
    s.insert(a[x]);
    for(int i:v[x])if(i!=f&&i!=son[x])find(i,x,a[x]),add(i,x);
}
struct seg
{
    int mn[N<<2],cnt[N<<2],tag[N<<2],htg[N<<2];ll sum[N<<2];
    inline void pushup(int id)
    {
        int l=id<<1,r=id<<1|1;
        mn[id]=min(mn[l],mn[r]),sum[id]=sum[l]+sum[r];
        cnt[id]=cnt[l]*(mn[l]==mn[id])+cnt[r]*(mn[r]==mn[id]);
    }
    inline void push1(int id,int v){tag[id]+=v,mn[id]+=v;}
    inline void push2(int id,int v){htg[id]+=v,sum[id]+=1ll*cnt[id]*v;}
    inline void pushdown(int id)
    {
        if(tag[id])push1(id<<1,tag[id]),push1(id<<1|1,tag[id]),tag[id]=0;
        if(htg[id])
        {
            if(mn[id]==mn[id<<1])push2(id<<1,htg[id]);
            if(mn[id]==mn[id<<1|1])push2(id<<1|1,htg[id]);
            htg[id]=0;
        }
    }
    inline void build(int id,int l,int r)
    {
        if(l==r)return cnt[id]=1,void();
        int mid=l+r>>1;build(id<<1,l,mid),build(id<<1|1,mid+1,r),pushup(id);
    }
    inline ll ask(int id,int l,int r,int x,int y)
    {
        if(x<=l&&y>=r)return sum[id];
        int mid=l+r>>1,ans=0;pushdown(id);
        if(x<=mid)ans+=ask(id<<1,l,mid,x,y);
        if(y>mid)ans+=ask(id<<1|1,mid+1,r,x,y);
        return ans;
    }
    inline void add(int id,int l,int r,int x,int y,int v)
    {
        if(x<=l&&y>=r)
        {
            if(v)return push1(id,v);
            if(!mn[id])return push2(id,1);
            return;
        }
        int mid=l+r>>1;pushdown(id);
        if(x<=mid)add(id<<1,l,mid,x,y,v);
        if(y>mid)add(id<<1|1,mid+1,r,x,y,v);
        pushup(id);
    }
}T;
signed main()
{
    n=rd,m=rd;T.build(1,1,n);
    for(int i=1;i<=n;i++)a[i]=rd;
    for(int i=2;i<=n;i++)v[rd].push_back(i);
    dfs(1,0),sol(1,0);
    for(int i=1,l,r;i<=m;i++)l=rd,r=rd,q[r].push_back({l,i});
    for(int i=1;i<=n;i++)
    {
        for(auto [l,r,w]:k[i])T.add(1,1,n,l,r,w);
        T.add(1,1,n,1,i,0);
        for(auto [l,fl]:q[i])ans[fl]=T.ask(1,1,n,l,i);
    }
    for(int i=1;i<=m;i++)cout<<ans[i]<<'\n';
    return 0;
}

例题 3

给定一个序列 \{a\}，每次询问给定一个区间 [l,r]，求 \min_{l \le i,j \le r}\lvert a_i-a_j \rvert。

绝对值非负，分两次处理，每次只考虑 a_j-a_i 的值，其中 a_j-a_i 非负，并且有 i<j。第二次处理前，我们对于所有 a_i \gets -a_i。

那么从前向后枚举 j，对于每个 j 寻找支配对 (i,j)。

若 (i,j) 是一个有贡献的点对。我们希望找一个 k<i，使得 (k,j) 是一个有贡献的点对。

如上图，容易知道 (k,j) 不应被 (k,i) 或 (i,j) 支配。首先容易知道 a_i,a_k \le a_j。

对于 (i,j) 的影响，有 a_j-a_k < a_j-a_i，得 a_k>a_i。所以 a_i< a_k\le a_j。

对于 (k,i) 的影响，有 a_j-a_k < a_k-a_i，所以 a_k > \frac{a_i+a_j}{2}。

所以 k<i 是最大的满足 a_k \in (\frac{a_i+a_j}{2},a_j] 的数。插到线段树二分，然后 j \gets k 继续找，由于每次值域折半，所以支配对是 \mathcal {O}(n \log v ) 的。

询问挂在 r 上扫描线可以做到 \mathcal {O}(n \log n \log v + m \log n)。

#include<bits/stdc++.h>
#define N 300005
#define int long long
#define rd read()
#define gc pa == pb && (pb = (pa = buf) + fread(buf, 1, 100000, stdin), pa == pb) ? EOF : *pa++
using namespace std;
static char buf[100000], * pa(buf), * pb(buf);
inline int read()
{
    register int x=0,s=gc;
    while(!isdigit(s))s=gc;
    while(isdigit(s))x=(x<<1)+(x<<3)+(s^48),s=gc;
    return x;
}
const int inf=1000000001,V=inf-1;
int n,m,cnt,a[N],ans[N];
vector<pair<int,int> > q[N],v[N];
struct node{int ls,rs,mx;}t[N*20];
inline int New(){t[++cnt]={0,0,0};return cnt; }
struct seg
{
    int root=0;
    inline void pushup(int id){t[id].mx=max(t[t[id].ls].mx,t[t[id].rs].mx);}
    inline void modify(int &id,int l,int r,int x,int v)
    {
        if(!id)id=New();
        if(l==r)return t[id].mx=max(t[id].mx,v),void();
        int mid=l+r>>1;
        if(x<=mid)modify(t[id].ls,l,mid,x,v);
        else modify(t[id].rs,mid+1,r,x,v);
        pushup(id);
    }
    inline int ask(int id,int l,int r,int x,int y)
    {
        if(!id)return 0;
        if(x>r||y<l) return 0;
        if(x<=l&&y>=r)return t[id].mx;
        int mid=l+r>>1;
        return max(ask(t[id].ls,l,mid,x,y),ask(t[id].rs,mid+1,r,x,y));
    }
    inline int find(int l,int r){return ask(root,1,V,l,r);}
}T;
struct BIT
{
    int c[N];
    inline void clear(){memset(c,0x3f,sizeof(c));}
    inline int ask(int x)
    {
        int s=inf;
        while(x<=n)s=min(s,c[x]),x+=(x&-x);
        return s;
    }
    inline void chk(int x,int y){while(x)c[x]=min(c[x],y),x^=(x&-x);}
}G;
inline void sol()
{
    cnt=0,a[0]=inf,T.root=0;
    for(int j=1;j<=n;j++)
    {
        int i=T.find(1,a[j]);
        while(a[i]<a[j])v[j].push_back({i,a[j]-a[i]}),i=T.find((a[i]+a[j]>>1)+1,a[j]);
        if(a[i]==a[j])v[j].push_back({i,0});
        T.modify(T.root,1,V,a[j],j);
    }
}
signed main()
{
    n=rd;for(int i=1;i<=n;i++)a[i]=rd;m=rd;
    for(int i=1,l,r;i<=m;i++)l=rd,q[rd].push_back({l,i});
    sol();for(int i=1;i<=n;i++)a[i]=inf-a[i];
    sol(),G.clear();
    int cnt=0;
    for(int i=1;i<=n;i++)cnt+=v[i].size();
    for(int i=1;i<=n;i++)
    {
        for(auto [l,w]:v[i])G.chk(l,w);
        for(auto [l,id]:q[i])ans[id]=G.ask(l);
    }
    for(int i=1;i<=m;i++)cout<<ans[i]<<'\n';
    return 0;
}

*例题 4

给定一个带边权的有 n 个点的树，m 次询问，每次询问求起点和终点在 [l,r] 内的最短树上路径。

树上路径，考虑点分治。对于当前根 r，先找出所有的 d_x=\mathrm{dis}(x,r)。则对于任意一条路径 (x,y)，我们用 d_x+d_y 表示其长度。

对于在 r 同一颗子树的 x,y，我们会将其路径算长，但当我们继续递归，一定会算到正确的路径，所以这样做对答案没有影响。

于是我们有若干点对 (x,d_x)，按 x 增序排列。每次求 l \le x,y \le r 的最小的 d_x+d_y，我们不可能每次询问都来求一边 rmq。考虑找支配点对。

对于一个支配点对 (x,y)，显然满足 \max(d_x,d_y)\le \min _{i \in (x,y)}d_i，否则 x 或 y 可以向内缩，得到更优解。

如果 d_x \le d_y，d_x 为 y 之前第一个比 d_y 小的元素。如果 d_y \le d_x，d_y 为 x 之后第一个比 d_x 小的元素。

正反分别做单调栈维护，每个点贡献 \mathcal{O}(1) 个支配对。加上点分治，一共 \mathcal{O}(n \log n) 个支配对。

扫描线，二维数点即可。时间复杂度 \mathcal{O}(n \log^2 n +q \log n)，空间复杂度 \mathcal{O}(n \log n+q)。

#include<bits/stdc++.h>
#define int long long
#define rd read()
#define gc pa == pb && (pb = (pa = buf) + fread(buf, 1, 100000, stdin), pa == pb) ? EOF : *pa++
using namespace std;
static char buf[100000], * pa(buf), * pb(buf);
inline int read()
{
    register int x=0,s=gc;
    while(!isdigit(s))s=gc;
    while(isdigit(s))x=(x<<1)+(x<<3)+(s^48),s=gc;
    return x;
}
const int N=200005,M=1000005,inf=1e16;
bool vis[N];
int n,m,rt,sz,mx[N],siz[N],ans[M];
vector<pair<int,int> > v[N],q[N],p[N],d;
inline void chkmax(int &x,int y){x=(x<y?y:x);}
inline void chkmin(int &x,int y){x=(x>y?y:x);}
inline void find(int x,int f)
{
    siz[x]=1,mx[x]=0;
    for(auto [i,j]:v[x])
        if(i!=f&&!vis[i])find(i,x),siz[x]+=siz[i],chkmax(mx[x],siz[i]);
    chkmax(mx[x],sz-siz[x]);
    if(mx[x]<mx[rt])rt=x;
}
inline void get(int x,int l,int f)
{
    if(vis[x])return;
    d.push_back({x,l});
    for(auto [i,j]:v[x])if(i!=f)get(i,l+j,x);
}
inline void sol(int x)
{
    if(vis[x])return;
    vis[x]=1;
    for(auto [i,j]:v[x])get(i,j,x);
    d.push_back({x,0}),sort(d.begin(),d.end()); 
    stack<pair<int,int> > st;
    for(auto [i,j]:d)
    {
        while(st.size()&&st.top().second>j)st.pop();
        if(st.size())p[i].push_back({st.top().first,st.top().second+j});
        st.push({i,j});
    }
    while(st.size())st.pop();
    reverse(d.begin(),d.end());
    for(auto [i,j]:d)
    {
        while(st.size()&&st.top().second>j)st.pop();
        if(st.size())p[st.top().first].push_back({i,st.top().second+j});
        st.push({i,j});
    }
    d.clear();
    for(auto [i,j]:v[x])if(!vis[i])rt=0,sz=siz[i],find(i,x),sol(rt);    
}
struct BIT
{
    int c[N];
    inline void chk(int x,int y){while(x)chkmin(c[x],y),x^=(x&-x);}
    inline int ask(int x){int s=LONG_LONG_MAX;while(x<=n)chkmin(s,c[x]),x+=(x&-x);return s;}
}G;
signed main()
{
    n=rd;for(int i=1,x,y,w;i<n;v[x].push_back({y,w}),v[y].push_back({x,w}),++i)x=rd,y=rd,w=rd;
    m=rd;for(int i=1,l;i<=m;++i)l=rd,q[rd].push_back({l,i});
    mx[0]=n+1,rt=0,sz=n,find(1,0),sol(rt),memset(G.c,0x3f,sizeof(G.c));
    for(int i=1;i<=n;++i)
    {
        for(auto [l,k]:p[i])G.chk(l,k);
        for(auto [l,id]:q[i])ans[id]=G.ask(l);
    }
    for(int i=1;i<=m;++i)cout<<(ans[i]>inf?-1:ans[i])<<'\n';
    return 0;
}

*例题 5

给你一个长度为 n 的序列 \{a\}，共有 q 次询问，每次询问给你一个区间 [l,r]，求满足 l\le i,j,k\le r 且 a_i,a_j,a_k 为边长可以构成三角形，a_i+a_j+a_k 的最小值。

值域倍增分块，其中第 m 个块 B_m=[2^{m},2^{m+1})。容易知道在同一个块中容易选的 3 个均可以组成三角形。

若区间 [l,r] 在 B_k 中存在 \ge 3 个数，那么可以将其中最小的三个数之和贡献到答案。这个用线段树维护。对于其他的符合条件的 k'>k，他们显然无用。

找区间中某个块的数的个数，可以对每个块 B_m 开一个前缀和记录。同时，我们还可以选若干个 < 2^k 的数，按选这种数的个数讨论。

1. 若三角形中包含 \ge 2 个 <2^k 的数。

   因为块的数量是 \mathcal{O}(\log v) 的，而 [0,k) 中每个块只有 \mathcal{O}(1) 个元素，故 <2^k 的数在区间 [l,r] 只有 \mathcal{O}(\log v) 个。

   将这些元素全部取出。具体的，取出元素的过程分别求 l 的后继与 r 的前驱，对于每个块，这可以在 \mathcal{O}(n) 的时间内求出。将这些元素和 B_k 的最小元素一起从小到大排列，取出元素判一判即可，记为 [t_1 ,\ldots ,t_m]。

   对于一种三角形选法，其最长的两条边在 \{t_m\} 必然相邻。证明考虑最大边更大不优。所以当我们在 <2^k 的数中选了 =2 个时，其最长边为 B_k 的 [l,r] 的最小值。

   设目前考虑的点对为 (i,j-1,j)，则有 t_j-t_{j-1}<t_i。如果存在 j'>j，满足 t_{j'}-t_{j'-1}\ge t_j-t_{j-1}，那么 j' 一定无用。因为其对应的 t_{i'}\ge t_i。

   于是只用考虑前缀最小的 (t_j-t_{j-1})，它肯定是递减的，所以直接双指针即可。

   这部分的时间复杂度为 \mathcal{O}(n \log v)。

2. 若三角形中包含 = 1 个 <2^k 的数。

   判掉有数在 B_{k+1} 的情况。选了一个 <2^k 的数表示我们选了 2 个 B_k 中的数。

   枚举所有 < 2^k 的数 a_e，如果我们选了它。则我们选的另外两数 a_i,a_j 要满足 \lvert a_i-a_j\rvert <a_e。

   根据 1. 中的结论，a_i,a_j 一定是排序后相邻的两个数。所以当 \max(a_i,a_j) 最小时，(a_i+a_j) 也最小。

   将块中所有数从小到大排序，记为 [t_1 ,\ldots ,t_m]，依次插入。考虑统计支配对。

   若当前插入了 t_p，新增支配对一定要选 p，所以这些点对的 \max(a_i,a_j)=t_p 相等，只需要让 \lvert a_i-a_j\rvert 最小，这是区间最近点对。用 CF765F 的方法线段树二分，可以在 \mathcal{O}(n \log n \log v) 的时间找到所有支配对。

   于是现在有了 \mathcal{O}(n \log v) 个支配对 (I,J)，扫描线。然后每次会找 l \le I,J \le r, \lvert a_I-a_J\rvert<a_e 的最小 (a_I+a_J)。三维偏序，此时我们的复杂度不低于 \mathcal{O}(n \log n \log^2 v +q \log n \log v)，看起来不可以过。原因是维数过大。

   考虑什么样的询问 [l,r]，最小值可以枚举到 a_e，若 a_L,a_R 分别是 e 同块前后两个数，则 L < l\le r <R。我们称 [L+1,R-1] 为 e 的最小值区间。

   因为每个块中最小值区间长度总和是 \mathcal{O}(n) 的，所以最小值区间长度一共是 \mathcal{O}(n \log v) 的。如果在这些区间找 \lvert a_I-a_J\rvert<a_e 的支配对，一共有 \mathcal{O}(n \log ^2 v) 个。然后以 (i,j,a_i+a_j+a_e) 的形式扫描线即可。

   扫描线的结构中修改与查询的次数分别为 \mathcal{O}(n \log^2 v) 和 \mathcal{O}(q)。使用 \mathcal{O}(1)-\mathcal{O}(n^{\epsilon}) 的迭代分块即可。

   这部分的时间复杂度为 \mathcal{O}(n \log^2 v+q n^{\epsilon})。

这个做法空间复杂度是 \mathcal{O}(n \log^2 v)。是官方题解中的算法 1，比算法 2 好想，但是时空复杂度均劣于算法 2。

我们只需要一边扫描线一边找支配对即可做到 \mathcal{O}(n \log v) 空间，比算法 2 的 \mathcal{O}(n + v) 还要优。最后空间只跑了 200 MB。

时间上有点慢，但不太卡常。

#include<bits/stdc++.h>
#define rd read()
#define gc pa == pb && (pb = (pa = buf) + fread(buf, 1, 100000, stdin), pa == pb) ? EOF : *pa++
#define min(x,y) (x<y?x:y)
#define max(x,y) (x>y?x:y)
#define chkmin(x,y) (x=x<y?x:y)
using namespace std;
static char buf[100000], * pa(buf), * pb(buf);
inline int read()
{
    register int x=0,s=gc;while(!isdigit(s))s=gc;
    while(isdigit(s))x=(x<<1)+(x<<3)+(s^48),s=gc;
    return x;
}
const int N=250005,M=500005,LG=24,inf=1e8,V=1e7;
const int B1=21,B2=B1*B1,B3=B1*B1*B1;
const int S1=N/B1+5,S2=N/B2+5,S3=N/B3+5;
int n,m,cnt;
int a[N],b[N],c[N],sc[N],bl[N],p[N];
int p2[N],s2[N],MX[M];
int ql[M],qr[M],ans[M],pos[N],is[M];
vector<int> G[M],P[N],K[N],K2[N];
vector<pair<int,int> > Q[N];
inline bool cmp(int x,int y){return a[x]<a[y];}
inline bool cmp2(int x,int y){return x>y;}
struct SEG
{
    int mx[N<<2];
    inline void modify(int id,int v){id=pos[id],mx[id]=v;for(id>>=1;id;id>>=1)mx[id]=v;}
    inline int ask(int id,int l,int r,int x,int v)
    {
        if(mx[id]<v||l>x)return 0;
        if(l==r)return l;int mid=l+r>>1,X=0;
        if(mx[id<<1|1]>=v)X=ask(id<<1|1,mid+1,r,x,v);
        if(!X&&mx[id<<1]>=v)X=ask(id<<1,l,mid,x,v);
        return X;
    }
    inline int find(int l,int MX){return ask(1,1,n,l,MX);}
}fd;
struct BT
{
    int L1[S1],R1[S1],L2[S2],R2[S2],L3[S3],R3[S3];
    int mn1[S1],mn2[S2],mn3[S3],b1[N],b2[N],b3[N],C[N];
    inline void build()
    {
        memset(C,0x3f,sizeof(C)),memset(mn1,0x3f,sizeof(mn1));
        memset(mn2,0x3f,sizeof(mn2)),memset(mn3,0x3f,sizeof(mn3));
        for(int i=1;i<=n;++i)b1[i]=(i-1)/B1+1,b2[i]=(i-1)/B2+1,b3[i]=(i-1)/B3+1;
        for(int i=1;i<=b1[n];++i)L1[i]=R1[i-1]+1,R1[i]=min(n,i*B1);
        for(int i=1;i<=b2[n];++i)L2[i]=R2[i-1]+1,R2[i]=min(n,i*B2);
        for(int i=1;i<=b3[n];++i)L3[i]=R3[i-1]+1,R3[i]=min(n,i*B3);
    }
    inline int ask(int x)
    {
        int res=inf;
        for(int i=b3[n];i>b3[x];--i)chkmin(res,mn3[i]);
        for(int i=b2[R3[b3[x]]];i>b2[x];--i)chkmin(res,mn2[i]);
        for(int i=b1[R2[b2[x]]];i>b1[x];--i)chkmin(res,mn1[i]);
        for(int i=R1[b1[x]];i>=x;--i)chkmin(res,C[i]);
        return res;
    }
    inline void chk(int x,int y){chkmin(C[x],y),chkmin(mn1[b1[x]],y),chkmin(mn2[b2[x]],y),chkmin(mn3[b3[x]],y);}
}sl;
struct node
{
    int m1,m2,m3,mx;
    inline node operator +(const node &o)const
    {
        node res;
        res.mx=max(mx,o.mx);
        if(m1<o.m1)
        {
            res.m1=m1;
            if(m2<o.m1)res.m2=m2,res.m3=m3<o.m1?m3:o.m1;
            else res.m2=o.m1,res.m3=m2<o.m2?m2:o.m2;
        }
        else
        {
            res.m1=o.m1;
            if(m1<o.m2)res.m2=m1,res.m3=m2<o.m2?m2:o.m2;
            else res.m2=o.m2,res.m3=m1<o.m3?m1:o.m3;
        }
        return res;
    }
}t[N<<2],it;
struct seg
{
    inline void build(int id,int l,int r)
    {
        if(l==r)return t[id]={b[l],inf,inf,b[l]==inf?-inf:b[l]},void();
        int mid=l+r>>1;build(id<<1,l,mid),build(id<<1|1,mid+1,r);
        t[id]=t[id<<1]+t[id<<1|1];
    }
    inline node ask(int id,int l,int r,int x,int y)
    {
        if(x>r||y<l)return {inf,inf,inf,-inf};
        if(x<=l&&y>=r)return t[id];int mid=l+r>>1;
        return ask(id<<1,l,mid,x,y)+ask(id<<1|1,mid+1,r,x,y);
    }
}T;
inline void gt(int id,int l,int r)
{
    if(l==r)return pos[l]=id,void();
    int mid=l+r>>1;gt(id<<1,l,mid),gt(id<<1|1,mid+1,r);
}
signed main()
{
    n=rd,m=rd,sc[n+1]=n+1,sc[n+2]=n+1,a[n+1]=a[0]=inf,sl.build(),gt(1,1,n);
    for(int i=1;i<=n;bl[i]=__lg(a[i]),p[i]=i,s2[i]=n+1,++i)a[i]=rd;sort(p+1,p+n+1,cmp);
    for(int i=1;i<=m;++i)ql[i]=rd,qr[i]=rd,ans[i]=inf,Q[qr[i]].push_back({i,ql[i]});
    for(int i=0;i<=24;++i)
    {
        for(int j=1;j<=n;++j)
            if(bl[j]==i)b[j]=a[j],c[j]=c[j-1]+1;
        else b[j]=inf,c[j]=c[j-1];
        T.build(1,1,n);
        for(int j=n;j>=1;--j)sc[j]=(a[j]==b[j]?j:sc[j+1]);
        for(int j=1;j<=n;++j)
            if(a[j]==b[j])s2[j]=sc[sc[j+1]+1],p2[sc[sc[j+1]+1]]=j;
        for(int j=1,cnt,x,y,l,r;j<=m;++j)if(!is[j])
        {
            l=ql[j],r=qr[j],cnt=c[r]-c[l-1];
            if(cnt==1)G[j].push_back(a[sc[l]]);
            else if(cnt==2)
            {
                x=sc[l],y=sc[sc[l]+1];if(a[x]>a[y])swap(x,y);
                G[j].push_back(a[x]),G[j].push_back(a[y]);
            }
            else if(cnt>=3)
            {
                is[j]=i,it=T.ask(1,1,n,l,r),MX[j]=it.mx;
                chkmin(ans[j],it.m1+it.m2+it.m3),G[j].push_back(it.m1);
            }
        }else if(i==is[j]+1)
        {
            l=ql[j],r=qr[j],cnt=c[r]-c[l-1];
            if(cnt>0)
            {
                int MN=T.ask(1,1,n,l,r).m1;
                for(int e:G[j])if(e>MN-MX[j]){chkmin(ans[j],e+MN+MX[j]);break;}
            }
        }
    }
    for(int i=1,j,mn,h,P;i<=m;++i)
    {
        mn=inf,P=G[i].size(),j=1;
        while(j<P-1&&G[i][j-1]+G[i][j]<=G[i][j+1])++j;
        for(;j<G[i].size()-1;++j)
        {
            h=G[i][j+1]-G[i][j];
            if(mn>=h)
            {
                while(P>0&&G[i][P-1]>h)--P;
                if(P<j&&G[i][P]>h)chkmin(ans[i],G[i][P]+G[i][j]+G[i][j+1]);mn=h;
            }
        }
    }
    for(int J=1,i,j;J<=n;fd.modify(j,a[j]),++J)
    {
        j=p[J],i=fd.find(j,1<<bl[j]);
        while(a[i]<=a[j])P[j].push_back(i),i=fd.find(j,(a[i]+a[j]>>1)+1);
    }
    memset(fd.mx,0,sizeof(fd.mx));
    for(int J=1,i,j;J<=n;fd.modify(n-j+1,a[j]),++J)
    {
        j=p[J],i=n-fd.find(n-j+1,1<<bl[j])+1;
        while(a[i]<=a[j])P[i].push_back(j),i=n-fd.find(n-j+1,(a[i]+a[j]>>1)+1)+1;
    }
    for(int i=1;i<=n;++i)stable_sort(P[i].begin(),P[i].end(),cmp2);
    for(int e,E=n,R;E>=1;--E){e=p[E],R=s2[e];for(int j=e+1;j<R;++j)K[j].push_back(e);}
    for(int i=1,h;i<=n;++i)
    {
        for(int j=p2[i]+1;j<i;++j)for(int I:P[j])
        {
            if(I<=p2[i])break;
            if(i!=I&&a[i]>abs(a[I]-a[j])&&bl[i]<bl[I])sl.chk(min(i,I),a[I]+a[i]+a[j]);
        }
        for(int j:P[i])
        {
            h=abs(a[i]-a[j]);
            for(int e:K[i])
            {
                if(a[e]<=h)break;
                if(e!=j&&bl[e]<bl[i])sl.chk(min(e,j),a[e]+a[i]+a[j]);
            }
        }
        for(auto [id,l]:Q[i])chkmin(ans[id],sl.ask(l));
    }
    for(int i=1;i<=m;++i)
        if(ans[i]>=inf)cout<<"yumi!\n";
        else cout<<ans[i]<<'\n';
    return 0;
}