自动搬运

查看原文

来自洛谷，原作者为

	Reunite Wish us good luck.

搬运于2025-08-24 23:09:57，当前版本为作者最后更新于2025-02-15 18:38:46，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

这是两个时间复杂度 $O(n\sqrt n)$，空间复杂度 $O(n)$ 的做法，下文设 $n,m,q$ 同阶。

不考虑阈值分治，而是直接考虑对区间序列分块，设块长为 $B$。

先考虑整块，设 $f_{i,j}$ 为第 $i$ 个块 $j$ 的最大出现次数。显然有包含关系的区间，小的区间一定没有贡献，直接删去，现在该块内所有区间 $l_i,r_i$ 同时单调上升，我们维护 $t_i,h_i$ 分别为当前区间每个数出现次数，以及每个数的最大出现次数，用两个指针 $L,R$ 表示当前取到的区间，显然因为端点同时单调，顺次取到每个区间的复杂度为 $O(n)$，现在考虑如何更新答案。

注意到，我们从 $[l_i,r_i]$ 移动到 $[l_i+x,r_i+y]$ 的过程中，如果我们先移动左指针，再移动右指针，同时动态更新 $t,h$，那一定是对的，因为是取 $\max$，容易发现我们在移动过程中任意时刻任意数的出现次数，一定不大于其应在相邻两个区间中的出现次数，也就是正确的。注意过程中可以出现 $L>R$ 的情况，但无所谓。

现在考虑散块，就转化为 $O(nB)$ 次询问区间某个数出现次数，直接 $\text{vector}$ 上二分复杂度 $O(nB\log)$，很不牛。于是分出了两种做法：

• 注意到本质不同的区间只有 $O(n)$ 个，因此可以对这些区间做莫队，处理完一整个区间之后，遍历其对应的块中的所有询问并更新答案，因为一个询问最多拆到两个散块上，复杂度为 $O(nB+m\sqrt n)$。

• 还有一种做法是，把询问的 $[l,r,k]$ 挂在 $k$ 上，顺次做所有的 $k$，我们设 $b_i=[a_i=k]$，那询问就是区间和，使用 $O(\sqrt n)-O(1)$ 再次分块平衡即可 $O(1)$ 查询。

这两种做法总复杂度显然都可以做到 $O(n\sqrt n)$，现在考虑空间复杂度，我们不维护 $f_{i,j}$，而是离线逐块处理，这样整块空间复杂度线性。对于散块，做法一空间直接就是线性的；做法二注意到一次询问会被拆到散块中的两个连续区间，只记录端点即可做到空间线性。

这样总复杂度就是时间 $O(n\sqrt n)$，空间 $O(n)$ 了。口胡没写。

写了，莫队最后遍历常数太大，用第二种方法过的，给一个卡常前的代码。

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#define B 600
#define BB 500
using namespace std;

int n,m,q,cnt;
int a[200005];
int p[200005];
int t[200005];
int h[200005];
int g[200005];
int bl[200005];
int lf[200005];
int rt[200005];
int ll[200005];
int rr[200005];
bool mp[200005];
int ans[200005];
vector <int> F[200005];
vector <int> G[200005];
struct node{int l,r,x;}qq[200005];

inline void in(int &n){
	n=0;
	char c=getchar();
	while(c<'0' || c>'9') c=getchar();
	while(c>='0'&&c<='9') n=n*10+c-'0',c=getchar();
	return ;
}

int llf[200005];
int rrt[200005];
int bll[200005];

inline void add(int x,int y){
	for(int i=bll[x];i<=bll[n];i++) t[i]+=y;
	for(int i=x;i<=rrt[bll[x]];i++) h[i]+=y;
	return ;
}

inline int ask(int x){return t[bll[x]-1]+h[x];}

int main(){
	in(n),in(m),in(q);
	for(int i=1;i<=n;i++) in(a[i]),F[a[i]].emplace_back(i);

	for(int i=1;i<=m;i++) bl[i]=(i+B-1)/B;
	for(int i=1;i<=m;i++) rt[bl[i]]=i;
	for(int i=m;i>=1;i--) lf[bl[i]]=i;

	for(int i=1;i<=n;i++) bll[i]=(i+BB-1)/BB;
	for(int i=1;i<=n;i++) rrt[bll[i]]=i;
	for(int i=n;i>=1;i--) llf[bll[i]]=i;

	for(int i=1;i<=m;i++) in(ll[i]),in(rr[i]),p[i]=i;
	for(int i=1;i<=q;i++) in(qq[i].l),in(qq[i].r),in(qq[i].x);
	for(int i=1;i<=bl[m];i++){
		for(int j=lf[i];j<=rt[i];j++) h[j]=j;
		sort(h+lf[i],h+rt[i]+1,[](int x,int y){return ll[x]==ll[y]?rr[x]>rr[y]:ll[x]<ll[y];});
		int R=0,mm=0;
		for(int j=lf[i];j<=rt[i];j++){
			if(R>=rr[h[j]]) continue;
			g[++mm]=h[j];
			R=max(R,rr[h[j]]);
		}
		for(int j=1;j<=n;j++) t[j]=h[j]=0;
		int L=1;R=0;
		for(int j=1;j<=mm;j++){
			while(L<ll[g[j]]) t[a[L++]]--;
			while(R<rr[g[j]]) t[a[++R]]++,h[a[R]]=max(h[a[R]],t[a[R]]);
		}
		for(int j=1;j<=q;j++) if(qq[j].l<=lf[i]&&qq[j].r>=rt[i]) ans[j]=max(ans[j],h[qq[j].x]);
	}
	for(int i=1;i<=q;i++) G[qq[i].x].emplace_back(i);
	memset(t,0,sizeof(t));
	memset(h,0,sizeof(h));
	for(int i=1;i<=n;i++){
		for(int v:F[i]) add(v,1);
		for(int v:G[i]){
			int x=0,l,r;
			if(bl[qq[v].l]+1>=bl[qq[v].r]){
				l=qq[v].l,r=qq[v].r;
				for(int j=l;j<=r;j++) x=max(x,ask(rr[j])-ask(ll[j]-1));
				ans[v]=max(ans[v],x);
				continue;
			}
			l=qq[v].l,r=rt[bl[l]];
			for(int j=l;j<=r;j++) x=max(x,ask(rr[j])-ask(ll[j]-1));
			r=qq[v].r,l=lf[bl[r]];
			for(int j=l;j<=r;j++) x=max(x,ask(rr[j])-ask(ll[j]-1));
			ans[v]=max(ans[v],x);
		}
		for(int v:F[i]) add(v,-1);
	}
	for(int i=1;i<=q;i++) printf("%d\n",ans[i]);

	return 0;
}