神秘哈希做法，看完不笑说明你有玉米症
2025-08-14 21:55:18
发布于：浙江
95阅读
0回复
0点赞
题目：给定一个 个元素的数组 和 次询问，每次会询问一个区间 ，你需要判断 中的元素是否都出现了偶数次。。
代码：
#include <iostream>
#include <cstdio>
#include <random>
#include <ctime>
#define int long long
using namespace std;
int a[200005];
unsigned int mp[1000005];
unsigned int pre[200005];
mt19937_64 rng;
void solve(){
int n, m;
cin >> n >> m;
for(int i = 1; i <= n; i++) cin >> a[i], pre[i] = pre[i - 1] ^ mp[a[i]];
while(m--){
int l, r;
cin >> l >> r;
cout << (pre[r] == pre[l - 1] ? "YES\n" : "NO\n");
}
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
rng.seed(time(0));
for(int i = 1; i <= 1000000; i++){
mp[i] = rng();
}
int t;
cin >> t;
while(t--) solve();
return 0;
}
全部评论 7
磁铁节，师童用了我的代码：
#include<bits/stdc++.h> #define int long long using namespace std; int T,n,Q,a[200005],cnt[1000005],ans[200005],block,i,l,r,cur; struct query { int l,r,id; }q[200005]; bool cmp(query x,query y) { if(x.l/block!=y.l/block)return x.l<y.l; return x.r<y.r; } void add(int x) { cnt[a[x]]++; if(cnt[a[x]]&1)cur++; else cur--; } void del(int x) { cnt[a[x]]--; if(cnt[a[x]]&1)cur++; else cur--; } signed main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin>>T; while(T--) { cin>>n>>Q; block=sqrt(n); for(i=1;i<=n;i++)cin>>a[i]; for(i=1;i<=Q;i++) { cin>>q[i].l>>q[i].r; q[i].id=i; } memset(cnt,0,sizeof(cnt)); sort(q+1,q+Q+1,cmp); l=1; r=0; cur=0; for(i=1;i<=Q;i++) { while(l<q[i].l)del(l++); while(l>q[i].l)add(--l); while(r<q[i].r)add(++r); while(r>q[i].r)del(r--); //cout<<cur<<" "<<q[i].id<<endl; ans[q[i].id]=cur; } for(i=1;i<=Q;i++) { if(ans[i])cout<<"NO"<<endl; else cout<<"YES"<<endl; } } return 0; }他说他没学过莫队%%%%%%%%%
1周前 来自 北京
1
有帮助，赞一个