第87个点wa了。。。
查看原帖
第87个点wa了。。。
473401
zcxnb楼主2023/10/15 22:50
#include<bits/stdc++.h>
using namespace std;
const int N=3e5+5,inf=1e9+5;
int q,n,ha,hb;
int a[N],b[N],v[N],t[4*N],c[N];
map<int,map<int,int> >s;
void build(int k,int l,int r){
	if(l==r){
		t[k]=a[l];
		return;
	}
	int mid=(l+r)>>1;
	build(2*k,l,mid);
	build(2*k+1,mid+1,r);
	t[k]=min(t[2*k],t[2*k+1]);
	return;
}
void dotchange(int k,int l,int r,int x){
	if(l==r&&l==x){
		t[k]=inf;
		return;
	}
	int mid=(l+r)>>1;
	if(x<=mid)  dotchange(2*k,l,mid,x);
	if(x>mid)  dotchange(2*k+1,mid+1,r,x);
	t[k]=min(t[2*k],t[2*k+1]);
}
int longquery(int k,int l,int r,int x,int y){
	if(x<=l&&r<=y){
		return t[k];
	}
	int res=inf;
	int mid=(l+r)>>1;
	if(x<=mid)  res=min(longquery(2*k,l,mid,x,y),res);
	if(y>mid)  res=min(longquery(2*k+1,mid+1,r,x,y),res);
	return res;
}
bool pan(){
	if(ha!=hb)  return 0;
	for(int i=1;i<=4*n+1;i++)  t[i]=inf;//注意多测
	build(1,1,n);
	for(int i=1;i<=n;i++){
		++v[b[i]];
		int z=longquery(1,1,n,1,max(s[b[i]][v[b[i]]]-1,1));//前缀查询最小值
		if(z<b[i])  return 0;
		dotchange(1,1,n,max(s[b[i]][v[b[i]]],1));//单点修改 inf

	}
	return 1;
}
int main(){
	scanf("%d",&q);
	while(q--){
		ha=0,hb=0;
		scanf("%d",&n);
		for(int i=1;i<=n;i++)  v[i]=0,c[i]=0;
		s.clear();
		for(int i=1;i<=n;i++){
			scanf("%d",&a[i]);
			s[a[i]][++c[a[i]]]=i;//依次记录每个 a[i] 出现的位置
			ha^=a[i];
		}
		for(int i=1;i<=n;i++){
			scanf("%d",&b[i]);
			hb^=b[i];
		}
		if(pan())  printf("YES\n");
		else  printf("NO\n");
	}
}

不知道什么原因。。。

2023/10/15 22:50
加载中...