这题官方只给了数据，没给 std（上交命题组特有的草台班子），因此公开我自己实现的写法。

（老实说，上交出题如果能保持 20 年的质量，我都可以忍受，但是 22 和 24 真的是恶臭至极，可以说是让 CCSP 名声毁于一旦了）

这是我去年写的代码了，大概花了 3 个多小时写完的。虽然相对比较工整，但是要想一点点重新写解释也是需要时间的，以后有时间再补一下吧（咕咕咕）。

需要注意的主要就是几点：

• 将 commit 名称的字符串与 commit 静态数组利用 unordered_map<string, int> 进行数组下标的映射，这样访存节省时间。
• merge 命令可以利用类似 dijkstra 的优先级宽度搜索，以上述映射 id 的大小为优先级做搜索，就不会爆栈了。这里就需要最先把 git 文件系统的有向图结构想清楚，每个 commit 最多有两个父 commit。
• 文件规模最大不超过 1.5 GB，题面给的 2 GB 完全可以把所有的文件都无脑复制存储下来，想什么可持久化都是完全没必要的（这题的操作其实也不支持可持久化数据结构），实际测下来也就 1.3 GB 这样。

算上头文件 250 行，小于场上满分选手的平均行数。

#include <iostream>
#include <string>
#include <sstream>
#include <unordered_map>
#include <map>
#include <set>
#include <queue>
#include <assert.h>
using namespace std;
const int N = 20010;
int stdoutline;
struct file
{
    string name, text;
    bool del;
    inline file(string n = "", string t = "") : name(n), text(t) {}
    inline file& operator=(const file& o) { return name = o.name, text = o.text, (*this); }
    inline void remove() { del = 1, text.clear(); }
    inline void recover() { del = 0; }
    inline void write(size_t off, const string& s)
    {
        if (text.size() < off + s.length())
        {
            size_t ori = text.length();
            text.resize(off + s.length());
            for (size_t i = ori; i < off; ++i) text[i] = '.';
        }
        for (size_t i = 0; i < s.length(); ++i) text[i + off] = s[i];
    }
    inline string read(size_t off, size_t len) const
    {
        string ret = "";
        for (size_t i = off; i < off + len; ++i) ret.push_back((i >= text.size()) ? '.' : text[i]);
        return ret;
    }
};

unordered_map<string, int> commit_id; // <commit-name, index>
int HEAD, cmtcnt, uncommitid;
struct commit
{
    string name;
    map<string, int> fid; // <file-name, index>
    map<string, int> delfid; // <del-file-name, index>
    vector<file> files;
    bool is_merge_commit;
    int faid1, faid2;
    inline bool empty() const { return fid.empty() && delfid.empty(); }
    inline bool exist(const string& filename) const { return fid.count(filename); }
    inline bool exist_del(const string& filename) const { return delfid.count(filename); }
    inline void create_file(const string& filename)
    {
        if (exist_del(filename))
        {
            int x = delfid[filename];
            files[x].recover(), fid[filename] = x, delfid.erase(delfid.find(filename));
        }
        else if (!exist(filename))
            fid[filename] = files.size(), files.push_back(file(filename, ""));
    }
    inline void copy_file(const file& f) { fid[f.name] = files.size(), files.push_back(f); }
    inline void create_delfile(const string& filename)
    {
        if (exist(filename))
        {
            int x = fid[filename];
            files[x].remove(), delfid[filename] = x, fid.erase(fid.find(filename));
        }
        else if (!exist_del(filename))
        {
            delfid[filename] = files.size(), files.push_back(file(filename, ""));
            files.back().remove();
        }
    }
} cmts[N];
// bool true : exist false : del
inline pair<int, bool> find_file(const string& filename)
{
    if (cmts[uncommitid].exist(filename)) return make_pair(uncommitid, 1);
    else if (cmts[uncommitid].exist_del(filename)) return make_pair(uncommitid, 0);
    set<int> q; // set queue
    q.insert(HEAD);
    while (q.size())
    {
        int u = *q.rbegin();
        if (!u) break;
        q.erase(q.find(u));
        if (cmts[u].exist(filename)) return make_pair(u, 1); 
        else if (cmts[u].exist_del(filename)) return make_pair(u, 0); 
        (cmts[u].is_merge_commit) ? (q.insert(cmts[u].faid1), q.insert(cmts[u].faid2)) : (q.insert(cmts[u].faid1));
    }
    return make_pair(0, 0);
}

