蒟蒻一句心里话，大模拟题真恶心

1 急诊就诊{

1. 题意:有一个门诊，其中包含m个医生和k组操作：

 1 A t id p k: 操作A,表示时刻t时有编号为id的病人约诊，优先级为p,治疗时间为k

2 C t id: 操作C,表示时刻t时有编号为id的病人请求取消预约，同时只有仍在等待的病人才可取消预约

3 Q t:操作Q, 表示当进行完时刻t以前的所有操作后剩余的病人数量，正在治疗的人数和当前第一个等待的病人编号

2 思路：如此繁杂的操作给我的第一感觉就是STL的题目。当然也确实是，只不过复杂亿点点。

首先我们可以先写出对于每种操作我们可能需要执行的部分：

A: 考虑当前病人就诊的优先级，统一按就诊时间>优先级>治疗时间进行治疗

C:考虑当前的病人是否处于治疗状态，如果仍在等待那么将其移出集合

Q:输出答案

而这题我们需要考虑的东西远不止于此。对于快速的按上述顺序对需要治疗的病人进行处理，我们可以直接用两个堆来维护，一个是已经接受治疗的病人堆，一个是仍在等待治疗的病人堆。可如果我们要删除取消预约的病人怎么办呢？

很显然我们不能直接去删除，因为堆不支持快速删除元素。所以我们可以将需要删除的病人进行标记，遇到时直接弹出即可。当一个病人接受完治疗后，我们需要从接受完治疗后的时间开始，而不是从初始时间开始（本人挂分就挂在这里），因此我们只需要在处理病人时记录当前空闲医生个数有几个，每治疗完一个病人treedoc++,直到为0为止

初始化：三元组：id,p,t 病人的治疗时刻，优先级与治疗所需的时长

3.算法： 优先队列，模拟

}

代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2e5+10;
int m,q;
int status[N];
int dur[N];
ll arrive[N];
struct Waiting{
    int id, p;
    ll t;
    bool operator<(const Waiting& other)const{
        if (p!=other.p) return p<other.p;
        if (t!=other.t) return t>other.t;
        return id>other.id;
    }
};
priority_queue<Waiting,vector<Waiting>,less<>> waitQ;
priority_queue<pair<ll, int>,vector<pair<ll, int>>,greater<>> treatQ;
int freeDoc=0,waitCnt=0,treatCnt=0;
void admit(ll now){//接诊
    while (freeDoc>0&&waitCnt>0){ // 弹出无效的等待项（已被取消或状态不对）
        while (!waitQ.empty()&&status[waitQ.top().id]!=1) waitQ.pop();
        if (waitQ.empty()) break;
        auto p=waitQ.top(); waitQ.pop();
        status[p.id]=2;//已就诊
        waitCnt--;
        freeDoc--;
        treatCnt++;
        treatQ.push({now+dur[p.id],p.id});
    }
}
// 处理所有结束时间 <= now 的治疗
void finish(ll now) {//处理已接诊的病人
    while (!treatQ.empty()&&treatQ.top().first<=now) {
        auto [end, id]=treatQ.top(); treatQ.pop();
        status[id]=3;//标记为已取消（懒删除）
        treatCnt--;//弹出
        freeDoc++;// 医生空闲后立即接诊
        admit(end);
    }
}
int main(){
    cin >> m >> q;
    freeDoc=m;
    while (q--){
        char op;
        cin >> op;
        if (op=='A'){
            ll t; int id, p, d;
            cin >> t >> id >> p >> d;
            finish(t);
            status[id]=1;
            waitCnt++;
            arrive[id]=t;
            dur[id]=d;
            waitQ.push({id, p, t});//等待三元组
            admit(t);
        } 
        else if (op=='C'){
            ll t; int id;
            cin >> t >> id;
            finish(t);
            if (status[id]==1) {
                status[id]=4;
                waitCnt--;
            }
        } 
        else if (op=='Q'){
            ll t;
            cin >> t;
            finish(t);
            while (!waitQ.empty()&&status[waitQ.top().id]!=1) waitQ.pop();
            int frontId=waitQ.empty()?0:waitQ.top().id;
            cout<<waitCnt<<' '<<treatCnt<<' '<<frontId<<endl;
        }
    }
}

