LOJ3299 【2020联合省选】冰火战士

Description

有两组二元组，((a_i,b_i),(c_i,d_i)) 每次添加或者删除两组中的一个

求一个 (e) 使得

[min(sum_{b_ile e} a_i,sum_{d_ige e} c_i) ]

最大

如果对于任意一个 (e) 都不能满足 (min) 中的俩值不为 (0)，输出 (Peace)

(T le 10^6)

Solution

首先观察题目，发现是个 (X) 型函数求 (min) 最值问题

然后本质上就转化成了找一个函数的峰

我们可以考虑将两个函数作差之后在线段树上二分做，但是发现这东西常数是很大的

（啊这里要离散化，然后仍到一个线段树上面就能做了）

最后是卡常神器：(BIT+) 倍增

考虑到我们只是维护前缀和这样的形式，所以我们可以考虑维护一个前缀和的树状数组，然后在上面倍增找到 (min) 函数的最值

这种手段常用于维护一个前缀和然后求满足某条件的 (lower / upper bound)

Code

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define For(i, a, b) for (register int i = a; i <= b; ++i)
#define reg register
#define Down(i, a, b) for (register int i = a; i >= b; --i)
namespace yspm {
inline int read() {
    int res = 0, f = 1;
    char k;
    while (!isdigit(k = getchar()))
        if (k == '-')
            f = -1;
    while (isdigit(k)) res = res * 10 + k - '0', k = getchar();
    return res * f;
}
const int N = 2e6 + 10;
struct opt {
    int typ, x, y, z;
} a[N];
int b[N<<1], m, T;
struct BIT {
    int c[N << 1];
    inline int lowbit(int x) { return x & (-x); }
    inline void add(int x, int d) {
        for (; x <= m; x += lowbit(x)) c[x] += d;
        return ;
    }
    inline int calc(int x) {
        int res = 0;
        for (; x; x -= lowbit(x)) res += c[x];
        return res;
    }
} T0, T1;
inline int calc1() {
    reg int now = 0, ans = 0;
    Down(i, 22, 0) 
		if (ans + (1 << i) > m) continue;
	    else if (now + T0.c[ans + (1 << i)] - T1.c[ans + (1 << i)] < 0) 
			ans += 1 << i,now += T0.c[ans] - T1.c[ans];
    return ans;
}
inline int calc2(int x) {
    reg int now = 0, ans = 0;
    Down(i, 22, 0) 
		if (ans + (1 << i) > m) continue;
    	else if (now + T1.c[ans + (1 << i)] >= x) 
			ans += (1 << i), now += T1.c[ans];
    return ans;
}
signed main() {
	//freopen("1.in","r",stdin); 
    T = read();
    int id;
    For(i, 1, T) {
        a[i].typ = read();
        if (a[i].typ - 1)
            a[i] = a[read()], a[i].typ = 2;
        else
            a[i].x = read(), a[i].y = read(), a[i].z = read();
        b[++m] = a[i].y;
        b[++m] = a[i].y + 1;
    }
    sort(b + 1, b + m + 1);
    m = unique(b + 1, b + m + 1) - b - 1;
    For(i, 1, T) a[i].y = lower_bound(b + 1, b + m + 1, a[i].y) - b;
	For(i, 1, T) {
        if (a[i].x == 0)
            T0.add(a[i].y, a[i].typ == 1 ? a[i].z : -a[i].z);
        else
        {
        	T1.add(1, a[i].typ == 1 ? a[i].z : -a[i].z);
			T1.add(a[i].y + 1, a[i].typ == 1 ? -a[i].z : a[i].z);
		}
        int r1 = calc1(), ans1 = T0.calc(r1), ans2 = 0;
        if (r1 + 1 <= m)
            ans2 = T1.calc(r1 + 1);
        if (ans1==0 && ans2==0)
            puts("Peace");
        else if (ans2 >= ans1)
            printf("%lld %lld
", b[calc2(ans2)], ans2 << 1);
        else
            printf("%lld %lld
", b[r1], ans1 << 1);
    }
    return 0;
}
}  // namespace yspm
signed main() { return yspm::main(); }