用命名保存点回退的账本

import sys  def main():    lines = sys.stdin.read().split("\n")    s, m = map(int, lines[0].split())    val = [0] * (s + 1)     log = []  # 되돌리기 기록 스택: (칸, 바꾸기 전 값)    names = []  # 저장점 스택: 이름    marks = []  # 저장점 스택: 저장할 때의 기록 길이    below = []  # 저장점 스택: 같은 이름의 바로 아래 저장점 자리(없으면 -1)    top = {}  # 이름 → 그 이름의 살아 있는 저장점 가운데 가장 위의 자리     def cut(size):        """저장점 스택을 size개만 남기고 위에서부터 없앤다."""        while len(names) > size:            top[names.pop()] = below.pop()            marks.pop()     out = []    for line in lines[1 : 1 + m]:        t = line.split()        cmd = t[0]        if cmd == "set" or cmd == "add":            k, x = int(t[1]), int(t[2])            log.append((k, val[k]))            val[k] = x if cmd == "set" else val[k] + x        elif cmd == "get":            out.append(val[int(t[1])])        elif cmd == "save":            below.append(top.get(t[1], -1))            top[t[1]] = len(names)            names.append(t[1])            marks.append(len(log))        else:            p = top.get(t[1], -1)            if p == -1:                out.append(-1)            elif cmd == "back":                # 기록을 위에서부터(나중 것부터) 꺼내며 옛 값을 되살린다                while len(log) > marks[p]:                    k, old = log.pop()                    val[k] = old                cut(p + 1)  # 그 저장점은 남는다                out.append(p + 1)            else:  # drop                cut(p)  # 그 저장점까지 없앤다(값은 그대로)                out.append(p)    print("\n".join(map(str, out)))  main()

const lines = require("fs").readFileSync(0, "utf8").split("\n");const [s, m] = lines[0].trim().split(/\s+/).map(Number);const val = new Array(s + 1).fill(0); const logSlot = []; // 되돌리기 기록 스택: 칸const logOld = []; //  되돌리기 기록 스택: 바꾸기 전 값const names = []; // 저장점 스택: 이름const marks = []; // 저장점 스택: 저장할 때의 기록 길이const below = []; // 저장점 스택: 같은 이름의 바로 아래 저장점 자리(없으면 -1)const top = new Map(); // 이름 → 그 이름의 살아 있는 저장점 가운데 가장 위의 자리 // 저장점 스택을 size개만 남기고 위에서부터 없앤다function cut(size) {  while (names.length > size) {    top.set(names.pop(), below.pop());    marks.pop();  }} const out = [];for (let i = 1; i <= m; i++) {  const t = lines[i].trim().split(/\s+/);  const cmd = t[0];  if (cmd === "set" || cmd === "add") {    const k = Number(t[1]);    const x = Number(t[2]);    logSlot.push(k);    logOld.push(val[k]);    val[k] = cmd === "set" ? x : val[k] + x;  } else if (cmd === "get") {    out.push(val[Number(t[1])]);  } else if (cmd === "save") {    below.push(top.has(t[1]) ? top.get(t[1]) : -1);    top.set(t[1], names.length);    names.push(t[1]);    marks.push(logSlot.length);  } else {    const p = top.has(t[1]) ? top.get(t[1]) : -1;    if (p === -1) {      out.push(-1);    } else if (cmd === "back") {      // 기록을 위에서부터(나중 것부터) 꺼내며 옛 값을 되살린다      while (logSlot.length > marks[p]) val[logSlot.pop()] = logOld.pop();      cut(p + 1); // 그 저장점은 남는다      out.push(p + 1);    } else {      cut(p); // drop: 그 저장점까지 없앤다(값은 그대로)      out.push(p);    }  }}console.log(out.join("\n"));

