题意分析

对于每次修改后的情况,求一个最大的 $k$ ,使得温度不大于 $k$ 的冰系战士的能量和与温度不小于 $k$ 的火系战士的能量和的最小值最大。

思路分析

显然所求的 $k$ 一定是某战士的温度,因此先将数据进行升序排序离散化处理。此时问题就转变为,设冰系与火系战士组成的序列分别为 $a,b$ ,则求一个最大的 $x$ ,使得在 $x$ 位置 $a$ 的前缀和与 $b$ 的后缀和的最小值最大。

60pts

可以发现答案具有单调性,想到二分答案。 $check$ 函数很容易想到暴力地每次查询前后缀和判断,用树状数组或线段树维护前后缀和,时间复杂度 $O(nlog^2n)$ ,可以拿到 $60$ 分。维护 $b$ 序列时,可以用倒着维护后缀和的方式维护前缀和。

注意,由于题目要求的是最大的 $x$,在 $a$ 序列的前缀和大于 $b$ 序列的后缀和的情况为答案时,此时二分到的 $x$ 应该最大的使 $a$ 的前缀和不大于 $b$ 的后缀和的 $x$ ,因此需要额外进行一次处理,找到该情况下最大的 $x$ 。

...bool check(int x){    int lsum=askl(x),rsum=askr(cnt-x+1);//分别查询 a,b 的前缀和,这里用倒着维护后缀和的方式维护前缀和    now=min(lsum,rsum);    return lsum<=rsum;}//二分判断void get(){    int l=1,r=cnt,mid=(l+r)>>1;    while(l<=r)    {        if(askr(cnt-mid+1)<now)            r=mid-1;        else            l=mid+1;        mid=(l+r)>>1;    }    ans=mid;}//额外处理void query(){    int l=1,r=cnt,mid=(l+r)>>1,lsum,rsum,val;    while(l<=r)    {        if(check(mid))            l=mid+1;        else            r=mid-1;        mid=(l+r)>>1;    }    lsum=askl(mid),rsum=askr(cnt-mid+1),val=min(lsum,rsum);    lsum=askl(mid+1),rsum=askr(cnt-mid),now=min(lsum,rsum);    if(now>=val)        get();    else        now=val,ans=mid;}int main(){    ...    for(int i=1;i<=Q;i++)        if(p(i)==1)        {            int x=lower_bound(b+1,b+cnt+1,x(i))-b;            if(!t(i))                changel(x,y(i));            else                changer(cnt-x+1,y(i));            query();            if(now)                printf("%d %d\n",b[ans],now*2);            else                puts("Peace");        }        else        {            int x=lower_bound(b+1,b+cnt+1,x(t(i)))-b;            if(!t(t(i)))                changel(x,-y(t(i)));            else                changer(cnt-x+1,-y(t(i)));            query();            if(now)                printf("%d %d\n",b[ans],now*2);            else                puts("Peace");        }    ...}

100pts

每次都查询一次前后缀和显然耗费了较多的时间,想到从这里进行优化。

根据树状数组的性质: $c_x$ 存储区间 $[x-lowbit(x)+1,x]$ 中的数据 可知,可以直接对树状数组进行类似倍增的二分。这样,对于每次二分到的 $x$ ,下一次加上一个数在二进制下表现为在 $x$ 的最末位的 $1$ 后某一位添上一个 $1$ ,即若加上的数为 $y$ ,则有 $lowbit(x+y)=y$ ,因此 $c_y$ 存储的即为区间 $[x+1,y]$ 的数据,尝试是否可行即可。

由于这里是直接对树状数组进行二分,因此对 $b$ 序列倒着维护前缀和的方式不方便操作,可以先统计 $b$ 序列的总和,再用总和减去前缀和来得到后缀和。

这样可以减掉一个 $log$ 的复杂度,将时间复杂度降到 $O(nlogn)$ ,理论上可以拿到 $100$ 分。但是本题卡常十分毒瘤,卡过去还是有一定难度的。

#include<iostream>#include<cstdio>#include<algorithm>#define rg register #define il inlineusing namespace std;const int N=2e6+10;struct Que{    int p,t,x,y;    #define p(i) q[i].p    #define t(i) q[i].t    #define x(i) q[i].x    #define y(i) q[i].y}q[N+100];int Q,cnt,now,ans,rcnt;int b[N],tl[N],tr[N];il int read(){    int w=1,num=1;    char ch;    while(ch=getchar(),ch<'0' || ch>'9')        if(ch=='-') w=-1;    num=ch-'0';    while(ch=getchar(),ch>='0' && ch<='9')        num=(num<<3)+(num<<1)+ch-'0';    return num*w;}//快读il void changel(int p,int k){    for(;p<=N;p+=p&-p)        tl[p]+=k;}//冰系序列修改il int askl(int p){    rg int val=0;    for(;p;p-=p&-p)        val+=tl[p];    return val;}//冰系序列查询il void changer(rg int p,int k){    for(;p<=N;p+=p&-p)        tr[p]+=k;}//火系序列修改il int askr(rg int p){    rg int val=0;    for(;p;p-=p&-p)        val+=tr[p];    return val;}//火系序列查询il void query(){    rg int p=0,lsum=0,rsum=0;    for(rg int i=20;i>=0;i--)        if(p+(1<<i)<=cnt && lsum+tl[p+(1<<i)]<rcnt-rsum-tr[p+(1<<i)])        {            p+=(1<<i);            lsum+=tl[p],rsum+=tr[p];        }//树状数组二分    rg int lans=min(lsum,rcnt-rsum),rans=min(askl(p+1),rcnt-askr(p));//分别计算两种情况的答案    if(lans>rans)        ans=p,now=lans;//冰系序列较小为答案的情况    else    {        now=rans;        p=0,lsum=0,rsum=0;        for(rg int i=20;i>=0;i--)            if(p+(1<<i)<=cnt &&(lsum+tl[p+(1<<i)]<rcnt-rsum-tr[p+(1<<i)] || min(lsum+tl[p+(1<<i)],rcnt-rsum-tr[p+(1<<i)])==now))            {                p+=(1<<i);                lsum+=tl[p],rsum+=tr[p];            }        ans=p;    }//火系序列较小为答案的情况}int main(){    Q=read();    for(rg int i=1;i<=Q;i++)    {        p(i)=read(),t(i)=read();        if(p(i)==1)            x(i)=read(),y(i)=read(),b[++cnt]=x(i);    }    sort(b+1,b+cnt+1);    cnt=unique(b+1,b+cnt+1)-b-1;//离散化    for(rg int i=1;i<=Q;i++)        if(p(i)==1)        {            rg int x=lower_bound(b+1,b+cnt+1,x(i))-b;            if(!t(i))                changel(x,y(i));            else                changer(x,y(i)),rcnt+=y(i);            query();            if(now)                printf("%d %d\n",b[ans+1],now*2);            else                puts("Peace");        }        else        {            rg int x=lower_bound(b+1,b+cnt+1,x(t(i)))-b;            if(!t(t(i)))                changel(x,-y(t(i)));            else                changer(x,-y(t(i))),rcnt-=y(t(i));            query();            if(now)                printf("%d %d\n",b[ans+1],now*2);            else                puts("Peace");        }    return 0;}