Luogu

LOJ

分析

看完题后可以发现几个结论:

  • 冰人能选的是一段前缀,火人能选的是一段后缀。
  • 总能量为能选的冰人的能量和和能选的火人的能量和中较小的那个的两倍。
  • 总能量是关于温度的单峰函数。
  • 答案一定是某个战士的温度。

因为答案一定是某个战士的温度,所以先把所有温度离散化(下文的温度也指离散化后的温度)。

看到这个单峰可以想到三分温度,但是由于有很多地方的值是相同的所以不太好三分;但是注意到冰人的能量和减火人的能量和(下面称作能量差)是单增的,而最优解一定在 $0$ 左右,于是只要二分这两个位置即可。check 时可以通过树状数组来判断。

这样子是 $\mathcal{O}(Q\log^2 Q)$ 的,显然跑不过 $2\times 10^6$。

因此我们可以想办法把二分+树状数组改成树状数组上二分,这样子就可以做到 $\mathcal{O}(Q\log Q)$ 了。

具体的,我们先二分出最大的能量差 $\leq 0$ 的温度 $T$:设 $sf_i$ 表示温度为 $i$ 的火人的能量和,$I(i)$ 为温度 $\leq i$ 的冰人的能量和,$F(i)$ 为温度 $\leq i$ 的火人的能量和,$sum\_fire$ 为所有火人的能量和,则温度为 $t$ 时能量差为 $I(t)-(sum\_fire-F(t)+sf_t)$,即应满足条件 $I(t)+F(t)-sum\_fire-sf_t\leq 0$,于是就很好在树状数组上二分了。

这样子答案只可能是温度为 $T$ 时或温度为 $T+1$ 时。如果 $ans(T)>ans(T+1)$,则答案为 $ans(T)$,答案温度为 $T$;否则答案为 $ans(T+1)$,但求答案温度我们还需要二分出一个最大的 $T'$ 满足 $ans(T')=ans(T+1)$,同样在树状数组上二分即可。

因为奇妙的数据范围所以可能会有些卡常。

代码

// ====================================
//   author: M_sea
//   website: https://m-sea-blog.com/
// ====================================
#include <bits/stdc++.h>
#define file(x) freopen(#x".in","r",stdin); freopen(#x".out","w",stdout)

using namespace std;
typedef long long ll;

namespace IO {
    const int SIZE=1<<21;
    char ibuf[SIZE|1],*iS,*iT,obuf[SIZE|1],*oS=obuf,*oT=obuf+SIZE-1;
    void flush() { fwrite(obuf,1,oS-obuf,stdout); oS=obuf; }
    char getc() {
        if (iS==iT) {
            iT=(iS=ibuf)+fread(ibuf,1,SIZE,stdin);
            if (iS==iT) return EOF;
        }
        return *iS++;
    }
    void putc(char x) { *oS++=x; if (oS==oT) flush(); }
    int read() {
        int X=0,w=1; char c=getc();
        while (c<'0'||c>'9') { if (c=='-') w=-1; c=getc(); }
        while (c>='0'&&c<='9') X=X*10+c-'0',c=getc();
        return X*w;
    }
    void write(int x) {
        static char sta[40]; int top=0;
        if (!x) putc('0');
        if (x<0) putc('-'),x=-x;
        while (x) sta[++top]=x%10+'0',x/=10;
        while (top) putc(sta[top--]);
    }
    struct flusher { ~flusher() { flush(); } } io_flusher;
}
using IO::getc;
using IO::putc;
using IO::read;
using IO::write;

void Peace() { putc('P'),putc('e'),putc('a'),putc('c'),putc('e'),putc('\n'); }

const int N=2000000+10;

int Q,top=0; pair<int,int> S[N];
int sf[N],cnt_ice=0,cnt_fire=0,sum_fire=0;
struct query { int op,k,x,y; } q[N];

struct BIT {
    int c[N];
    void add(int x,int y) { for (;x<=top;x+=x&-x) c[x]+=y; }
    int sum(int x) { int s=0; for (;x;x-=x&-x) s+=c[x]; return s; }
} I,F;

int calc(int t) {
    if (t<1||t>top) return -1;
    return min(I.sum(t),sum_fire-F.sum(t-1));
}

int main() {
    Q=read();
    for (int i=1;i<=Q;++i) {
        q[i].op=read(),q[i].k=read();
        if (q[i].op==1) q[i].x=read(),q[i].y=read(),S[++top]=make_pair(q[i].x,i);
    }
    sort(S+1,S+top+1);
    for (int i=1,p=1;i<=Q;++i) {
        if (S[i].first!=S[i-1].first) p=i;
        q[S[i].second].x=p;
    }
    for (int i=1;i<=Q;++i) {
        if (q[i].op==1) {
            if (!q[i].k) I.add(q[i].x,q[i].y),++cnt_ice;
            else F.add(q[i].x,q[i].y),++cnt_fire,sum_fire+=q[i].y,sf[q[i].x]+=q[i].y;
        } else {
            int p=q[i].k;
            if (!q[p].k) I.add(q[p].x,-q[p].y),--cnt_ice;
            else F.add(q[p].x,-q[p].y),--cnt_fire,sum_fire-=q[p].y,sf[q[p].x]-=q[p].y;
        }
        if (!cnt_ice||!cnt_fire) { Peace(); continue; }
        int p=0,sum=0;
        for (int j=21;~j;--j) {
            int v=p|1<<j;
            if (v<=top&&sum+I.c[v]+F.c[v]-sf[v]-sum_fire<=0) p=v,sum+=I.c[p]+F.c[p];
        }
        int w1=calc(p),w2=calc(p+1);
        if (w1<=0&&w2<=0) { Peace(); continue; }
        if (w1>w2) { write(S[p].first),putc(' '),write(w1<<1),putc('\n'); continue; }
        p=0,sum=0;
        for (int j=21;~j;--j) {
            int v=p|1<<j;
            if (v<=top&&sum_fire-sum-F.c[v]+sf[v]>=w2) p=v,sum+=F.c[p];
        }
        write(S[p].first),putc(' '),write(w2<<1),putc('\n');
    }
    return 0;
}
最后修改:2020 年 06 月 28 日 10 : 53 AM