import { readFileSync } from "node:fs"; const lines: string[] = readFileSync(0, "utf8").split("\n");const [s, m] = lines[0].trim().split(/\s+/).map(Number);const val: number[] = new Array<number>(s + 1).fill(0); const logSlot: number[] = []; // 되돌리기 기록 스택: 칸const logOld: number[] = []; //  되돌리기 기록 스택: 바꾸기 전 값const names: string[] = []; // 저장점 스택: 이름const marks: number[] = []; // 저장점 스택: 저장할 때의 기록 길이const below: number[] = []; // 저장점 스택: 같은 이름의 바로 아래 저장점 자리(없으면 -1)const top = new Map<string, number>(); // 이름 → 그 이름의 살아 있는 저장점 가운데 가장 위의 자리 // 저장점 스택을 size개만 남기고 위에서부터 없앤다function cut(size: number): void {  while (names.length > size) {    // pop()의 타입은 `T | undefined`다. 길이를 확인했으니 !로 undefined가 아님을 알린다    top.set(names.pop()!, below.pop()!);    marks.pop();  }} const out: number[] = [];for (let i = 1; i <= m; i++) {  const t = lines[i].trim().split(/\s+/);  const cmd = t[0];  if (cmd === "set" || cmd === "add") {    const k = Number(t[1]);    const x = Number(t[2]);    logSlot.push(k);    logOld.push(val[k]);    val[k] = cmd === "set" ? x : val[k] + x;  } else if (cmd === "get") {    out.push(val[Number(t[1])]);  } else if (cmd === "save") {    below.push(top.get(t[1]) ?? -1);    top.set(t[1], names.length);    names.push(t[1]);    marks.push(logSlot.length);  } else {    const p = top.get(t[1]) ?? -1;    if (p === -1) {      out.push(-1);    } else if (cmd === "back") {      // 기록을 위에서부터(나중 것부터) 꺼내며 옛 값을 되살린다      while (logSlot.length > marks[p]) val[logSlot.pop()!] = logOld.pop()!;      cut(p + 1); // 그 저장점은 남는다      out.push(p + 1);    } else {      cut(p); // drop: 그 저장점까지 없앤다(값은 그대로)      out.push(p);    }  }}console.log(out.join("\n"));

