P11750 「TPOI-1D」谢谢您。题解

这是两个时间复杂度

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)

了。~~口胡没写。~~

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

CPP

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

P11750 「TPOI-1D」谢谢您。题解

文章操作

相关推荐

评论

P11750 「TPOI-1D」谢谢您。题解