题面
https://www.luogu.com.cn/problem/P6619
分析
题目说的复杂,不过这种逐个对战多询问的基本上都有只和双方最值有关的结论,这题也不例外
简单整理可得对战消耗的能量是 $2\times min(\sum ice,\sum fire)$
然后不难发现 $\sum ice$ 是随温度单调不减的,$\sum fire$ 是随温度单调不增的
那么显然答案应该是两者图像的交点,但是严格来说这不是曲线而是离散的点,所以没有确切交点
那么问题转化为找到一个最大的 $x$ 有 $\sum_{ice_i\leq x} ice_i \leq \sum_{fire_i>x} fire_i$ 或者最小的 $x$ 有 $\sum_{ice_i\leq x} ice_i > \sum_{fire_i>x} fire_i$
其中第二种找到这个 $x$ 后需要找到等效的最大的 $y$ 满足 $\sum_{fire_i>x} fire_i \leq \sum_{fire_i>y} fire_i $ (因为要求能量值最大的情况下温度最高)
不难想到线段树二分,但是常数过大会T
我们可以用两个树状数组维护 $\sum ice$ $\sum fire$,然后运用它lowbit的神奇性质
因为 $t[x]$ 储存的数据就是 $x-lowbit(x)+1~x$ 这段的数据,也就是说当我们想从一个 $x$ 跳到 $x+2^j (2^j
所以我们可以利用倍增的思想在树状数组上跳跃,这样就可以用 $O(nlogn)$ 的时间通过此题
代码
#include
#include
#include
#include
#define lowbit(x) (x&-x)
using namespace std;
const int N=2e6+10;
int q,m,tp[N],x[N],y[N],a[N],b[N],t[2][N],fsum;
void Add(int id,int x,int k) {for (;x<=b[0];x+=lowbit(x)) t[id][x]+=k;}
int Query(int id,int x) {if (x<=0||x==b[0]+1) return 0;int ans=0;for (;x;x-=lowbit(x)) ans+=t[id][x];return ans;}
int main() {
scanf("%d",&q);
for (int i=1,ord;i<=q;i++) {
scanf("%d%d",&ord,&tp[i]);
if (ord==1) scanf("%d%d",&x[i],&y[i]),b[++b[0]]=x[i];
}
sort(b+1,b+b[0]+1);b[0]=unique(b+1,b+b[0]+1)-b-1;
m=log2(b[0]);m=1<<m;
for (int i=1;i<=q;i++) {
if (x[i]) {
x[i]=lower_bound(b+1,b+b[0]+1,x[i])-b;
Add(tp[i],x[i],y[i]);
if (tp[i]) fsum+=y[i],a[x[i]]+=y[i];
}
else {
Add(tp[tp[i]],x[tp[i]],-y[tp[i]]);
if (tp[tp[i]]) fsum-=y[tp[i]],a[x[tp[i]]]-=y[tp[i]];
}
int k=0,ice=0,fire=fsum;
for (int j=m;j;j>>=1)
if (k+j<=b[0]&&ice+t[0][k+j]<=fire-t[1][k+j]+a[k+j]) ice+=t[0][k+j],fire-=t[1][k+j],k+=j;
int ans1=ice,ans2=fire;
if (!max(ans1,ans2)) {printf("Peace\n");continue;}
if (ans1>ans2) printf("%d %lld\n",b[k],2ll*ans1);
else {
fire=fsum;k=0;
for (int j=m;j;j>>=1)
if ((k|j)!=k&&k+j<=b[0]&&ans2<=fire-t[1][k+j]+a[k+j]) fire-=t[1][k+j],k+=j;
printf("%d %lld\n",b[k],2ll*ans2);
}
}
}