洛谷 P5048 - [Ynoi2019 模拟赛] Yuno loves sqrt technology III（分块）

qwq 感觉跟很多年前做过的一道题思路差不多罢，结果我竟然没想起那道题？！！所以说我 wtcl/wq

首先将 \(a_i\) 离散化。

如果允许离线那显然一遍莫队就能解决，复杂度 \(n\sqrt{n}\)。

那如果强制在线怎么办呢？

既然离线都只能做到 \(n\sqrt{n}\)，那在线肯定至少 \(n\sqrt{n}\) 咯

考虑将原序列分块，我们预处理处 \(mx_{i,j}\) 表示第 \(i\) 块开头到第 \(j\) 块结尾的区间中出现次数最多的值的出现次数。这个显然可以 \(n\sqrt{n}\) 求出，具体来说枚举开头的块 \(i\) 并实时维护一个桶 \(cnt_i\)，然后一遍向后扫描一遍更新答案即可。

接下来考虑怎样求出答案：

如果 \(l,r\) 在同一块中那直接暴力统计答案即可，复杂度 \(\sqrt{n}\)。
如果 \(l,r\) 不在同一块中，我们掏出求得的 \(mx\) 数组，先令 \(ans=mx_{bel_l+1,bel_r-1}\)，也就是 \([l,r]\) 中间整块的答案。然后考虑边角元素对答案的影响。我们对每个值 \(v\) 开一个 std::vector<int> \(pos\) 维护其出现的位置，记 \(p_i\) 为 \(i\) 在 \(pos_{a_i}\) 中的位置。对于左边的边角元素 \(i\in[l,R[bel[r]]]\)，如果 \(i\) 能使答案变得更优，那么 \(a_i\) 在 \([l,r]\) 中出现的次数应当大于 \(ans\)，换句话说，\(pos[a[i]][p[i]+ans]\leq r\)，那我们可以暴力往右移，每次答案加一，直到 \(pos[a[i]][p[i]+ans]>r\)。对于右边的边角元素也同理，不难发现边角元素最多 \(2\sqrt{n}\) 个，故 \(ans\) 最多自增 \(2\sqrt{n}\) 次，故查询复杂度 \(\sqrt{n}\)。

总复杂度 \(n\sqrt{n}\)，只要常数稍微小一点即可通过本题时限。

#include <bits/stdc++.h>

using namespace std;

#define fi first

#define se second

#define fill0(a) memset(a,0,sizeof(a))

#define fill1(a) memset(a,-1,sizeof(a))

#define fillbig(a) memset(a,63,sizeof(a))

#define pb push_back

#define ppb pop_back

#define mp make_pair

template<typename T1,typename T2> void chkmin(T1 &x,T2 y){if(x>y) x=y;}

template<typename T1,typename T2> void chkmax(T1 &x,T2 y){if(x<y) x=y;}

typedef pair<int,int> pii;

typedef long long ll;

namespace fastio{

	#define FILE_SIZE 1<<23

	char rbuf[FILE_SIZE],*p1=rbuf,*p2=rbuf,wbuf[FILE_SIZE],*p3=wbuf;

	inline char getc(){return p1==p2&&(p2=(p1=rbuf)+fread(rbuf,1,FILE_SIZE,stdin),p1==p2)?-1:*p1++;}

	inline void putc(char x){(*p3++=x);}

	template<typename T> void read(T &x){

		x=0;char c=getchar();T neg=0;

		while(!isdigit(c)) neg|=!(c^'-'),c=getchar();

		while(isdigit(c)) x=(x<<3)+(x<<1)+(c^48),c=getchar();

		if(neg) x=(~x)+1;

	}

	template<typename T> void recursive_print(T x){if(!x) return;recursive_print(x/10);putc(x%10^48);}

	template<typename T> void print(T x){if(!x) putc('0');if(x<0) putc('-'),x=~x+1;recursive_print(x);}

	void print_final(){fwrite(wbuf,1,p3-wbuf,stdout);}

}

const int MAXN=5e5;

const int MAX_BLK=710;

int n,qu,a[MAXN+5],key[MAXN+5],uni[MAXN+5],num;

int blk,blk_cnt,L[MAX_BLK+5],R[MAX_BLK+5],bel[MAXN+5];

int mx[MAX_BLK+5][MAX_BLK+5],cnt[MAXN+5];

vector<int> pos[MAXN+5];int p[MAXN+5];

int main(){

	scanf("%d%d",&n,&qu);

	for(int i=1;i<=n;i++) scanf("%d",&a[i]),key[i]=a[i];

	sort(key+1,key+n+1);key[0]=-1;

	for(int i=1;i<=n;i++) if(key[i]!=key[i-1]) uni[++num]=key[i];

	for(int i=1;i<=n;i++) a[i]=lower_bound(uni+1,uni+num+1,a[i])-uni;

	blk=(int)pow(n,0.5);blk_cnt=(n-1)/blk+1;

	for(int i=1;i<=blk_cnt;i++){

		L[i]=(i-1)*blk+1;R[i]=min(i*blk,n);

		for(int j=L[i];j<=R[i];j++) bel[j]=i;

	}

	for(int i=1;i<=blk_cnt;i++){

		memset(cnt,0,sizeof(cnt));int ret=0;

		for(int j=i;j<=blk_cnt;j++){

			for(int k=L[j];k<=R[j];k++){

				cnt[a[k]]++;chkmax(ret,cnt[a[k]]);

			} mx[i][j]=ret;

		}

	}

	for(int i=1;i<=n;i++) pos[a[i]].pb(i),p[i]=pos[a[i]].size()-1;

	int ans=0;memset(cnt,0,sizeof(cnt));

	while(qu--){

		int l,r;scanf("%d%d",&l,&r);l^=ans;r^=ans;ans=0;

		if(bel[l]==bel[r]){

			for(int i=l;i<=r;i++) cnt[a[i]]++;

			for(int i=l;i<=r;i++) chkmax(ans,cnt[a[i]]);

			for(int i=l;i<=r;i++) cnt[a[i]]--;

			printf("%d\n",ans);

		} else {

			ans=mx[bel[l]+1][bel[r]-1];

			for(int i=l;i<=R[bel[l]];i++){

				int cur=p[i];

				while(cur+ans<pos[a[i]].size()&&pos[a[i]][cur+ans]<=r)

					++ans;

			}

			for(int i=L[bel[r]];i<=r;i++){

				int cur=p[i];

				while(cur-ans>=0&&pos[a[i]][cur-ans]>=l)

					++ans;

			}

			printf("%d\n",ans);

		}

	}

	return 0;

}

/*

10 1

1 2 3 3 2 3 3 1 1 2

4 10

*/

巴特西

洛谷 P5048 - [Ynoi2019 模拟赛] Yuno loves sqrt technology III（分块）

最新文章

热门文章