P11983 [JOIST 2025] 展览会 3 / Exhibition 3 做题记录

给定一个长 $n$ 的序列 $a$ 和 $m$ 个区间 $[l_i,r_i]$ ，你要重排 $a$ 的元素，使得序列 $b_i=\max\limits_{j\in[l_i,r_i]} a_j$ 的字典序最大，输出字典序最大的序列 $b$ 。

$1\le n,m\le 10^5$ ， $1\le a_i\le n$ ， $1\le l_i\le r_i\le n$ 。

考虑贪心，若 $a$ 互不相同，则可以从大到小考虑每个 $a_i$ ：

在区间序列上从前往后扫，维护 $b_j=a_i$ 的区间集合 $S$ 。扫到一个 $b_j$ 尚未确定的区间 $[l_j,r_j]$ 时，若加入当前区间后 $S$ 中所有区间还有交，则令 $b_j=a_i$ ，并向 $S$ 加入当前区间；

而 $a$ 可能有重复元素，故需要稍微修改一下贪心。依旧是从大到小考虑 $[1,n]$ 中的每个数 $x$ ，设 $x$ 在 $a$ 中出现了 $cnt$ 次：

在区间序列上从前往后扫，维护 $b_j=x$ 的区间集合 $S$ 。扫到一个 $b_j$ 尚未确定的区间 $[l_j,r_j]$ 时，若加入当前区间后 $S$ 可以划分成 $cnt$ 个子集并满足每个子集中所有区间有交，则令 $b_j=a_i$ ，并向 $S$ 加入当前区间；

不难发现只要每次准确地找到 $b_j=x$ 的那些位置，均摊时间复杂度就是对的。所以现在问题变为对于一个 $x$ ，如何快速找到所有 $b_j=x$ 的位置 $j$ ，并将它们删去。

先考虑怎么判定一个区间集合 $S$ 是否合法（能被划分为 $cnt$ 个有交子集），这其实等价于判断能否选 $cnt$ 个点使得 $S$ 中区间均包含至少一个点。这是一个经典贪心：

将 $S$ 中区间按右端点排序后从前往后扫，同时维护最后一个选择的点 $x$ ；
若当前区间 $[l,r]$ 满足 $l>x$ ，那么在 $r$ 处额外选择一个点，令 $x=r$ ；

注意到这个贪心实际上能求出第 $i$ 个点的最大位置 $rb_i$ ，而按 $l$ 排序反过来贪心一次能求出第 $i$ 个点的最小位置 $lb_i$ 。故有一个结论：

区间 $[l,r]$ 能加入区间集合 $S$ 当且仅当其和 $S$ 导出的某个 $[lb_i,rb_i]$ 有交。

并且这些区间还是两两不交的：如果两个区间相交，则在它们的交中放一个点就可以了，不用在两个区间中都点。

那么考虑求出一段合法的前缀 $[l_1,r_1],[l_2,r_2],\dots,[l_k,r_k]$ ，此时要么 $b$ 确定完了，要么我们就确定了 $S$ 导出的这 $cnt$ 个区间。接下来就可以通过线段树不断找到编号最小的和这些区间有交的区间。

这一步不能直接二分，因为单次 check 复杂度是 $O(k\log k)$ 的。考虑经典技巧，先倍增确定出 $k\in [2^p,2^{p+1})$ ，再在 $[2^p,2^{p+1})$ 中二分 $k$ 。这样由于最终至少删除前 $2^p$ 个区间，故复杂度是对的，即均摊 $O(m\log m)$ 。

现在问题变为不断找到编号最小的合法区间，将其加入 $S$ 中，并维护这 $cnt$ 个区间。

考虑若区间 $[l_i,r_i]$ 完全包含了某个区间 $[lb_j,rb_j]$ ，则 $[l_i,r_i]$ 无论如何一定能加入 $S$ 。这是因为 $[lb_j,rb_j]$ 在之后只会缩减。并且这样的区间显然不会对这 $cnt$ 个 $[lb_j,rb_j]$ 造成影响。故可以使用一棵线段树维护 $l_i\le lb_j$ 的最大 $r_i$ 及对应的编号 $i$ ，每次 $[lb_j,rb_j]$ 改变的时候都不断找到完全包含它的区间，将它们删掉。

那么现在只需要找到 $\exist j,l_i\in [lb_j,rb_j]$ 和 $\exist j,r_i\in [lb_j,rb_j]$ 的最小的 $i$ 即可，这也可以通过线段树和 set 简单维护。

接下来需要考虑加入一个区间 $[l,r]$ 对这 $cnt$ 个区间的影响：

若 $\exist j,l\in [lb_j,rb_j]$ ，则显然只会影响到 $lb_{[1,j]}$ 。而注意到一个区间的左端点只会在一段区间的时间内成为某一个 $lb_j$ ，故直接暴力修改就是对的。这里还要开一棵线段树找到 $S$ 中右端点 $< x$ 的区间的最大左端点；
若 $\exist j,r\in [lb_j,rb_j]$ ，则显然只会影响到 $rb_{[j,cnt]}$ ，同上，暴力修改即可；