import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.HashMap;import java.util.StringTokenizer; public class Main {    static String[] names; // 저장점 스택: 이름    static int[] marks;    // 저장점 스택: 저장할 때의 기록 길이    static int[] below;    // 저장점 스택: 같은 이름의 바로 아래 저장점 자리(없으면 -1)    static int count = 0;  // 살아 있는 저장점 수    static HashMap<String, Integer> top = new HashMap<>(); // 이름 → 가장 위의 자리     // 저장점 스택을 size개만 남기고 위에서부터 없앤다    static void cut(int size) {        while (count > size) {            count--;            top.put(names[count], below[count]);        }    }     public static void main(String[] args) throws IOException {        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));        StringTokenizer st = new StringTokenizer(br.readLine());        int s = Integer.parseInt(st.nextToken());        int m = Integer.parseInt(st.nextToken());         long[] val = new long[s + 1]; // add가 쌓이면 int를 넘는다        int[] logSlot = new int[m];   // 되돌리기 기록 스택: 칸        long[] logOld = new long[m];  // 되돌리기 기록 스택: 바꾸기 전 값        int logSize = 0;        names = new String[m];        marks = new int[m];        below = new int[m];         StringBuilder sb = new StringBuilder();        for (int i = 0; i < m; i++) {            st = new StringTokenizer(br.readLine());            String cmd = st.nextToken();            if (cmd.equals("set") || cmd.equals("add")) {                int k = Integer.parseInt(st.nextToken());                long x = Long.parseLong(st.nextToken());                logSlot[logSize] = k;                logOld[logSize] = val[k];                logSize++;                val[k] = cmd.equals("set") ? x : val[k] + x;            } else if (cmd.equals("get")) {                sb.append(val[Integer.parseInt(st.nextToken())]).append('\n');            } else if (cmd.equals("save")) {                String name = st.nextToken();                below[count] = top.getOrDefault(name, -1);                top.put(name, count);                names[count] = name;                marks[count] = logSize;                count++;            } else {                int p = top.getOrDefault(st.nextToken(), -1);                if (p == -1) {                    sb.append(-1).append('\n');                } else if (cmd.equals("back")) {                    // 기록을 위에서부터(나중 것부터) 꺼내며 옛 값을 되살린다                    while (logSize > marks[p]) {                        logSize--;                        val[logSlot[logSize]] = logOld[logSize];                    }                    cut(p + 1); // 그 저장점은 남는다                    sb.append(p + 1).append('\n');                } else {                    cut(p); // drop: 그 저장점까지 없앤다(값은 그대로)                    sb.append(p).append('\n');                }            }        }        System.out.print(sb);    }}

using System;using System.Collections.Generic;using System.Text; class Program{    static void Main()    {        string[] first = Console.ReadLine().Split(' ', StringSplitOptions.RemoveEmptyEntries);        int s = int.Parse(first[0]);        int m = int.Parse(first[1]);         long[] val = new long[s + 1]; // add가 쌓이면 int를 넘는다        var log = new Stack<(int Slot, long Old)>(); // 되돌리기 기록: (칸, 바꾸기 전 값)        var names = new List<string>(); // 저장점 스택: 이름        var marks = new List<int>();    // 저장점 스택: 저장할 때의 기록 길이        var below = new List<int>();    // 저장점 스택: 같은 이름의 바로 아래 저장점 자리(없으면 -1)        var top = new Dictionary<string, int>(); // 이름 → 가장 위의 자리         // 저장점 스택을 size개만 남기고 위에서부터 없앤다        void Cut(int size)        {            while (names.Count > size)            {                int last = names.Count - 1;                top[names[last]] = below[last];                names.RemoveAt(last);                marks.RemoveAt(last);                below.RemoveAt(last);            }        }         var sb = new StringBuilder();        for (int i = 0; i < m; i++)        {            string[] t = Console.ReadLine().Split(' ', StringSplitOptions.RemoveEmptyEntries);            string cmd = t[0];            if (cmd == "set" || cmd == "add")            {                int k = int.Parse(t[1]);                long x = long.Parse(t[2]);                log.Push((k, val[k]));                val[k] = cmd == "set" ? x : val[k] + x;            }            else if (cmd == "get")            {                sb.Append(val[int.Parse(t[1])]).Append('\n');            }            else if (cmd == "save")            {                below.Add(top.TryGetValue(t[1], out int under) ? under : -1);                top[t[1]] = names.Count;                names.Add(t[1]);                marks.Add(log.Count);            }            else            {                int p = top.TryGetValue(t[1], out int found) ? found : -1;                if (p == -1)                {                    sb.Append(-1).Append('\n');                }                else if (cmd == "back")                {                    // 기록을 위에서부터(나중 것부터) 꺼내며 옛 값을 되살린다                    while (log.Count > marks[p])                    {                        var (k, old) = log.Pop();                        val[k] = old;                    }                    Cut(p + 1); // 그 저장점은 남는다                    sb.Append(p + 1).Append('\n');                }                else                {                    Cut(p); // drop: 그 저장점까지 없앤다(값은 그대로)                    sb.Append(p).Append('\n');                }            }        }        Console.Write(sb);    }}

#include <iostream>#include <string>#include <unordered_map>#include <utility>#include <vector>using namespace std; vector<string> names;            // 저장점 스택: 이름vector<int> marks;               // 저장점 스택: 저장할 때의 기록 길이vector<int> below;               // 저장점 스택: 같은 이름의 바로 아래 저장점 자리(없으면 -1)unordered_map<string, int> top;  // 이름 → 그 이름의 살아 있는 저장점 가운데 가장 위의 자리 // 저장점 스택을 size개만 남기고 위에서부터 없앤다void cut(size_t size) {    while (names.size() > size) {        top[names.back()] = below.back();        names.pop_back();        marks.pop_back();        below.pop_back();    }} int main() {    ios::sync_with_stdio(false);    cin.tie(nullptr);     int s, m;    cin >> s >> m;    vector<long long> val(s + 1, 0);     // add가 쌓이면 int를 넘는다    vector<pair<int, long long>> log;    // 되돌리기 기록 스택: (칸, 바꾸기 전 값)     for (int i = 0; i < m; i++) {        string cmd;        cin >> cmd;        if (cmd == "set" || cmd == "add") {            int k;            long long x;            cin >> k >> x;            log.push_back({k, val[k]});            val[k] = cmd == "set" ? x : val[k] + x;        } else if (cmd == "get") {            int k;            cin >> k;            cout << val[k] << '\n';        } else {            string name;            cin >> name;            auto it = top.find(name);            int p = it == top.end() ? -1 : it->second;            if (cmd == "save") {                below.push_back(p);                top[name] = (int)names.size();                names.push_back(name);                marks.push_back((int)log.size());            } else if (p == -1) {                cout << -1 << '\n';            } else if (cmd == "back") {                // 기록을 위에서부터(나중 것부터) 꺼내며 옛 값을 되살린다                while ((int)log.size() > marks[p]) {                    val[log.back().first] = log.back().second;                    log.pop_back();                }                cut(p + 1); // 그 저장점은 남는다                cout << p + 1 << '\n';            } else {                cut(p); // drop: 그 저장점까지 없앤다(값은 그대로)                cout << p << '\n';            }        }    }    return 0;}

#include <stdio.h>#include <stdlib.h>#include <string.h> #define TABLE 32768 // 이름은 많아야 10,000가지라 넉넉하다(2의 거듭제곱) // 이름 → 그 이름의 살아 있는 저장점 가운데 가장 위의 자리(해시 표, 빈칸은 이름이 "")static char keys[TABLE][9];static int tops[TABLE]; // 이름이 들어 있는(또는 들어갈) 칸을 찾는다static int find(const char *name) {    unsigned h = 2166136261u;    for (const char *p = name; *p; p++) h = (h ^ (unsigned char)*p) * 16777619u;    int i = (int)(h & (TABLE - 1));    while (keys[i][0] != '\0' && strcmp(keys[i], name) != 0) i = (i + 1) & (TABLE - 1);    return i;} static int *name_cell; // 저장점 스택: 이름이 든 해시 표의 칸static int *marks;     // 저장점 스택: 저장할 때의 기록 길이static int *below;     // 저장점 스택: 같은 이름의 바로 아래 저장점 자리(없으면 -1)static int count = 0;  // 살아 있는 저장점 수 // 저장점 스택을 size개만 남기고 위에서부터 없앤다static void cut(int size) {    while (count > size) {        count--;        tops[name_cell[count]] = below[count];    }} int main(void) {    int s, m;    if (scanf("%d %d", &s, &m) != 2) return 1;     long long *val = calloc(s + 1, sizeof(long long)); // add가 쌓이면 int를 넘는다    int *log_slot = malloc(sizeof(int) * m);            // 되돌리기 기록 스택: 칸    long long *log_old = malloc(sizeof(long long) * m); // 되돌리기 기록 스택: 바꾸기 전 값    int log_size = 0;    name_cell = malloc(sizeof(int) * m);    marks = malloc(sizeof(int) * m);    below = malloc(sizeof(int) * m);     for (int i = 0; i < m; i++) {        char cmd[8];        scanf("%7s", cmd);        if (strcmp(cmd, "set") == 0 || strcmp(cmd, "add") == 0) {            int k;            long long x;            scanf("%d %lld", &k, &x);            log_slot[log_size] = k;            log_old[log_size] = val[k];            log_size++;            val[k] = cmd[0] == 's' ? x : val[k] + x;        } else if (strcmp(cmd, "get") == 0) {            int k;            scanf("%d", &k);            printf("%lld\n", val[k]);        } else {            char name[9];            scanf("%8s", name);            int cell = find(name);            int p = keys[cell][0] == '\0' ? -1 : tops[cell];            if (strcmp(cmd, "save") == 0) {                if (keys[cell][0] == '\0') strcpy(keys[cell], name);                below[count] = p;                tops[cell] = count;                name_cell[count] = cell;                marks[count] = log_size;                count++;            } else if (p == -1) {                printf("-1\n");            } else if (strcmp(cmd, "back") == 0) {                // 기록을 위에서부터(나중 것부터) 꺼내며 옛 값을 되살린다                while (log_size > marks[p]) {                    log_size--;                    val[log_slot[log_size]] = log_old[log_size];                }                cut(p + 1); // 그 저장점은 남는다                printf("%d\n", p + 1);            } else {                cut(p); // drop: 그 저장점까지 없앤다(값은 그대로)                printf("%d\n", p);            }        }    }     free(val); free(log_slot); free(log_old); free(name_cell); free(marks); free(below);    return 0;}

첫줄 = 控制台.读数字();s = 첫줄[0];m = 첫줄[1];val = 新列表(s, 0); // 칸 k는 val[k - 1]에 둔다 logSlot = []; // 되돌리기 기록 스택: 칸logOld = []; // 되돌리기 기록 스택: 바꾸기 전 값names = []; // 저장점 스택: 이름marks = []; // 저장점 스택: 저장할 때의 기록 길이below = []; // 저장점 스택: 같은 이름의 바로 아래 저장점 자리(없으면 -1)top = 字典(); // 이름 → 그 이름의 살아 있는 저장점 가운데 가장 위의 자리 循环 (i = 0; i < m; i++){    t = 控制台.读行().去空白().分割();    cmd = t[0];    如果 (cmd == "set" || cmd == "add")    {        k = t[1].转数字() - 1;        x = t[2].转数字();        logSlot.添加(k);        logOld.添加(val[k]);        如果 (cmd == "set")        {            val[k] = x;        }        否则        {            val[k] = val[k] + x;        }    }    否则 如果 (cmd == "get")    {        控制台.输出(val[t[1].转数字() - 1]);    }    否则    {        p = -1;        如果 (top.包含(t[1]))        {            p = top[t[1]];        }        如果 (cmd == "save")        {            below.添加(p);            top[t[1]] = names.数量;            names.添加(t[1]);            marks.添加(logSlot.数量);        }        否则 如果 (p == -1)        {            控制台.输出(-1);        }        否则 如果 (cmd == "back")        {            // 기록을 위에서부터(나중 것부터) 꺼내며 옛 값을 되살린다            当 (logSlot.数量 > marks[p])            {                끝 = logSlot.数量 - 1;                val[logSlot[끝]] = logOld[끝];                logSlot.按位置移除(끝);                logOld.按位置移除(끝);            }            자르기(p + 1); // 그 저장점은 남는다            控制台.输出(p + 1);        }        否则        {            자르기(p); // drop: 그 저장점까지 없앤다(값은 그대로)            控制台.输出(p);        }    }} // 저장점 스택을 size개만 남기고 위에서부터 없앤다자르기(size){    当 (names.数量 > size)    {        끝 = names.数量 - 1;        top[names[끝]] = below[끝];        names.按位置移除(끝);        marks.按位置移除(끝);        below.按位置移除(끝);    }}