模拟 + 双向链表 + map

根据提议模拟一个双向链表，用map映射下节点的地址就好啦。

有点卡时间，cin取消同步还是一直T，改成scanf才过。

#include 
    
     #define INF 0x3f3f3f3f#define full(a, b) memset(a, b, sizeof a)#define FAST_IO ios::sync_with_stdio(false)using namespace std;typedef long long LL;inline int lowbit(int x){ return x & (-x); }inline int read(){    int ret = 0, w = 0; char ch = 0;    while(!isdigit(ch)){        w |= ch == '-', ch = getchar();    }    while(isdigit(ch)){        ret = (ret << 3) + (ret << 1) + (ch ^ 48);        ch = getchar();    }    return w ? -ret : ret;}inline int lcm(int a, int b){ return a / __gcd(a, b) * b; }template 
     
      inline A fpow(A x, B p, C lyd){    A ans = 1;    for(; p; p >>= 1, x = 1LL * x * x % lyd)if(p & 1)ans = 1LL * x * ans % lyd;    return ans;}int _, q, m, opt, v, size;char str[20];struct Node{    LL index;    int val;    Node *prev, *next;    Node(){}    Node(LL index, int val, Node *prev, Node *next): index(index), val(val), prev(prev), next(next){}}*head, *tail;unordered_map
      
        um;inline void initialize(){    um.clear();    size = 0;    head = new Node();    tail = new Node();    head->next = tail;    tail->prev = head;}inline void insert(Node *p, int val, LL index){    auto *cur = new Node(index, val, p->prev, p);    um[index] = cur;    p->prev = cur;    cur->prev->next = cur;}inline void remove(Node *p){    p->prev->next = p->next;    p->next->prev = p->prev;    um.erase(p->index);    delete p;}inline void calc(Node *p){   p->prev->next = p->next;   p->next->prev = p->prev;   p->prev = tail->prev, p->next = tail;   p->prev->next = p, tail->prev = p;}int main(){    //FAST_IO, cin.tie(0);    for(scanf("%d", &_); _; _ --){        scanf("%d%d", &q, &m);        initialize();        while(q --){            scanf("%d%s%d", &opt, str, &v);            int t = strlen(str);            LL index = atoll(str) + 100000000000LL * t;            if(opt == 0){                if(um.find(index) == um.end()){                    insert(tail, v, index);                    size ++;                    if(size > m) remove(head->next), size --;                    printf("%d\n", v);                }                else{                    auto *addr = um[index];                    printf("%d\n", addr->val);                    calc(addr);                }            }            else{                if(um.find(index) == um.end()){                    printf("Invalid\n");                }                else{                    auto *addr = um[index];                    if(v == -1 && addr->prev != head){                        printf("%d\n", addr->prev->val);                    }                    else if(v == 0){                        printf("%d\n", addr->val);                    }                    else if(v == 1 && addr->next != tail){                        printf("%d\n", addr->next->val);                    }                    else printf("Invalid\n");                }            }        }    }    return 0;}