2 连续窗口{

1. 题意：有一组大小为n的窗口和q次操作，操作分为以下几种：

1 A id k: 表示第id支队伍到达，并且需要占用k个位置

2 L k: 表示正在等待的队伍第k支队伍将退出

3 C k: 表示已入座的队伍将退出，并腾出size[k]点空间

4 Q: 输出剩余已入座的队伍个数，未入座的队伍个数和正在等待的队首下标

2. 思路：这题由于数据过水，我们只需要存储每支队伍出现过的下标以及占用的空间大小，用两个map 分别存储已入座的队伍和正在等待的队伍。对于每次L操作，如果当前k队伍是处于正在等待的队伍当中，那么直接移出，对于C操作同样也是如此，最后输出每个map的大小和waitingmap中的第一个队伍下标

3. 算法：STL,模拟

}

#include <bits/stdc++.h>
using namespace std;
const int N=105;
int n, q;
bool occupied[N];
struct Team{
    int id, k;
};
list<Team> waitList;
unordered_map<int,list<Team>::iterator> waitPos;
unordered_map<int,pair<int,int>> seated;
int allocate(int k){// 分配 k 个连续窗口，返回起始位置（1-based），失败返回 -1
    for (int l=1;l+k-1<=n;l++){
        bool ok = true;
        for (int i=l;i<l+k;i++){
            if (occupied[i]){ ok=false; break; }
        }
        if (ok) {
            for (int i=l;i<l+k;i++) occupied[i]=true;
            return l;
        }
    }
    return -1;
}
void freeSeg(int l,int r) {// 释放窗口区间 [l, r]
    for (int i=l;i<=r;i++) occupied[i]=false;
}
void tryAssign(){// 尝试安排等待队首（直到无法安排或队列为空）
    while (!waitList.empty()){
        Team front=waitList.front();
        int start=allocate(front.k);
        if (start==-1) break;
        seated[front.id]={start,start+front.k-1};
        waitPos.erase(front.id);
        waitList.pop_front();
    }
}
int main() {
    cin >> n >> q;
    while (q--){
        char op;
        cin >> op;
        if (op=='A'){
            int id, k;
            cin >> id >> k;
            waitList.push_back({id, k});
            waitPos[id]=prev(waitList.end());
            tryAssign();
        } 
        else if (op=='L'){
            int id;
            cin >> id;
            auto it=seated.find(id);
            if(it!=seated.end()){
                auto [l,r]=it->second;
                freeSeg(l,r);
                seated.erase(it);
                tryAssign();
            }
        } 
        else if (op=='C') {
            int id;
            cin >> id;
            auto it=waitPos.find(id);
            if (it!=waitPos.end()) {
                waitList.erase(it->second);
                waitPos.erase(it);
                tryAssign(); // 关键：取消后也要尝试安排队首
            }
        } 
        else if (op=='Q') {
            int seatedCnt=seated.size();
            int waitingCnt=waitList.size();
            int frontId=waitingCnt?waitList.front().id:0;
            cout<<seatedCnt<<' '<<waitingCnt<<' '<<frontId<<endl;
        }
    }
}