故总时间复杂度 $O(n\log n)$ （认为 $n,m$ 同阶），代码如下：

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

using namespace std;

const int S=100005;

int n,m,a[S];
int lb[S],rb[S],nxt[S],pre[S];
int mn[S<<2],mx[S<<2];
set<int> idl[S],idr[S];
set<pair<int,int> > str[S];
int mnr[S],mxl[S],ans[S];

inline int calc(int p,int len)
{
	vector<pair<int,int> > vec;
	for(int i=1,u=p;i<=len;i++,u=nxt[u])
		vec.emplace_back(rb[u],lb[u]);
	sort(vec.begin(),vec.end());
	int x=0,res=0;
	for(auto t:vec)
		if(x<t.second) x=t.first,res++; 
	return res;
}
inline void gets(int p,int len,vector<pair<int,int> > &res)
{
	vector<pair<int,int> > vec;
	for(int i=1,u=p;i<=len;i++,u=nxt[u])
		vec.emplace_back(rb[u],lb[u]);
	sort(vec.begin(),vec.end());
	int x=0;
	for(auto t:vec)
		if(x<t.second) res.emplace_back(0,x=t.first);
	vec.clear();
	for(int i=1,u=p;i<=len;i++,u=nxt[u])
		vec.emplace_back(lb[u],rb[u]);
	sort(vec.begin(),vec.end(),greater<pair<int,int> >());
	x=n+1;
	int pos=res.size()-1;
	for(auto t:vec)
		if(x>t.second) res[pos--].first=x=t.first;
}

inline void upda(int u)
{
	int ls=u<<1,rs=u<<1|1;
	mn[u]=min(mn[ls],mn[rs]);
	mx[u]=rb[mx[ls]]>rb[mx[rs]]?mx[ls]:mx[rs];
}
inline void initu(int u,int p)
{
	mn[u]=m+1;
	if(!idl[p].empty()) mn[u]=min(mn[u],*idl[p].begin());
	if(!idr[p].empty()) mn[u]=min(mn[u],*idr[p].begin());
	mx[u]=0;
	if(!str[p].empty()) mx[u]=str[p].rbegin()->second;
}
void build(int u,int l,int r)
{
	if(l==r) return initu(u,l),void();
	int mid=l+r>>1;
	build(u<<1,l,mid),build(u<<1|1,mid+1,r);
	upda(u);
}
void updp(int u,int l,int r,int p)
{
	if(l==r) return initu(u,l),void();
	int mid=l+r>>1;
	if(p<=mid) updp(u<<1,l,mid,p);
	else updp(u<<1|1,mid+1,r,p);
	upda(u);
}
int quelr(int u,int l,int r,int L,int R,int &rmx)
{
	if(l>R||r<L) return m+1;
	if(l>=L&&r<=R) return rmx=rb[rmx]>rb[mx[u]]?rmx:mx[u],mn[u];
	int mid=l+r>>1,res=m+1;
	if(L<=mid) res=min(res,quelr(u<<1,l,mid,L,R,rmx));
	if(R>=mid+1) res=min(res,quelr(u<<1|1,mid+1,r,L,R,rmx));
	return res;
}

inline void delp(int p)
{
	nxt[pre[p]]=nxt[p];
	pre[nxt[p]]=pre[p];
	idl[lb[p]].erase(p),idr[rb[p]].erase(p);
	str[lb[p]].erase(make_pair(rb[p],p));
	updp(1,1,n,lb[p]),updp(1,1,n,rb[p]);
}

namespace seg2
{
	int mn[S<<2];
	inline void upda(int u){mn[u]=min(mn[u<<1],mn[u<<1|1]);}
	int quelr(int u,int l,int r,int L,int R)
	{
		if(l>R||r<L) return n+1;
		if(l>=L&&r<=R) return mn[u];
		int mid=l+r>>1,res=n+1;
		if(L<=mid) res=min(res,quelr(u<<1,l,mid,L,R));
		if(R>=mid+1) res=min(res,quelr(u<<1|1,mid+1,r,L,R));
		return res;
	}
	void updp(int u,int l,int r,int p,int x)
	{
		if(l==r) return mn[u]=x,void();
		int mid=l+r>>1;
		if(p<=mid) updp(u<<1,l,mid,p,x);
		else updp(u<<1|1,mid+1,r,p,x);
		upda(u);
	}
}
namespace seg3
{
	int mx[S<<2];
	inline void upda(int u){mx[u]=max(mx[u<<1],mx[u<<1|1]);}
	int quelr(int u,int l,int r,int L,int R)
	{
		if(l>R||r<L) return 0;
		if(l>=L&&r<=R) return mx[u];
		int mid=l+r>>1,res=0;
		if(L<=mid) res=max(res,quelr(u<<1,l,mid,L,R));
		if(R>=mid+1) res=max(res,quelr(u<<1|1,mid+1,r,L,R));
		return res;
	}
	void updp(int u,int l,int r,int p,int x)
	{
		if(l==r) return mx[u]=x,void();
		int mid=l+r>>1;
		if(p<=mid) updp(u<<1,l,mid,p,x);
		else updp(u<<1|1,mid+1,r,p,x);
		upda(u);
	}
}

