CF1455G Forbidden Value
已知初始值\(x=0\)，给定下面2种命令：
set\(y\) \(v\)，令\(x=y\)，或花费\(v\)元钱删除该命令；if\(y\) ...end，如果\(x==y\)，执行if...end中的命令，否则跳过该if...end。你需要使用最少的花费，使得无论运行到哪里，都有\(x \neq s\)。
可以考虑对这些命令建树，对于每个 if...end 这个命令中的命令，其父亲节点为这个 if。整个程序可以看作在一个 if 0 ... end 命令中，这个命令为根节点。这个建树用一个栈就可以实现了。
然后我们考虑一个比较显然的动态规划。定义 \(dp_{i,j}\) 表示执行子树 \(i\) 中的命令，最后的数为 \(j\) 的最小花费。如果现在有 set y v 操作，将所有下标非 \(y\) 的 \(dp\) 值变大 \(v\)，\(y\) 位置的值不变（注意判断是否\(y=s\)）。对于 if y ...end 操作，可以计算出这个 if 子树内的 \(dp\) 数组，然后对于 \(y\) 位置，更改为子树内的 \(dp\) 值，对于非 \(y\) 位置，原数组与子树数组取最小值即可。
这个 \(dp\) 可以使用线段树合并优化。就是上述过程用线段树合并实现。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;
typedef long long ll;
inline ll read(){
ll x=0,f=1;char ch=getchar();
while(ch<'0'||'9'<ch){if(ch=='-')f=-1;ch=getchar();}
while('0'<=ch&&ch<='9'){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
return x*f;
}
const int N=200005,M=200000;
ll INF=0x3f3f3f3f3f3f3f3f;
int n,s;
struct options{int op,y;ll v;}opt[N];
vector<int>edge[N];
int lc[N*20],rc[N*20],rt[N],tot;ll minv[N*20],tag[N*20];
#define mid ((l+r)>>1)
inline void modify(int p,ll v){minv[p]+=v;tag[p]+=v;}
inline void pushup(int p){minv[p]=min(minv[lc[p]],minv[rc[p]]);}
inline void pushdown(int p){
if(!tag[p])return;
if(lc[p])modify(lc[p],tag[p]);
if(rc[p])modify(rc[p],tag[p]);
tag[p]=0;
}
void change(int &p,int l,int r,int L,ll v){
if(!p)minv[p=++tot]=INF;
if(l==r){minv[p]=v;return;}
pushdown(p);
if(L<=mid)change(lc[p],l,mid,L,v);
else change(rc[p],mid+1,r,L,v);
pushup(p);
}
ll query(int p,int l,int r,int L){
if(!p)return INF;
if(l==r)return minv[p];
pushdown(p);
if(L<=mid)return query(lc[p],l,mid,L);
return query(rc[p],mid+1,r,L);
}
int merge(int x,int y,int l,int r){
if(!x||!y)return x+y;
if(l==r){minv[x]=min(minv[x],minv[y]);return x;}
pushdown(x);pushdown(y);
lc[x]=merge(lc[x],lc[y],l,mid);
rc[x]=merge(rc[x],rc[y],mid+1,r);
pushup(x);return x;
}
void dfsp(int u){
change(rt[u],0,M,opt[u].y,0);
for(auto v:edge[u]){
if(opt[v].op==1){
ll tmp=minv[rt[u]];
modify(rt[u],opt[v].v);
if(opt[v].y!=s)change(rt[u],0,M,opt[v].y,tmp);
}else{
ll tmp=query(rt[u],0,M,opt[v].y);
if(tmp!=INF){
dfsp(v);
modify(rt[v],tmp);
change(rt[u],0,M,opt[v].y,INF);//如果我们能进入这个 If 语句，那么显然 dp_{u,y} 的代价要重新计算，必须删除原有贡献
rt[u]=merge(rt[u],rt[v],0,M);//不然这里 dp_{u,y} 还会保留原先的值。
}
}
}
}
int stk[N],top=0;
int main(){
scanf("%d%d",&n,&s);int nod=1;
stk[++top]=nod;
char s[10];
for(int i=1;i<=n;++i){
scanf("%s",s);
if(s[0]=='s'){
opt[++nod].op=1;
opt[nod].y=read(),opt[nod].v=read();
edge[stk[top]].push_back(nod);
}else if(s[0]=='i'){
opt[++nod].op=2;
opt[nod].y=read();
edge[stk[top]].push_back(nod);
stk[++top]=nod;
}else --top;
}
minv[0]=INF;dfsp(1);
printf("%lld\n",minv[rt[1]]);
return 0;
}