第3个点被卡了。。。
查看原帖
第3个点被卡了。。。
687621
wwjjrr楼主2024/7/20 21:29

谁能帮帮忙?第3个点死活卡不过去。。。

#include<bits/stdc++.h>

using namespace std;

const int N=500005;

int n,a[N],m,pp[N],cxt,l,r,ans=0,o,f[710][710],e[N][710],x,y,p,q;
map<int,int> s;

int main(){
	ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
	cin>>n>>m;
	for(int i=1;i<=n;i++) cin>>a[i],pp[i]=a[i];
	sort(pp+1,pp+n+1);
	for(int i=1;i<=n;i++) if(pp[i]!=pp[i-1]) ++cxt,s[pp[i]]=cxt;
	for(int i=1;i<=n;i++) a[i]=s[a[i]];
	o=708;
	for(int i=1;i*o<=n;++i){
		for(int j=1;j<=cxt;++j) pp[j]=0;
		for(int j=i;o*j<=n;++j){
			int l=(j-1)*o+1,r=j*o;
			for(int k=l;k<=r;++k) ++pp[a[k]];
			f[i][j]=f[i][j-1];
			for(int k=l;k<=r;++k) f[i][j]=max(f[i][j],pp[a[k]]);
		}
	}
	for(int i=1;i<=cxt;++i) pp[i]=0;
	for(int i=1;i*o<=n;++i){
		for(int j=(i-1)*o+1;j<=i*o;++j) ++pp[a[j]];
		for(int j=1;j<=cxt;++j) e[j][i]=pp[j];
	}
//	while(cin>>n>>m) cout<<f[n][m]<<"\n";
	while(m--){
		cin>>l>>r;
		l^=ans;
		r^=ans;
		if(l>r) swap(l,r);
		x=(l-1)/o+2,y=r/o;
		if(l%o==1) x=l/o+1;
//		cout<<x<<" "<<y<<"\n";
		if(x<=y){
//			cout<<o<<" "<<x<<" "<<y<<"  "<<f[x][y]<<"    ";
			p=x,q=y;
			ans=f[x][y];
			x--,x*=o;
			y*=o,y++;
			for(int i=l;i<=x;++i) pp[a[i]]=0;
			for(int i=y;i<=r;++i) pp[a[i]]=0;
			for(int i=l;i<=x;++i) ++pp[a[i]];
			for(int i=y;i<=r;++i) ++pp[a[i]];
			for(int i=l;i<=x;++i) ans=max(ans,pp[a[i]]+e[a[i]][q]-e[a[i]][p-1]);
			for(int i=y;i<=r;++i) ans=max(ans,pp[a[i]]+e[a[i]][q]-e[a[i]][p-1]);
		}
		else {
			ans=0;
			for(int i=l;i<=r;++i) pp[a[i]]=0;
			for(int i=l;i<=r;++i) ++pp[a[i]];
			for(int i=l;i<=r;++i) ans=max(ans,pp[a[i]]);
		}
		cout<<ans<<"\n";
	}
}
2024/7/20 21:29
加载中...