首先做法很简单：令缓存大小为n，然后直接把操作模拟一遍，后期如果我们限制了缓存大小为x，那就等价于取我们在模拟时长度为x的前缀。
然后我们显然可以把前缀哈希算一算，插到`std::unordered_map`里，然后成功TLE。
然后我们考虑另一个做法：把询问插到字典树里，仍然对操作进行模拟，每模拟一次后，在字典树上把序列走一遍，并标记对应的询问为Yes。
但是有几个地方要注意
- 一个点可能对应多个询问，所以用一个vector来挂询问吧。
- 一组询问在去除后缀0之后可能长度为0，此时询问是被挂在根上的，务必进行处理，否则WA！
#include <assert.h>
#include <algorithm>
#include <cstring>
#include <iostream>
#include <unordered_map>
#include <vector>
using int_t = int;
using std::cin;
using std::cout;
using std::endl;
using map_t = std::unordered_map<int_t, struct Node*>;
const int_t LARGE = 5e3 + 20;
char inputbuf[(int64_t)1e8];
char* head = inputbuf;
void initinput() {
fread(inputbuf, 1, sizeof(inputbuf), stdin);
}
char nextchar() {
assert(head <= inputbuf + sizeof(inputbuf));
return *(head++);
}
template <class T>
void read(T& x) {
x = 0;
char chr = nextchar();
while (chr < '0' || chr > '9')
chr = nextchar();
while (chr >= '0' && chr <= '9') {
x = x * 10 + chr - '0';
chr = nextchar();
}
}
struct Node {
std::vector<bool*> result;
map_t chd;
~Node() {
for (const auto& kvp : chd)
delete kvp.second;
}
};
int_t arr[LARGE + 1];
int_t arr1[LARGE + 10], queue[LARGE + 1];
bool result[LARGE + 1];
int main() {
initinput();
int_t T;
read(T);
while (T--) {
queue[0] = 0;
int_t n, q;
read(n), read(q);
Node* root = new Node;
for (int_t i = 1; i <= n; i++) {
read(arr[i]);
}
for (int_t i = 1; i <= q; i++) {
result[i] = false;
Node* curr = root;
int_t len;
read(len);
#ifdef DEBUG
cout << "insert len " << len << endl;
#endif
for (int_t j = 1; j <= len; j++) {
int_t x;
read(x);
if (x == 0)
continue;
#ifdef DEBUG
cout << "insert " << x << endl;
#endif
auto& ref = curr->chd[x];
if (ref == nullptr)
ref = new Node;
curr = ref;
}
curr->result.push_back(&result[i]);
#ifdef DEBUG
cout << "insert ok, result to " << i << endl;
#endif
}
for (int_t i = 1; i <= n; i++) {
int_t x = arr[i];
arr1[0] = 0;
arr1[++arr1[0]] = x;
for (int_t j = 1; j <= queue[0]; j++) {
if (queue[j] != x)
arr1[++arr1[0]] = queue[j];
}
// arr1[0] = std::min(arr1[0], n);
assert(arr1[0] <= n);
memcpy(queue, arr1, sizeof(arr1[0]) * (n + 1));
Node* curr = root;
#ifdef DEBUG
cout << "mapping seq ";
for (int_t i = 1; i <= queue[0]; i++)
cout << queue[i] << " ";
cout << endl;
#endif
for (int_t i = 1; i <= queue[0]; i++) {
if (!curr->chd.count(queue[i]))
break;
else
curr = curr->chd[queue[i]];
#ifdef DEBUG
cout << "walk with " << queue[i] << endl;
#endif
for (auto ptr : curr->result) {
*ptr = true;
#ifdef DEBUG
cout << "mark result " << (ptr - result) << " to true"
<< endl;
#endif
}
}
}
for (auto x : root->result)
*x = true;
for (int_t i = 1; i <= q; i++) {
if (result[i]) {
puts("Yes");
} else {
puts("No");
}
}
delete root;
}
return 0;
}