inline void write_commit(commit& c, const string& filename, size_t off, const string& s)
{
    if (c.exist(filename) || c.exist_del(filename))
    {
        c.create_file(filename);
        int x = c.fid[filename];
        c.files[x].write(off, s);
    }
    else
    {
        pair<int, bool> search = find_file(filename);
        if (search.first && search.second)
        {
            int x = cmts[search.first].fid[filename];
            c.copy_file(cmts[search.first].files[x]);
            x = c.fid[filename];
            c.files[x].write(off, s);
        }
        else
        {
            c.create_file(filename);
            int x = c.fid[filename];
            c.files[x].write(off, s);
        }
    }
}

inline void read_commit(commit& c, const string& filename, size_t off, size_t len)
{
    pair<int, bool> search = find_file(filename);
    if (!search.second)
    {
        for (size_t i = 0; i < len; ++i) cout << '.';
        cout << '\n';
    }
    else
    {
        int x = cmts[search.first].fid[filename];
        cout << cmts[search.first].files[x].read(off, len) << '\n';
    }
}

inline void unlink_commit(commit& c, const string& filename)
{
    pair<int, bool> search = find_file(filename);
    if (!search.first) return;
    if (!search.second) return;
    c.create_delfile(filename);
}
// modify
inline void ls_commit()
{
    set<string> ret, ret_del;
    for (auto& x : cmts[uncommitid].fid) ret.insert(x.first);
    for (auto& x : cmts[uncommitid].delfid) ret_del.insert(x.first);
    set<int> q; // set queue
    q.insert(HEAD);
    while (q.size())
    {
        int u = *q.rbegin();
        if (!u) break;
        q.erase(q.find(u));
        for (auto& x : cmts[u].fid) if (!ret_del.count(x.first)) ret.insert(x.first);
        for (auto& x : cmts[u].delfid) if (!ret.count(x.first)) ret_del.insert(x.first);
        (cmts[u].is_merge_commit) ? (q.insert(cmts[u].faid1), q.insert(cmts[u].faid2)) : (q.insert(cmts[u].faid1));
    }
    if (ret.empty()) cout << "0\n";
    else cout << ret.size() << ' ' << (*ret.begin()) << ' ' << (*ret.rbegin()) << '\n';
}
inline void upload_commit(const string& cmtname)
{
    if (cmts[uncommitid].empty() || commit_id.count(cmtname)) return;
    cmts[uncommitid].name = cmtname, cmts[uncommitid].faid1 = HEAD, commit_id[cmtname] = uncommitid;
    HEAD = uncommitid, ++uncommitid;
}
inline void checkout_commit(const string& cmtname)
{
    if (!cmts[uncommitid].empty()) return;
    if (!commit_id.count(cmtname)) return;
    HEAD = commit_id[cmtname];
}
inline void merge_commit(const string& mergee, const string& cmtname)
{
    if (!cmts[uncommitid].empty()) return;
    if (!commit_id.count(mergee)) return;
    if (commit_id[mergee] == HEAD) return;
    cmts[uncommitid].name = cmtname, commit_id[cmtname] = uncommitid;
    cmts[uncommitid].is_merge_commit = 1, cmts[uncommitid].faid1 = HEAD, cmts[uncommitid].faid2 = commit_id[mergee];
    HEAD = commit_id[cmtname], ++uncommitid;
}
int n;
string input, instr, text;
string filename;
size_t off, len;
string cmtname, mergee;
inline void init() { HEAD = 0, uncommitid = 1; }
inline int get_n()
{
    int ret = 0;
    getline(cin, input);
    while (input.back() == '\r') input.pop_back();
    stringstream ss(input);
    return ss >> ret, ret;
}
inline void handle_instruction()
{
    getline(cin, input);
    while (input.back() == '\r') input.pop_back();
    stringstream ss(input);

    ss >> instr;
    if (instr == "write")
    {
        ss >> filename >> off >> len;
        getline(cin, text);
        while (text.back() == '\r') text.pop_back();
        write_commit(cmts[uncommitid], filename, off, text);
    }
    else if (instr == "read")
    {
        ss >> filename >> off >> len;
        read_commit(cmts[uncommitid], filename, off, len);
    }
    else if (instr == "unlink")
    {
        ss >> filename;
        unlink_commit(cmts[uncommitid], filename);
    }
    else if (instr == "ls")
    {
        ls_commit();
    }
    else if (instr == "commit")
    {
        ss >> cmtname;
        upload_commit(cmtname);
    }
    else if (instr == "checkout")
    {
        ss >> cmtname;
        checkout_commit(cmtname);
    }
    else if (instr == "merge")
    {
        ss >> mergee >> cmtname;
        merge_commit(mergee, cmtname);
    }
}
int main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0), cerr.tie(0);
    init();
    // input
    int n = get_n();
    while (n--) handle_instruction();
}