I 前缀和,二分,高性能优化 B站讲解https://www.bilibili.com/video/BV1GT4y1M78d?p=4
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
typedef vector<int> vii;
typedef vector<ll> vll;
typedef pair<int,int> PII;
#define so sizeof
#define pb push_back
#define pf push_front
#define ppb pop_back
#define ppf pop_front
#define fi first
#define se second
#define mp make_pair
#define lb lower_bound
#define ub upper_bound
const db esp=1e-5;
const int N=2e5+10,M=1e7+10,Max=2e5,inf=0x3f3f3f3f,mod=998244353;
const ll INF=0x3f3f3f3f3f3f3f3f;
int n,m,a[N],ps[N],v,cnt;
struct VL{
int v,len;
VL(int v=0,int len=0):v(v),len(len){};
};
bool operator<(VL a,VL b){
if(a.v!=b.v)
return a.v<b.v;
else return a.len<b.len;
}
VL vlen[M];
unordered_map<int,int> vis;
bool cmp0(VL a,VL b){
return a.v<b.v;
}
void work(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
for(int i=1;i<=n;i++) ps[i]=ps[i-1]^a[i];
for(int l=1;l<=n;l++){//l
for(int r=l;r<=n;r++){//r
int v=ps[r]^ps[l-1], len=r-l+1;
if(vis[v]==0) vis[v]=cnt, vlen[cnt]=VL(v, len), cnt++;
else if(vlen[vis[v]].len > len) vlen[vis[v]].len=len;
}
}
sort(vlen, vlen + cnt,cmp0);
for(int i=cnt-2;i>=0;i--)
if(vlen[i].len > vlen[i + 1].len)
vlen[i].len=vlen[i + 1].len;
while(m--){
scanf("%d",&v);
int pos= lb(vlen, vlen + cnt, VL(v, -inf)) - vlen;
if(pos>=cnt) puts("-1");
else printf("%d\n", vlen[pos].len);
}
return ;
}
int main(){
work();
return 0;
}


京公网安备 11010502036488号