ABC127F
*2003
这个定数让我很心动阿。可惜了。
题目描述
有一个函数 \(f(x)\) ，初始时 \(f(x)=0\)
接下来你会对这个函数进行 \(Q\) 次以下操作：
- \(\texttt{1 a b}\)，将 \(f(x)\) 替换为 \(g(x)=f(x)+|x-a|+b\)
- \(\texttt{2}\)，询问最小的整数 \(x\) ，使得 \(f(x)\) 取到最小值，以及 \(f(x)\) 的最小值
数据范围与提示
\(1 \le Q \le 200000,-10^9 \le a,b \le 10^9\) ，保证第一次操作一定是修改操作
题解
一开始以为这个函数是那种嵌套的。就是 \(g(x)=|f(x)-a|+b\) 这种抽象东西。
后面发现不是，然后就等价于大力累加所有的 \(b\) ，然后就是一车 \(a\) ，找到一个点给他们取绝对值。
我们在小学二年级的时候就在某而思学过修厕所模型，所以最小的 \(x\) 一定在中位数处取到。
用对顶堆维护就好了。
const ll maxn=2e5+5;
priority_queue<ll,vector<ll>,greater<ll> >q;
priority_queue<ll>p;
ll n,sum;
ll ls,rs;
void upd(){
while(q.size()>p.size()){
ll u=q.top();
q.pop();
rs-=u;
ls+=u;
p.push(u);
}
while(p.size()-q.size()>1){
ll u=p.top();
p.pop();
ls-=u;
rs+=u;
q.push(u);
}
}
void solve(){
n=R;
n--;
R;
p.push(R);
ls+=p.top();
sum+=R;
while(n--){
ll opt=R;
if(opt==1){
ll a=R,b=R;
sum+=b;
if(a>p.top())q.push(a),rs+=a;
else p.push(a),ls+=a;
upd();
}
else {
wk(p.top());
we((p.size()>q.size()?rs-ls+p.top():rs-ls)+sum);
}
}
return ;
}