题解：P14713 [ICPC 2023 Tehran R] Monster Warehouse
lailai0916 · · 题解
题意简述
维护散装货物和可递归嵌套的容器。操作包括购入、出售、拆箱和用散装货物打包。还要查询某种散装货物的数量、包含它的顶层容器数，以及取得它至少需要拆开多少层容器。货物名不区分大小写。
解题思路
先考虑容器的解析。
一个容器描述天然对应一棵有根树。每个结点表示一个容器，保存两类信息：
- 直接位于该容器内的货物及数量；
- 按输入顺序排列的直接子容器编号。
用指针从左向右扫描整行。读到左括号时递归建立新结点，读到右括号时结束当前结点。货物可能写成数量在前、数量在后或省略数量三种形式，分别处理即可。所有名称转为小写，再用哈希表压缩为整数编号。
容器树建立后不会再改变。UNPACK 只会令原来的根容器失效，并让它的直接子结点分别成为新的根，不需要复制或修改子树。
接着为当前根容器建立摘要。
当前拥有编号的容器，称为根容器。对每个根容器遍历其子树，并为出现过的每种货物记录最小深度。根内直接货物的深度为
这个最小深度恰好等于取得一件该货物所需的拆箱次数。更深位置的同种货物不会影响任何查询，因此摘要中每种货物只保留一个值。
处理 PACK 时，还要统计描述中每种货物的总需求量。遍历同一棵树时额外累加数量即可。其他操作不需要这份总量。
不把摘要永久缓存到每个树结点中。否则，一条深链上的同一种统计会保存在大量祖先中。只有某个结点成为根容器时，才计算并保存它的摘要。
最后维护所有根容器的全局信息。
对每种货物维护一个有序集合。集合元素为二元组：
其中
根容器加入仓库时，把摘要中的所有二元组插入对应集合。根容器失效时，按容器编号精确删除相同二元组。编号互不相同，因此普通 set 已足够处理深度相同的多个容器。
这个集合同时回答两种查询。集合大小就是包含该货物的根容器数；首元素的深度就是从所有容器取得它所需的最少拆箱次数。另用一个数组保存每种散装货物的数量。
下面逐项处理操作：
BUY：解析新树，计算根摘要，分配新编号并加入全局集合；SELL：若编号有效，则删除对应摘要并令编号失效；UNPACK：删除原摘要，直接货物入库，并按原顺序加入子容器；PACK：解析描述并统计全部需求，库存足够时统一扣除，再加入新根容器；否则整条操作作废。
失败的 PACK 不分配编号。UNPACK 的子容器按解析时保存的顺序依次加入，所以编号顺序也符合题意。
对于 COUNT，直接返回散装数量。对于 CONTAINS，返回对应有序集合的大小。对于 MIN，若散装数量非零则返回
设一次操作实际遍历的子树大小为
一次拆箱产生的各棵子树互不相交。因此，该次拆箱的总遍历量仍为原容器子树大小。查询只需期望
所有当前根容器的子树也互不相交，空间复杂度为
参考代码
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
struct Node
{
vector<pair<int,int>> a;
vector<int> son;
};
struct Stat
{
vector<pair<int,int>> mn;
vector<pair<int,ll>> sum;
};
struct Box
{
int rt=-1;
vector<pair<int,int>> mn;
};
vector<Node> tr;
vector<Box> box;
unordered_map<string,int> mp;
vector<ll> num;
vector<set<pair<int,int>>> dep;
string s;
int pos;
int get(string x)
{
for(char &c:x)c=char(tolower((unsigned char)c));
auto it=mp.find(x);
if(it!=mp.end())return it->second;
int res=mp.size();
mp[x]=res;
num.push_back(0);
dep.emplace_back();
return res;
}
void skip()
{
while(pos<s.size()&&isspace((unsigned char)s[pos]))pos++;
}
int read_num()
{
int res=0;
while(pos<s.size()&&isdigit((unsigned char)s[pos]))res=res*10+s[pos++]-'0';
return res;
}
string read_word()
{
string res;
while(pos<s.size()&&isalpha((unsigned char)s[pos]))res+=s[pos++];
return res;
}
int parse()
{
int u=tr.size();
tr.push_back({});
pos++;
while(1)
{
skip();
if(s[pos]==')')
{
pos++;
return u;
}
if(s[pos]==',')
{
pos++;
continue;
}
if(s[pos]=='(')
{
int v=parse();
tr[u].son.push_back(v);
continue;
}
int c=1;
string x;
if(isdigit((unsigned char)s[pos]))
{
c=read_num();
skip();
x=read_word();
}
else
{
x=read_word();
skip();
if(pos<s.size()&&isdigit((unsigned char)s[pos]))c=read_num();
}
tr[u].a.push_back({get(x),c});
}
}
void dfs(int u,int d,unordered_map<int,int> &mn,unordered_map<int,ll> &sum,bool need)
{
for(auto [g,c]:tr[u].a)
{
auto it=mn.find(g);
if(it==mn.end()||d<it->second)mn[g]=d;
if(need)sum[g]+=c;
}
for(auto v:tr[u].son)dfs(v,d+1,mn,sum,need);
}
Stat calc(int rt,bool need)
{
unordered_map<int,int> mn;
unordered_map<int,ll> sum;
dfs(rt,1,mn,sum,need);
Stat res;
for(auto [g,d]:mn)res.mn.push_back({g,d});
for(auto [g,c]:sum)res.sum.push_back({g,c});
return res;
}
void add(int rt,vector<pair<int,int>> mn)
{
int id=box.size();
for(auto [g,d]:mn)dep[g].insert({d,id});
box.push_back({rt,move(mn)});
}
bool valid(int id)
{
return id>0&&id<box.size()&&box[id].rt!=-1;
}
void del(int id)
{
for(auto [g,d]:box[id].mn)dep[g].erase({d,id});
box[id].rt=-1;
vector<pair<int,int>>().swap(box[id].mn);
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
box.push_back({});
while(getline(cin,s))
{
if(!s.empty()&&s.back()=='\r')s.pop_back();
if(s.empty())continue;
stringstream ss(s);
string cmd;
ss>>cmd;
if(cmd=="BUY")
{
pos=s.find('(');
int rt=parse();
Stat t=calc(rt,0);
add(rt,move(t.mn));
cout<<"OK"<<'\n';
}
else if(cmd=="SELL")
{
int id;
ss>>id;
if(!valid(id))cout<<"DISCARD"<<'\n';
else
{
del(id);
cout<<"OK"<<'\n';
}
}
else if(cmd=="UNPACK")
{
int id;
ss>>id;
if(!valid(id))cout<<"DISCARD"<<'\n';
else
{
int rt=box[id].rt;
del(id);
for(auto [g,c]:tr[rt].a)num[g]+=c;
int cnt=tr[rt].son.size();
for(auto v:tr[rt].son)
{
Stat t=calc(v,0);
add(v,move(t.mn));
}
cout<<"OK, ";
if(!cnt)cout<<"No containers added."<<'\n';
else if(cnt==1)cout<<"1 container added."<<'\n';
else cout<<cnt<<" containers added."<<'\n';
}
}
else if(cmd=="PACK")
{
pos=s.find('(');
int rt=parse();
Stat t=calc(rt,1);
bool ok=1;
for(auto [g,c]:t.sum)if(num[g]<c)ok=0;
if(!ok)cout<<"DISCARD"<<'\n';
else
{
for(auto [g,c]:t.sum)num[g]-=c;
add(rt,move(t.mn));
cout<<"OK"<<'\n';
}
}
else
{
string type,x;
ss>>type>>x;
int g=get(x);
if(type=="COUNT")cout<<num[g]<<'\n';
else if(type=="CONTAINS")cout<<dep[g].size()<<'\n';
else if(type=="MIN")
{
if(num[g])cout<<0<<'\n';
else if(dep[g].empty())cout<<-1<<'\n';
else cout<<dep[g].begin()->first<<'\n';
}
}
}
return 0;
}