#include <bits/stdc++.h>
#define rep(i, n) for (long long i = 0; i < n; ++i)
#define coutyes cout << "YES" << nl
#define coutno cout << "NO" << nl
#define IOS \
ios_base::sync_with_stdio(0); \
cin.tie(0); \
cout.tie(0)
#define nl '\n'
using namespace std;
using ll = long long;
void solve()
{
string a, b, s1, s2; cin >> s1 >> s2;
a = s1, b = s2;
ll t, q; cin >> t >> q;
queue<ll> qu;
rep(i,t) qu.push(-1);
while(q--){
ll x; cin >> x;
if(qu.front()==-1) qu.pop();
else{
ll k=qu.front();
a[k]=s1[k], b[k]=s2[k];
qu.pop();
}
if(x==3){
qu.push(-1);
if(a==b)coutyes;
else coutno;
}
else if(x==2){
qu.push(-1);
ll p, q, r, s; cin >> p >> q >> r >> s;
if(p==1 && r==1)
swap(a[q - 1], a[s - 1]), swap(s1[q - 1], s1[s - 1]);
else if(p==1 && r==2)
swap(a[q - 1], b[s - 1]), swap(s1[q - 1], s2[s - 1]);
else if(p==2 && r==1)
swap(b[q - 1], a[s - 1]), swap(s2[q - 1], s1[s - 1]);
else
swap(b[q - 1], b[s - 1]), swap(s2[q - 1], s2[s - 1]);
}
else{
ll y; cin>>y;
qu.push(y - 1); a[y-1]='A'; b[y-1]='A';
}
}
}
signed main()
{
IOS;
int t=1; cin >> t;
while(t--) solve();
}
Auto comment: topic has been updated by SP_22 (previous revision, new revision, compare).
(string)a==(string)bisn't $$$O(1)$$$, it's $$$O(\min(|a|,|b|))$$$So what should be done instead of that?
For example managing the positions $$$x$$$ which $$$S_{1,x} \neq S_{2,x}$$$ and $$$x$$$ isn't locked, with some data structure or smarter way.
But in my AC submission, I also did (s1 == s2) and didn't get TLE. Why so?
Also how to check if two strings are equal in O(1)?
Hacked :)
Bullying :((
Read info about polynomial hashing