[統一省選2020]冰火戰士

題意分析

對于每次修改后的情況,求一個最大的 $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;}