題目

點這里看題目。

分析

設\(F(T)\)為溫度為\(T\)的時候火系戰士能量和,\(I(T)\)為\(T\)時冰系戰士能量和。

顯然我們需要求:

\[\max\{\min\{F(T),I(T)\}\}\]

另一個顯然的事情是,\(F(T)\)是一個后綴和,\(I(T)\)是一個前綴和;因而\(F(T)\)單減,\(I(T)\)單增。

那么\(\min\{F(T),I(T)\}\)就應該是一個有最高平臺的函數。

更進一步的,設\(T_1=\max\{T|I(T)\le F(T)\},T_2=\min\{T|F(T)<I(T)\}\),那么我們可以知道,峰值要么是\(I(T_1)\),要么是\(F(T_2)\)。

首先我們可以離散化后,用樹狀數組維護一下\(I\)的前綴和和\(F\)的前綴差和。計算\(F\)的時候,我們用能量和減掉范圍外的。

尋找\(T_1\),我們可以直接在樹狀數組上面二分。具體來說,我們實際上枚舉步長來進行倍增,并利用樹狀數組得到當前的前綴信息。

尋找\(F(T_2)\),我們可以直接找出\(T_1\)的后繼\(T_2'\),那么\(F(T_2)=F(T_2')\)。不過,有可能\(T_2'<T_2\),我們需要在樹狀數組上面把\(F(T_2')\)的值代入,二分找出\(T_2\)。

所以總共應該有兩個二分,一個尋找\(T_1\),一個尋找\(T_2\)。

時間復雜度是\(O(n\log_2n)\),非常非?？?需要卡?；蛘?O2 。

代碼

#include <cmath>#include <cstdio>#include <algorithm>const int MAXN = 2e6 + 5;template<typename _T>void read( _T &x ){x = 0;char s = getchar();int f = 1;while( s > '9' || s < '0' ){if( s == '-' ) f = -1; s = getchar();}while( s >= '0' && s <= '9' ){x = ( x << 3 ) + ( x << 1 ) + ( s - '0' ), s = getchar();}x *= f;}template<typename _T>void write( _T x ){if( x < 0 ){ putchar( '-' ); x = ( ~ x ) + 1; }if( 9 < x ){ write( x / 10 ); }putchar( x % 10 + '0' );}struct oper{int type, id, x, y;}op[MAXN];int F[MAXN], I[MAXN];int temp[MAXN];int typ[MAXN], T[MAXN], E[MAXN];int Q, N, lg2, all;void up( int &x ) { x += x & ( -x ); }void down( int &x ) { x &= ( x - 1 ); }void uptF( int x, const int v ) { for( ; x <= N ; up( x ) ) F[x] += v; }void uptI( int x, const int v ) { for( ; x <= N ; up( x ) ) I[x] += v; }int getF( int x ) { int ret = 0; for( ; x ; down( x ) ) ret += F[x]; return ret; }int getI( int x ) { int ret = 0; for( ; x ; down( x ) ) ret += I[x]; return ret; }int find1(){int p = 0, ice = 0, fire = 0, tmp;for( int s = 1 << lg2 ; s ; s >>= 1 ){tmp = p + s;if( tmp > N ) continue;ice += I[tmp];fire += F[tmp];if( ice <= all - fire ) p = tmp;else ice -= I[tmp], fire -= F[tmp];}return p;}int find2( const int tar ){int p = 0, fire = 0, tmp;for( int s = 1 << lg2 ; s ; s >>= 1 ){tmp = p + s;if( tmp > N ) continue;fire += F[tmp];if( all - fire >= tar ) p = tmp;else fire -= F[tmp];}return p;}int main(){read( Q );for( int i = 1 ; i <= Q ; i ++ ){read( op[i].type ), read( op[i].id );if( op[i].type == 1 ) read( op[i].x ), read( op[i].y ), temp[++ N] = op[i].x;}std :: sort( temp + 1, temp + 1 + N );N = std :: unique( temp + 1, temp + 1 + N ) - temp - 1;lg2 = log2( N ); int pos, p1, e1, p2, e2;for( int i = 1 ; i <= Q ; i ++ ){if( op[i].type == 1 ){pos = std :: lower_bound( temp + 1, temp + 1 + N, op[i].x ) - temp;if( op[i].id ) all += op[i].y, uptF( pos + 1, op[i].y );else uptI( pos, op[i].y );typ[i] = op[i].id, T[i] = pos, E[i] = op[i].y;}else{pos = op[i].id;if( typ[pos] ) all -= op[pos].y, uptF( T[pos] + 1, -E[pos] );else uptI( T[pos], - E[pos] );}p1 = find1(), e1 = getI( p1 );p2 = p1 == N ? N : p1 + 1, e2 = all - getF( p2 );if( e1 == 0 && e2 == 0 ) { puts( "Peace" ); continue; }if( e1 > e2 ) write( temp[p1] ), putchar( ' ' ), write( e1 * 2ll ), putchar( '\n' );else write( temp[find2( e2 )] ), putchar( ' ' ), write( e2 * 2ll ), putchar( '\n' );}return 0;}