支配点对小记

支配点对

1

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

$1 \le n \le 10^5,1 \le m \le 5 \times 10^5$ 。

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

对于相同

\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)

。

CPP

#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}$ 。

$1\le n,m\le 2\times 10^5$ 。

考虑单个点对

(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)

。

CPP

#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$ 。

$1 \le n \le 10^5,1\le m \le 3 \times 10^5$ 。

绝对值非负，分两次处理，每次只考虑

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)

。

CPP

#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]$ 内的最短树上路径。

$1 \le n \le 2 \times 10^5,1\le m \le 10^6$ 。

树上路径，考虑点分治。对于当前根

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)

。

CPP

#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$ 的最小值。

$1\le n\le 2.5\times 10^5,1\le q\le 5\times 10^5,1\le a_i\le 10^7$ 。

值域倍增分块，其中第

m

个块

B_m=[2^{m},2^{m+1})

。容易知道在同一个块中容易选的

3

个均可以组成三角形。

若区间

[l,r]

在

B_k

中存在

\ge 3

个数，那么可以将其中最小的三个数之和贡献到答案。这个用线段树维护。对于其他的符合条件的

k'>k

，他们显然无用。

找区间中某个块的数的个数，可以对每个块

B_m

开一个前缀和记录。同时，我们还可以选若干个

< 2^k

的数，按选这种数的个数讨论。

若三角形中包含 $\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)$ 。
若三角形中包含 $= 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。

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

CPP

#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;
}

文章操作

支配点对

相关推荐

评论

支配点对小记