AtCoder Beginner Contest 250E Prefix Equality

#include <bits/stdc++.h>

using namespace std;

template <typename T> inline T read(){
T sum = 0;
int fl = 1,ch = getchar();
for(; !isdigit(ch); ch = getchar()) if(ch == '-') fl = -1;
for(; isdigit(ch); ch = getchar()) sum = (sum << 3) + (sum << 1) + ch - '0';
return sum * fl;
}

constexpr int maxn = 2e5 + 5;

int n,q;
int b[maxn];
map <int,unsigned long long> vis;
map <long long,map<int,bool> > chk;
map <int,long long> findB;

int main(){
mt19937_64 gen (19260817);
set<int> a,b;
long long hashA = 0,hashB = 0;
for(int i = 1; i <= n; i++){
bool flag = a.insert(x).second;
if(flag){
unsigned long long rnd;
if(vis[x]){
rnd = vis[x];
}else{
rnd = gen();
vis[x] = rnd;
}
hashA ^= rnd;
}
chk[hashA][i] = true;
}
for(int i = 1; i <= n; i++){
bool flag = b.insert(x).second;
if(flag){
unsigned long long rnd;
if(vis[x]){
rnd = vis[x];
}else{
rnd = gen();
vis[x] = rnd;
}
hashB ^= rnd;
}
findB[i] = hashB;
}
while(q--){
int x,y;
if(chk[findB[y]][x]){
puts("Yes");
}else puts("No");
}
return 0;
}


## 发送评论编辑评论

|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
（╯‵□′）╯︵┴─┴
￣﹃￣
(/ω＼)
∠( ᐛ 」∠)＿
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ｀)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ(￣∇￣o)
ヾ(´･ ･｀｡)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò｡)
Σ(っ °Д °;)っ
( ,,´･ω･)ﾉ"(´っω･｀｡)
╮(╯▽╰)╭
o(*////▽////*)q
＞﹏＜
( ๑´•ω•) "(ㆆᴗㆆ)

Emoji