int main()
{
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cin>>n>>m;
	for(int i=1;i<=n;i++) cin>>a[i];
	for(int i=1;i<=m;i++) cin>>lb[i]>>rb[i];
	for(int i=1;i<=m;i++) nxt[i]=i+1,pre[i]=i-1;
	nxt[0]=1;
	sort(a+1,a+n+1,greater<int>());
	for(int i=1;i<=m;i++)
	{
		idl[lb[i]].insert(i),idr[rb[i]].insert(i);
		str[lb[i]].emplace(rb[i],i);
	}
	build(1,1,n);
	for(int i=1;i<=(S<<2)-3;i++) seg2::mn[i]=n+1,seg3::mx[i]=0;
	for(int i=1;i<=n;i++) mnr[i]=n+1;
	int prem=m;
	for(int i=1;i<=n&&prem>0;)
	{
		int cnt=0;
		while(i+cnt<=n&&a[i+cnt]==a[i]) cnt++;
		int len=1;
		while(len*2<=prem&&calc(nxt[0],len*2)<=cnt) len*=2;
		int l=len+1,r=min(prem,len*2);
		while(l<=r)
		{
			int mid=l+r>>1;
			if(calc(nxt[0],mid)<=cnt) len=mid,l=mid+1;
			else r=mid-1;
		}
		vector<pair<int,int> > seg;
		gets(nxt[0],len,seg);
		set<int> st;
		vector<int> del;
		auto work=[&](int p)
		{
			del.push_back(p);
			mnr[lb[p]]=min(mnr[lb[p]],rb[p]);
			mxl[rb[p]]=max(mxl[rb[p]],lb[p]);
			seg2::updp(1,1,n,lb[p],mnr[lb[p]]);
			seg3::updp(1,1,n,rb[p],mxl[rb[p]]);
			ans[p]=a[i];
			delp(p);
			prem--;
		};
		auto fndid=[&](int x)
		{
			int p=upper_bound(seg.begin(),seg.end(),make_pair(x,n+1))-seg.begin()-1;
			bool inx=(p>=0&&seg[p].second>=x);
			return inx?p:-1;
		};
		auto ins=[&](int i)
		{
			int rmx=0;
			// printf("ins %d\n",quelr(1,1,n,seg[i].first,seg[i].second,rmx));
			st.insert(quelr(1,1,n,seg[i].first,seg[i].second,rmx));
		};
		auto doit=[&](pair<int,int> x){
			while(1)
			{
				int rmx=0;
				quelr(1,1,n,1,x.first,rmx);
				if(rb[rmx]>=x.second)
				{
					int p=rmx;
					work(p);
					int pl=fndid(lb[p]),pr=fndid(rb[p]);
					if(pl!=-1) ins(pl);
					if(pr!=-1) ins(pr);
				}
				else break;
			}
		};
		auto updrb=[&](int id)
		{
			for(int i=id;i<seg.size();i++)
			{
				int nr=seg2::quelr(1,1,n,i==0?1:seg[i-1].second+1,n);
				if(nr==seg[i].second)
				{
					ins(i);
					break;
				}
				seg[i].second=nr;
				ins(i);
				doit(seg[i]);
			}
		};
		auto updlb=[&](int id)
		{
			for(int i=id;i>=0;i--)
			{
				int nl=seg3::quelr(1,1,n,1,i+1==seg.size()?n:seg[i+1].first-1);
				if(nl==seg[i].first)
				{
					ins(i);
					break;
				}
				seg[i].first=nl;
				ins(i);
				doit(seg[i]);
			}
		};
		// printf("%d: ",a[i]);
		// for(auto t:seg) printf("[%d %d] ",t.first,t.second);
		// printf("\n");
		for(int i=1;i<=len;i++) work(nxt[0]);
		for(auto t:seg) doit(t);
		for(int i=0;i<seg.size();i++) ins(i);
		while(!st.empty())
		{
			int p=*st.begin();
			// printf("pop %d\n",p);
			if(p==m+1||ans[p]!=0)
				st.erase(p);
			else
			{
				st.erase(p);
				int pl=fndid(lb[p]),pr=fndid(rb[p]);
				// printf("> %d: [%d %d] (%d %d)\n",
					// p,lb[p],rb[p],pl,pr);
				if(pl==-1&&pr==-1) continue;
				work(p);
				if(pl!=-1) updlb(pl);
				if(pr!=-1) updrb(pr);
				// for(auto t:seg) printf("[%d %d] ",t.first,t.second);
				// printf("\n");
			}
		}
		for(int p:del)
		{
			mnr[lb[p]]=n+1;
			mxl[rb[p]]=0;
			seg2::updp(1,1,n,lb[p],mnr[lb[p]]);
			seg3::updp(1,1,n,rb[p],mxl[rb[p]]);
		}
		i+=cnt;
	}
	for(int i=1;i<=m;i++) cout<<ans[i]<<'\n';
	return 0;
}

P11983 [JOIST 2025] 展览会 3 / Exhibition 3 做题记录

感谢您的支持，我会继续努力的!