3 文件系统{

1. 题意：有q次操作，分为以下几种：

            1 MK: 建立一个空目录，并命名为a

            2 RM K: 将k文件夹下的子文件夹全部删除

            3 MV k rev: 将文件夹k移到目录rev下

            4 TOUCH path s:创立一个大小为s的空文件夹

            5 Q k: 输出目录k下的文件夹数和文件夹总大小

2. 思路：这题主要考察对树结构的熟练程度。

  初始化：

· 

每个节点（目录或文件）有：

parent：父节点编号（根为 -1）

children：子节点映射（unordered_map<string, int>）

isDir：是否为目录

fileCnt：以该节点为根的子树中的普通文件个数（若节点本身是文件，则为1）

sumSize：这些文件的大小总和

对于 Q path 查询，直接返回 fileCnt 和 sumSize。

对于 TOUCH、RM、MV 等操作，除了修改树结构，还需要更新从该节点到根路径上所有祖先的统计信息。

具体操作：

** **1. 路径解析

由于路径以 '/' 开头，我们可以：

· 

去掉首尾的 '/'

·

按 '/' 分割，得到各段名称

· 

例如 "/a/b/c" → ["a","b","c"]，最后一段是名称，前面的路径是父目录

2. 查找节点

从根（编号0）开始，依次查找每段，返回最终节点编号。

3. 更新祖先

对某个节点 id，其子树变化量为 (deltaCnt, deltaSum)，则从 parent[id] 开始向上循环，对每个祖先加上该变化量。

  具体实现：

#include <bits/stdc++.h>
using namespace std;
using ll=long long;
struct Node{
    int parent;
    bool isDir;
    unordered_map<string,int> children;
    ll fileCnt;   // 子树文件个数
    ll sumSize;   // 子树文件总大小
};
vector<Node> nodes;
// 初始化根目录
void init(){
    nodes.push_back({-1, true, {}, 0, 0});
}
// 解析路径，返回 vector<string>（不包含空段）
vector<string> splitPath(const string& path){
    vector<string> res;
    stringstream ss(path);
    string seg;
    while (getline(ss, seg, '/')) {
        if (!seg.empty()) res.push_back(seg);
    }
    return res;
}
// 根据路径查找节点，保证路径存在
int findNode(const string& path){
    if (path=="/") return 0;
    auto parts=splitPath(path);
    int cur=0;
    for (const string& seg:parts){
        cur=nodes[cur].children[seg];
    }
    return cur;
}
// 获取父目录节点和最后一段名称
pair<int, string> getParentAndName(const string& path){
    auto parts=splitPath(path);//子路
    string name=parts.back();//每一段的文件名
    parts.pop_back();
    // 构建父目录路径
    string parentPath = "/";
    for (const string &s:parts) parentPath+=s+"/";
    if (parentPath.size()>1) parentPath.pop_back(); // 去掉末尾多余的 '/'
    int parentId = findNode(parentPath);
    return {parentId, name};
}
// 更新某个节点到根路径上的所有祖先
void addToAncestors(int id,ll dc,ll ds){
    int p=nodes[id].parent;
    while (p!=-1) {
        nodes[p].fileCnt+= dc;
        nodes[p].sumSize+=ds;
        p=nodes[p].parent;
    }
}
int main(){
    init();
    int q;
    cin >> q;
    while (q--){
        string op;
        cin >> op;
        if (op=="MK"){
            string path;
            cin >> path;
            auto [parentId, name]=getParentAndName(path);
            int id = nodes.size();
            nodes.push_back({parentId,true,{},0,0});
            nodes[parentId].children[name]=id;//子树大小
        } 
        else if (op=="TOUCH"){
            string path;
            ll s;
            cin >> path >> s;
            auto [parentId, name]=getParentAndName(path);
            int id=nodes.size();
            nodes.push_back({parentId, false, {}, 1, s});
            nodes[parentId].children[name]=id;
            addToAncestors(id,1,s);
        }
        else if (op=="RM"){
            string path;
            cin >> path;
            int id = findNode(path);
            int parentId=nodes[id].parent;  // 从父目录中移除
            string name;
            for (auto &p:nodes[parentId].children){ // 找到名称：需要在父目录的children中找到id对应的key
                if (p.second==id){
                    name=p.first;
                    break;
                }
            }
            nodes[parentId].children.erase(name);
            // 减去该节点的统计值
            ll dc=-nodes[id].fileCnt;
            ll ds=-nodes[id].sumSize;
            addToAncestors(id, dc, ds);
            // 可选：清理该节点，但无需再使用
        }
        else if (op=="MV"){
            string src, dst;
            cin >> src >> dst;
            int srcId=findNode(src);
            int dstId=findNode(dst);
            // 找到源在父目录中的名称
            int parentId=nodes[srcId].parent;
            string name;
            for (auto &p : nodes[parentId].children){
                if (p.second == srcId) { name=p.first; break; }
            }
            // 从原父目录移除
            nodes[parentId].children.erase(name);
            // 减去原父祖先
            ll dc=-nodes[srcId].fileCnt;
            ll ds=-nodes[srcId].sumSize;
            addToAncestors(srcId, dc, ds);
            // 改变父节点
            nodes[srcId].parent = dstId;
            nodes[dstId].children[name] = srcId;
            // 加上目标祖先
            dc=nodes[srcId].fileCnt;
            ds=nodes[srcId].sumSize;
            addToAncestors(srcId, dc, ds);
        }
        else if (op=="Q"){
            string path;
            cin >> path;
            int id = findNode(path);
            cout<<nodes[id].fileCnt<<' '<<nodes[id].sumSize<<'\n';
        }
    }
}

3.算法：树，模拟

}

