链接
分析
别看题目说了一大串，实际上就是要让你动态维护一个 \(x\) 满足 \(\min\{\sum\limits_{A_i\ge x}a_i,\sum\limits_{B_i\le x}b_i\}\) 最大，其中 \(A,B\) 是温度，\(a,b\) 是能量，总能量消耗就是最大值的两倍。
发现 \(\sum\limits_{A_i\ge x}a_i\) 是随 \(x\) 而单减的，而 \(\sum\limits_{B_i\le x}b_i\) 是随 \(x\) 而单增的。
容易想到一个 \(O(n\log^2 n)\) 的算法。
首先判断 Peace 只需要用线段树维护一下 \(A\) 的最大值和 \(B\) 的最小值即可。
先二分出第一个使得 \(\sum\limits_{A_i\ge x}a_i<\sum\limits_{B_i\le x}b_i\) 的 \(x\)，前一个 \(x'\) 和 \(\sum\limits_{B_i\le x'}b_i\) 是一个可能的答案。同时找到 \(x\) 后的 \(\sum\limits_{A_i\ge x}a_i\) 也可能作为答案，所以再二分出最后一个 \(x''\) 使得 \(\sum\limits_{A_i\ge x}a_i=\sum\limits_{A_i\ge x''}a_i\)，这样择优选择即可。
因为二分时需要查询前缀 \(B\) 和后缀 \(A\)，我们可以维护两个树状数组，其中 \(A\) 的树状数组倒叙添加查询。
于是时间复杂度是两只 \(log\)。开了 O2 可以跑过 3s。
点击查看代码
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define in read()
inline int read(){
int p=0,f=1;
char c=getchar();
while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
while(isdigit(c)){p=p*10+c-'0';c=getchar();}
return p*f;
}
const int N=2e6+5;
int q[N],qn,n;
struct ques{
int opt,t,x,y;
}Q[N];
int c[N],s[N];
inline int lowbit(int x){return x&(-x);}
inline void updatec(int x,int d){for(int i=x;i<=qn;i+=lowbit(i))c[i]+=d;}
inline int queryc(int x){int res=0;for(int i=x;i>0;i-=lowbit(i))res+=c[i];return res;}
inline void updates(int x,int d){for(int i=x;i<=qn;i+=lowbit(i))s[i]+=d;}
inline int querys(int x){int res=0;for(int i=x;i>0;i-=lowbit(i))res+=s[i];return res;}
inline int bin(int x){
int l=1,r=qn,mid;
for(mid=(l+r)>>1;l<r;mid=(l+r)>>1)
if(q[mid]<x)l=mid+1;
else r=mid;
return l;
}
int maxn[N<<2],minn[N<<2];
inline void changec(int l,int r,int p,int x,int d){
if(l==r){minn[p]=d;return ;}
int mid=(l+r)>>1;
if(x<=mid)changec(l,mid,p<<1,x,d);
else changec(mid+1,r,p<<1|1,x,d);
minn[p]=min(minn[p<<1],minn[p<<1|1]);
}
inline void changes(int l,int r,int p,int x,int d){
if(l==r){maxn[p]=d;return ;}
int mid=(l+r)>>1;
if(x<=mid)changes(l,mid,p<<1,x,d);
else changes(mid+1,r,p<<1|1,x,d);
maxn[p]=max(maxn[p<<1],maxn[p<<1|1]);
}
inline void solve(){
//cout<<minn[1]<<' '<<maxn[1]<<'\n';
if(minn[1]>maxn[1]){puts("Peace");return ;}
int l=minn[1],r=maxn[1],mid=(l+r)>>1;
while(l<r){
mid=(l+r)>>1;
if(querys(qn-mid+1)<queryc(mid))r=mid;
else l=mid+1;
}
int ans1=0,ans2=0,tmp;
if(querys(qn-l+1)<queryc(l)){
if(l!=minn[1])ans1=q[l-1],ans2=queryc(l-1);
tmp=querys(qn-l+1);
if(!ans1||tmp>=ans2){
r=maxn[1];
for(r=maxn[1],mid=(l+r+1)>>1;l<r;mid=(l+r+1)>>1)
if(querys(qn-mid+1)>=tmp)l=mid;
else r=mid-1;
ans1=q[l],ans2=tmp;
}
}
else ans1=q[maxn[1]],ans2=queryc(maxn[1]);
cout<<ans1<<' '<<2*ans2<<'\n';
}
signed main(){
n=in;
for(int i=1;i<=n;i++){
Q[i].opt=in;
if(Q[i].opt==1)Q[i].t=in,Q[i].x=in,Q[i].y=in,q[++qn]=Q[i].x;
else Q[i].x=in;
}
sort(q+1,q+1+qn);
qn=unique(q+1,q+1+qn)-(q+1);
memset(minn,127,sizeof(minn));
memset(maxn,128,sizeof(maxn));
for(int i=1,opt,t,x;i<=n;i++){
opt=Q[i].opt;
if(opt==1){
x=bin(Q[i].x);
if(Q[i].t)updates(qn-x+1,Q[i].y),changes(1,qn,1,x,x);
else updatec(x,Q[i].y),changec(1,qn,1,x,x);
}
else{
t=Q[i].x,x=bin(Q[t].x);
if(Q[t].t)updates(qn-x+1,-Q[t].y),changes(1,qn,1,x,maxn[0]);
else updatec(x,-Q[t].y),changec(1,qn,1,x,minn[0]);
}
solve();
}
return 0;
}
这样二分答案再树状数组查询并不优秀，我们有一个更优秀的办法。
利用树状数组本身的性质在树状数组上二分，每次从后往前跳，累加树状数组路径来进行判断。
时间复杂度降为 \(O(n\log n)\)。