自动搬运

查看原文

来自洛谷，原作者为

	Lynkcat Reset.

搬运于2025-08-24 22:47:00，当前版本为作者最后更新于2023-04-27 09:28:16，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

先来一个不是很正经的 $O(n^2)$ 做法。

首先考虑显然有一个简单的 $O(n^2\log n)$ 的暴力，操作 $1$ 暴力排序，操作 $2$ 直接 $O(n)$ 扫。事实上操作 $2$ 直接 $O(len)$ 扫是相当优的，因为寻址是连续的。

然后考虑怎么优化，因为每次操作 $1$ 的排序保证区间包含或不交，所以每次相当于合并若干个有序段，这部分可以 $O(n\log ^2n)$ 启发式合并 set，然后再把当前这个区间的 set 遍历一边放回原序列。

这样做到 $O(n^2)$，其实已经很优秀了，但是卡满的情况下（比如每次对 $[1,i]$）排序，这样每次遍历的 set 大小会被卡满，而又因为遍历 set 事实上是瓶颈，所以会跑得挺满（本机 $12$s）。

事实上观察到上面这种情况每次合并的有序段不会很多，所以我们考虑当有序段个数小于一个很小的常数 $B$ 时，做 $B$ 次归并排序。这样子就能通过这个题了，我取了 $B=3$。

inline void merge(multiset<int>&x,multiset<int>&y)
{
	if (x.size()<y.size()) x.swap(y);
	for (auto u:y) x.insert(u);multiset<int>().swap(y);
}
void BellaKira()
{
	cin>>n;
	for (int i=1;i<=n;i++)
	{
		cin>>a[i];
		s[i].insert(a[i]);
		S.insert(i);
	}
	S.insert(n+1);
	cin>>q;
	ll all=0;
	int ooo=0;
	while (q--)
	{
		int opt,l,r;
		cin>>opt;
		if (opt==1)
		{
			cin>>l>>r;
			r=min(r,n);
			auto it=S.lower_bound(l);
			if (it==S.end()) continue;
			it++;
			auto itl=it;
			int t=0;
			while (it!=S.end())
			{
				if ((*it)>r) break;
				merge(s[l],s[*it]);
				it++;
				t++;
			}
			if (t>=3)
			{
				S.erase(itl,it);
				int o=l-1;
				for (auto u:s[l])
				{
					a[++o]=u;
				}
			} else
			{
				it=itl;
				while (it!=S.end())
				{
					if ((*it)>r) break;
					auto it1=it;
					it1++;
					// cout<<"???"<<l<<" "<<(*it)<<" "<<(*it1)<<endl;
					inplace_merge(a+l,a+(*it),a+(*it1));
					it++;
				}
				S.erase(itl,it);
			}
		} else
		{
			cin>>l>>r;
			int mx=0;
			ll ans=0;
			for (int i=l;i<=r;i++)
			{
				if (mx>a[i])
					ans=max(ans,1ll*a[i]*mx);
				mx=max(mx,a[i]);
			}
			all^=ans;
			cout<<ans<<'\n';
		}
	}
}

正经做法是个稍微有点 trivial 的东西，但是不那么好写。

考虑没有修改时的一个做法，就是我们每次线段树上维护一个 pair 表示当前节点答案以及当前节点的 $\max$。那么每次相当于合并的时候，在右儿子区间里找跟 $\max$ 最接近的比 $\max$ 小的数更新答案，右边这部分可以用主席树维护每个区间的权值集合。

那考虑有了排序，我们需要维护整个 $a$ 序列的变化，怎么维护呢？

其实并不需要维护，如果我们维护了每个有序段，那么 $a$ 序列的某个区间是可以表示成若干个整个有序段和“某个有序段的大于等于某个数的集合或小于等于某个数的集合”。

那就好办了，正好跟我们需要做的事情是一样的。

我们考虑对于两个点 $i,j(a_i>a_j)$ 产生的贡献直到 $i$ 与 $j$ 合并成一个有序段之前都是存在的。继续用线段树维护上述的那个 pair。

那么每次排序相当于合并有序段，然后把当前这个区间内的所有节点答案设成 $0$。

线段树上合并两个 pair 也很简单，由于之前已经知道了：某个区间是可以表示成若干个整个有序段和“某个有序段的大于等于某个数的集合或小于等于某个数的集合”。所以我们直接把右边这个区间分成：某个有序段的大于等于某个数的集合、若干个连续的整个的有序段、某个有序段的小于等于某个数的集合。然后在这三个部分上查询跟 $\max$ 最接近的比 $\max$ 小的数更新答案即可。

时间复杂度 $O(n\log ^2n)$。