P6619

发表于 分类于
[省选联考 2020 A/B 卷] 冰火战士

[省选联考 2020 A/B 卷] 冰火战士

应该是没有办法直接用线段树维护这类最大值最小的信息的。。。

所以该二分还是要二分。

注意到这个冰系战士的能量都是后缀的形式，火系的能量都是前缀的形式。

意味着冰系总能量随温度增加而增加，火系总能量随温度增加而降低。

很显然这个最佳温度大概就在这两个函数的交点。

我们可以通过能量差的正负来进行二分。

这里采用树状数组上二分的技巧，类似倍增，实际上也就是倍增。。。

然后我们找到温度 $p$ 是能量差为非正的最大值，显然 $p+1$ 也有可能是答案。

于是我们比较 $p$ 和 $p+1$ 处哪个更优，如果 $p$ 更优，不用想就可以直接输出了；反之比较麻烦，因为 $p+1$ 不一定是最大的最佳温度，所以我们要再次二分找到这个最大的最佳温度。

找到这个最大的最佳温度的二分可以通过火系的能量来判断，我们要找的就是火系总能量不低于我们现有答案，并且温度最高的温度。

找到后输出就完了。

时间复杂度 $O(n\log n)$。

虽然我严重怀疑只要卡卡常数 $O(n\log^2 n)$ 也可以搞过去。。。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
#include<iostream>
#include<cstdio>
#include<algorithm>
#define ll long long
using namespace std;
namespace Ehnaev{
  inline ll read() {
    ll ret=0,f=1;char ch=getchar();
    while(ch<48||ch>57) {if(ch==45) f=-f;ch=getchar();}
    while(ch>=48&&ch<=57) {ret=(ret<<3)+(ret<<1)+ch-48;ch=getchar();}
    return ret*f;
  }
  inline void write(ll x) {
    static char buf[22];static ll len=-1;
    if(x>=0) {do{buf[++len]=x%10+48;x/=10;}while(x);}
    else {putchar(45);do{buf[++len]=-(x%10)+48;x/=10;}while(x);}
    while(len>=0) putchar(buf[len--]);
  }
}using Ehnaev::read;using Ehnaev::write;
inline void writes(ll x) {write(x);putchar(32);}
inline void writeln(ll x) {write(x);putchar(10);}

const ll N=2e6;

ll n,amt;
ll uq[N+5],c0[N+5],c1[N+5];

struct Qry{ll op,t,x,y;}q[N+5];

inline void Add0(ll x,ll y) {for(;x<=amt;x+=x&-x) c0[x]+=y;}
inline ll Ask0(ll x) {ll r=0;for(;x;x-=x&-x) r+=c0[x];return r;}
inline void Add1(ll x,ll y) {for(;x<=amt;x+=x&-x) c1[x]+=y;}
inline ll Ask1(ll x) {ll r=0;for(;x;x-=x&-x) r+=c1[x];return r;}

int main() {

  n=read();
  for(ll i=1;i<=n;i++) {
    q[i].op=read();
    if(q[i].op==1) {
      q[i].t=read();q[i].x=read();q[i].y=read();uq[++amt]=q[i].x;
    }
    else {q[i].t=read();}
  }
  sort(uq+1,uq+amt+1);amt=unique(uq+1,uq+amt+1)-uq;uq[amt]=uq[amt-1]+1;

  for(ll i=1;i<=n;i++) {
    if(q[i].op==1) {q[i].x=lower_bound(uq+1,uq+amt+1,q[i].x)-uq;}
  }

  for(ll i=1;i<=n;i++) {
    if(q[i].op==1) {
      if(q[i].t==0) {Add0(q[i].x,q[i].y);Add0(amt,-q[i].y);}
      else {Add1(q[i].x+1,-q[i].y);Add1(1,q[i].y);}
    }
    else {
      if(q[q[i].t].t==0) {
        Add0(q[q[i].t].x,-q[q[i].t].y);
        Add0(amt,q[q[i].t].y);
      }
      else {Add1(q[q[i].t].x+1,q[q[i].t].y);Add1(1,-q[q[i].t].y);}
    }
    ll p=0,s0=0,s1=0;
    for(ll i=20;i>=0;i--) {
      ll tmp=p+(1ll<<i);if(tmp>amt) continue;
      ll delta=s0-s1+c0[tmp]-c1[tmp];
      if(delta<0) {p=tmp;s0+=c0[tmp];s1+=c1[tmp];}
    }
    ll w1=min(Ask0(p),Ask1(p)),w2=min(Ask0(p+1),Ask1(p+1));
    if(w1<=0&&w2<=0) {printf("Peace\n");continue;}
    if(w1>w2) {writes(uq[p]);writeln(w1*2);continue;}
    p=0;s1=0;
    for(ll i=20;i>=0;i--) {
      ll tmp=p+(1ll<<i);if(tmp>amt) continue;
      if(s1+c1[tmp]>=w2) {p=tmp;s1+=c1[tmp];}
    }
    writes(uq[p]);writeln(w2*2);
  }

  return 0;
}