题解：CF2176E Remove at the lowest cost
WAWA_OVO
·
·
题解
考虑无修改
先用单调栈预处理出 L_i 表示左边第一个满足 a_{L_i}>a_i，R_i 同理。
对于确定的序列，贪心过程是每次选 c_i 最小的，然后把 L_i 到 R_i 所有没被删除的元素对 i 做保留 i 的删除操作。
考虑刻画这个过程，可以理解为先按 c_i 为关键字由小到大排序，然后依次对 L_i 到 R_i 没有被染色过的格子染上 c_i 的颜色。
我们设最后第 i 个格子颜色是 d_i，a_i 最大的元素中 c_i 的最小值为 last，答案就是 (\sum_{i=1}^{n} d_i)-last（减去 last 的原因是最后只剩一个元素时多算了一次删除价值为 last 的代价）。
## 考虑有修改
修改是将一个点的 $c_i=0$，显然可以先用 $0$ 的代价将 $L_i$ 到 $R_i$ 的所有元素删除，这就相当与是把 $L_i$ 到 $R_i$ 区间颜色改为 $0$，可以用线段树区间赋 $0$，最后的答案是 $\max((\sum_{i=1}^{n} d_i)-last,0)$（和 $0$ 取最大值是当 $a_i$ 最大的元素中 $c_i$ 的最小值为 $0$ 时总代价为 $0$ 此时不需要减 $last$）。
## 代码
```cpp
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int maxn=200005;
int T,n;
struct DHC{
int a,c,id;
bool operator < (const DHC b) const {return c<b.c;}
}arr[maxn];
namespace dhcio{
inline int read(){
char ch=getchar();int ret=0,f=1;
while(ch<'0'||ch>'9'){if(ch=='-') f=-f;ch=getchar();}
while(ch>='0'&&ch<='9') ret=(ret<<3)+(ret<<1)+(ch&15),ch=getchar();
return ret*f;
}
inline void write(int x){
if(x<0) x=-x,putchar('-');
if(x>9) write(x/10);
putchar('0'+x%10);
}
}
using namespace dhcio;
struct SegmentTree{
#define ls (p<<1)
#define rs (p<<1|1)
int sum[4*maxn],tag[4*maxn];
void add_tag(int p,int pl,int pr,int d){sum[p]=(pr-pl+1)*d,tag[p]=d;}
void push_down(int p,int pl,int pr){
if(tag[p]==-1) return;
int mid=pl+pr>>1;
add_tag(ls,pl,mid,tag[p]);add_tag(rs,mid+1,pr,tag[p]);
tag[p]=-1;
}
void push_up(int p){sum[p]=sum[ls]+sum[rs];}
void build(int p,int pl,int pr){
if(pl==pr){sum[p]=0;tag[p]=0;return;}
int mid=pl+pr>>1;
build(ls,pl,mid);build(rs,mid+1,pr);
tag[p]=-1;push_up(p);
}
void update(int p,int pl,int pr,int L,int R,int d){
if(L<=pl&&pr<=R){add_tag(p,pl,pr,d);return;}
int mid=pl+pr>>1;push_down(p,pl,pr);
if(L<=mid) update(ls,pl,mid,L,R,d);
if(R> mid) update(rs,mid+1,pr,L,R,d);
push_up(p);
}
int query(int p,int pl,int pr,int L,int R){
if(L<=pl&&pr<=R) return sum[p];
int mid=pl+pr>>1,res=0;push_down(p,pl,pr);
if(L<=mid) res+=query(ls,pl,mid,L,R);
if(R> mid) res+=query(rs,mid+1,pr,L,R);
push_up(p);
return res;
}
#undef ls
#undef rs
}tree;
int L[maxn],R[maxn];
void solve(){
n=read();
for(int i=1;i<=n;i++) arr[i].id=i;
for(int i=1;i<=n;i++) arr[i].a=read();
for(int i=1;i<=n;i++) arr[i].c=read();
stack<int> st;
for(int i=1;i<=n;i++){
while(!st.empty()&&arr[st.top()].a<=arr[i].a) st.pop();
if(st.empty()) L[i]=1;else L[i]=st.top()+1;
st.push(i);
}
while(!st.empty()) st.pop();
for(int i=n;i;i--){
while(!st.empty()&&arr[st.top()].a<=arr[i].a) st.pop();
if(st.empty()) R[i]=n;else R[i]=st.top()-1;
st.push(i);
}
tree.build(1,1,n);int now=0;
sort(arr+1,arr+1+n);reverse(arr+1,arr+1+n);
for(int i=1;i<=n;i++){
tree.update(1,1,n,L[arr[i].id],R[arr[i].id],arr[i].c);
if(L[arr[i].id]==1&&R[arr[i].id]==n) now=arr[i].c;
}
for(int t=1;t<=n;t++){write(max(tree.sum[1]-now,0ll));putchar(' ');int pos=read();tree.update(1,1,n,L[pos],R[pos],0);}
write(max(tree.sum[1]-now,0ll));putchar('\n');
}
signed main(){
T=read();
while(T--) solve();
return 0;
}
```