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