4 文本编辑器{

1. 题意：有一个初始的字符串，并给定一些操作：

INS p s: 将字符串s插入到原串的位置p后面

DEL l r:删除原串的第l到第r个位置

REV l r:将原串的第l个位置到第r个位置翻转

CUT l r p:将原串中的第l个位置到第r个位置剪下来并插入到位置p后面

Q l1,r1,l2,r2:比较原串中两个区间位置内的子串是否相同

输出YES NO

2. 思路：这题恶心就恶心在这题得用新算法（虽然用暴力就能搞到60分，考场上也不缺剩下40分了）

首先先来普及一下FHQ treap 平衡树的概念：

由中国信竞选手范浩强提出，一种完全抛弃旋转的平衡树，只用分裂和合并来维持平衡树的性质

此算法主要依赖两种函数：merge和split：合并函数和分割函数

FHQ treap 的主要理念是：左子树+当前字符+右子树，而merge主要解决的是将除当前全部字符以外的子树全部合并为一棵左子树和一棵右子树，而split函数则主要解决子树间的节点分配问题

merge函数：

// 合并两棵树（a 的所有元素都在 b 的左边）
int merge(int a, int b){//treap树核心操作之一
    if (!a || !b) return a ? a : b;
    if (tr[a].pri<tr[b].pri) { // 小根堆，若优先级 a 更小
        pushdown(a);//处理儿子
        tr[a].r=merge(tr[a].r, b);//往右更新
        pushup(a);//更新节点哈希
        return a;
    } else {
        pushdown(b);
        tr[b].l=merge(a, tr[b].l);//往左更新
        pushup(b);
        return b;
    }
}

split函数：

// 分裂：将树 u 的前 k 个节点分到 a，剩余分到 b
void split(int u,int k,int &a,int &b){
    if (!u) { a=b=0; return; }
    pushdown(u);
    int lsz=tr[tr[u].l].sz;//左树大小
    if (k<=lsz){
        // 分裂左子树
        split(tr[u].l, k, a, tr[u].l);
        b=u;
        pushup(b);
    } 
	else {
        // 分裂右子树
        split(tr[u].r,k-lsz-1,tr[u].r,b);
        a=u;
        pushup(a);
    }
}

了解完这些以后，这题就基本解决了。因为我们这题中的所有操作都只依赖这两个函数,具体实现见代码：

Ins 插入函数：

   void insertStr(int p, const string& s){
    if (s.empty()) return;
    int newRoot=0;
    for (char c:s){
        newRoot=merge(newRoot, newNode(c));//将其与子树合并
    }
    int a, b;
    split(root, p, a, b);//顺序： a -> newstring -> b
    root = merge(merge(a, newRoot), b);
} 

REV翻转函数：

void reverseRange(int l, int r) {
    int a, b, c;
    split(root, l - 1, a, b);//分割前面0—l-1的区间
    split(b, r - l + 1, b, c);//分割后r-n的区间
    pushrev(b);//翻转中间
    root = merge(merge(a, b), c);//再次合并
}

CUT剪切函数：

void cutRange(int l, int r, int p) {// 剪切区间 [l, r] 并插入到位置 p 后面（p 基于删除后的字符串）
    int a, b, c;
    split(root, l - 1, a, b);
    split(b, r - l + 1, b, c);
    root = merge(a, c); // 先删除
    // 插入到删除后的位置 p 后面
    int x, y;
    split(root, p, x, y);
    root = merge(merge(x, b), y);
}

最后的查询函数：

ull getHash(int l, int r) {// 查询区间 [l, r] 的哈希值
    int a, b, c;
    split(root, l - 1, a, b);//切割出区间内的子串
    split(b, r - l + 1, b, c);
    ull res = tr[b].hash;//查询哈希值
    root = merge(merge(a, b), c);
    return res;
}
bool queryEqual(int l1, int r1, int l2, int r2) {// 比较两个子串是否相等
    int len1 = r1 - l1 + 1, len2 = r2 - l2 + 1;
    if (len1 != len2) return false;
    return getHash(l1, r1) == getHash(l2, r2);
}

完整代码（理解不了新算法，只能边打边想）：

#include <bits/stdc++.h>
using namespace std;
using ull=unsigned long long;
const int N=2e5+10;
const ull BASE=131;
int n, q, tot, root;
char initStr[N];
struct Node {
    int l, r;       // 左右孩子下标
    int sz;         // 子树大小
    int pri;        // 随机优先级
    char val;       // 当前字符
    ull hash;       // 子树哈希值
    bool rev;       // 翻转懒标记
} tr[N];
// 预计算 BASE 的幂
ull pw[N];
int newNode(char c){// 创建新节点
    tr[++tot]={0, 0, 1, rand(),c,c,false};
    return tot;
}
// 更新节点信息
void pushup(int u){
    int l=tr[u].l,r=tr[u].r;
    tr[u].sz=tr[l].sz+tr[r].sz+1;
    // 当前哈希 = 左子树哈希 * BASE^(右子树大小+1) + 当前字符 * BASE^(右子树大小) + 右子树哈希
    tr[u].hash=tr[l].hash*pw[tr[r].sz + 1]+(ull)tr[u].val*pw[tr[r].sz]+tr[r].hash;
}   
void pushrev(int u){ 
    if (!u) return;
    swap(tr[u].l,tr[u].r);
    tr[u].rev^=1;// 下传翻转标记 
}
void pushdown(int u){//懒标记法，快速为儿子节点分配好子节点
    if (tr[u].rev){
        pushrev(tr[u].l);
        pushrev(tr[u].r);
        tr[u].rev=false;
    }
}
// 合并两棵树（a 的所有元素都在 b 的左边）
int merge(int a, int b){//treap树核心操作之一
    if (!a || !b) return a ? a : b;
    if (tr[a].pri<tr[b].pri) { // 小根堆，若优先级 a 更小
        pushdown(a);//处理儿子
        tr[a].r=merge(tr[a].r, b);//往右更新
        pushup(a);//更新节点哈希
        return a;
    } else {
        pushdown(b);
        tr[b].l=merge(a, tr[b].l);//往左更新
        pushup(b);
        return b;
    }
}
// 分裂：将树 u 的前 k 个节点分到 a，剩余分到 b
void split(int u,int k,int &a,int &b){
    if (!u) { a=b=0; return; }
    pushdown(u);
    int lsz=tr[tr[u].l].sz;//左树大小
    if (k<=lsz){
        // 分裂左子树
        split(tr[u].l, k, a, tr[u].l);
        b=u;
        pushup(b);
    } 
	else {
        // 分裂右子树
        split(tr[u].r,k-lsz-1,tr[u].r,b);
        a=u;
        pushup(a);
    }
}
// 在位置 p 后插入字符串 s（p=0 表示开头）
void insertStr(int p, const string& s){
    if (s.empty()) return;
    int newRoot=0;
    for (char c:s){
        newRoot=merge(newRoot, newNode(c));//顺序一定不能反！必须保证第一项的所有节点都在第二项之前，否则整个流程就是反的
    }
    int a, b;
    split(root, p, a, b);
    root = merge(merge(a, newRoot), b);
}
void eraseRange(int l, int r) {// 删除区间 [l, r]
    int a, b, c;
    split(root, l - 1, a, b);
    split(b, r - l + 1, b, c);//将中间区间抽离
    root = merge(a, c);//合并剩余区间
}// 翻转区间 [l, r]
void reverseRange(int l, int r) {
    int a, b, c;
    split(root, l - 1, a, b);//抽离给定区间
    split(b, r - l + 1, b, c);
    pushrev(b);//打翻转标记
    root = merge(merge(a, b), c);//将顺序调换后合并
}
void cutRange(int l, int r, int p) {// 剪切区间 [l, r] 并插入到位置 p 后面（p 基于删除后的字符串）
    int a, b, c;
    split(root, l - 1, a, b);
    split(b, r - l + 1, b, c);
    root = merge(a, c); // 先删除
    // 插入到删除后的位置 p 后面
    int x, y;
    split(root, p, x, y);
    root = merge(merge(x, b), y);
}
ull getHash(int l, int r) {// 查询区间 [l, r] 的哈希值
    int a, b, c;
    split(root, l - 1, a, b);
    split(b, r - l + 1, b, c);
    ull res = tr[b].hash;
    root = merge(merge(a, b), c);
    return res;
}
bool queryEqual(int l1, int r1, int l2, int r2) {// 比较两个子串是否相等
    int len1 = r1 - l1 + 1, len2 = r2 - l2 + 1;
    if (len1 != len2) return false;
    return getHash(l1, r1) == getHash(l2, r2);
}
int buildTree(int l, int r, const string& s){// 从初始字符串建树（递归建树，保证平衡）
    if (l > r) return 0;
    int mid = (l + r) >> 1;
    int u = newNode(s[mid]);
    tr[u].l = buildTree(l, mid - 1, s);
    tr[u].r = buildTree(mid + 1, r, s);
    pushup(u);
    return u;
}
int main() {
    pw[0] = 1;
    for (int i=1;i<N;i++) pw[i]=pw[i-1]*BASE;
    string s;
    cin >> s;
    root = buildTree(0, s.size() - 1, s);
    cin >> q;
    while (q--) {
        string op;
        cin >> op;
        if (op=="INS") {
            int p;
            string t;
            cin >> p >> t;
            insertStr(p, t);
        } else if (op=="DEL") {
            int l, r;
            cin >> l >> r;
            eraseRange(l, r);
        } else if (op=="REV") {
            int l, r;
            cin >> l >> r;
            reverseRange(l, r);
        } else if (op=="CUT") {
            int l, r, p;
            cin >> l >> r >> p;
            cutRange(l, r, p);
        } else if (op=="Q") {
            int l1, r1, l2, r2;
            cin >> l1 >> r1 >> l2 >> r2;
            cout<<(queryEqual(l1, r1, l2, r2) ? "YES":"NO")<<endl;
        }
    }
}