题意:
给一个长度为\(m\)的队列,现给定以下操作:
\(opt=0\),插入一个串,如果不在队里直接插入栈尾,如果超出\(m\)删队首;在队里就拿出来重新放到队尾,返回\(v\)值。
\(opt=1\),问某串的前/中/后的串的\(v\)值是什么,不存在输出\(Invalid\)。
思路:
把串\(Hash\),然后用双向链表维护这个队列。标程建议用\(Trie\)去\(Hash\),不过也可以用\(unordered\_map\)卡过去。
代码:
/*****
双向链表板子
*****/
struct Node{ //双向链表
int v; //val或者其他属性
int pre; //前面
int nex; //后面
}p[maxn]; //p[i]表示值为i的节点
int head, tail, sz;
void ins(int ID){ //插在末尾
int u = p[tail].pre;
p[tail].pre = ID;
p[u].nex = ID;
p[ID].pre = u;
p[ID].nex = tail;
sz++;
}
void del(int ID){ //删除
int u = p[ID].pre;
int v = p[ID].nex;
p[u].nex = v;
p[v].pre = u;
sz--;
}
void init(){
head = 0; //头
tail = 1; //尾(空)
sz = 0; //链表中的节点数
p[head].nex = tail;
p[tail].pre = head;
}
#include<map>
#include<set>
#include<cmath>
#include<cstdio>
#include<stack>
#include<ctime>
#include<vector>
#include<queue>
#include<cstring>
#include<string>
#include<sstream>
#include<iostream>
#include<algorithm>
#include<unordered_map>
#include<unordered_set>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int maxn = 500000 + 5;
const int INF = 0x3f3f3f3f;
const ull seed = 131;
const ll MOD = 1e9 + 7;
using namespace std;
struct Node{ //双向链表
int v; //val或者其他属性
int pre; //前面
int nex; //后面
}p[maxn]; //p[i]表示值为i的节点
unordered_map<ull, int> id;
unordered_set<int> in;
int head, tail, sz, tot;
void ins(int ID){ //插在末尾
int u = p[tail].pre;
p[tail].pre = ID;
p[u].nex = ID;
p[ID].pre = u;
p[ID].nex = tail;
in.insert(ID);
sz++;
}
void del(int ID){ //删除
int u = p[ID].pre;
int v = p[ID].nex;
p[u].nex = v;
p[v].pre = u;
in.erase(ID);
sz--;
}
void init(){
tot = 2;
head = 0; //头
tail = 1; //尾(空)
sz = 0;
p[head].nex = tail;
p[tail].pre = head;
}
char s[maxn];
int main(){
int T;
scanf("%d", &T);
while(T--){
int Q, m;
scanf("%d%d", &Q, &m);
id.clear();
in.clear();
init();
while(Q--){
int op, v;
char s[20];
scanf("%d%s%d", &op, s, &v);
int len = strlen(s);
ull Ha = 0;
for(int i = 0; i < len; i++)
Ha = Ha * seed + s[i];
if(id.find(Ha) == id.end()) id[Ha] = tot++;
int ID = id[Ha];
if(op == 0){
if(in.find(ID) == in.end()){
ins(ID);
p[ID].v = v;
if(sz > m) del(p[head].nex);
}
else{
del(ID);
ins(ID);
}
printf("%d\n", p[ID].v);
}
else{
if(in.find(ID) == in.end()) printf("Invalid\n");
else{
if(v == 1){
if(p[ID].nex == tail) printf("Invalid\n");
else printf("%d\n", p[p[ID].nex].v);
}
else if(v == -1){
if(p[ID].pre == head) printf("Invalid\n");
else printf("%d\n", p[p[ID].pre].v);
}
else printf("%d\n", p[ID].v);
}
}
}
}
return 0;
}