8.21T1 草莓蛋糕（拆max + 权值线段树）

本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/141403142

http://cplusoj.com/d/senior/p/NODSX2302A

看到式子：

我们就应该想到拆max

若

我们可以整理推出：

记：

由 $L$ 算 $C$ ，我们满足 $h_a\le h_b$ ，找 $c$ 的最小值

$C$ 算 $L$ 同理。

我们直接拿权值线段树实现就行

但是叶子节点有很多信息，怎么维护？

直接multiset即可！

权值线段树要提前离散化一下，就不用动态开点了

#include<bits/stdc++.h>
using namespace std;
#ifdef LOCAL
 #define debug(...) fprintf(stdout, ##__VA_ARGS__)
 #define debag(...) fprintf(stderr, ##__VA_ARGS__)
#else
 #define debug(...) void(0)
 #define debag(...) void(0)
#endif
//#define int unsigned int
inline int read(){int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;
ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+
(x<<3)+(ch^48);ch=getchar();}return x*f;}
#define Z(x) (x)*(x)
#define pb push_back
#define fi first
#define se second
//#define M
//#define mo
#define N 4000010
int n, m, i, j, k, T, len[2];
int ans[N], ls[N], rs[N], mn[N][2][2], tot, tye; 
multiset<int>s1[1000010][2], s2[1000010][2];  
map<int, int>mp; 

void Set(int k) {
	ans[k] = mn[k][0][0] = mn[k][1][0] = mn[k][0][1] = mn[k][1][1] = 2e9; 
}

struct Segment_tree {
	void push_up(int k) {
		long long sss = ans[k]; 
		sss = min(ans[ls[k]], ans[rs[k]]); 
		sss = min(sss, (long long)mn[rs[k]][0][0] + (long long)mn[ls[k]][1][0]); 
		sss = min(sss, (long long)mn[rs[k]][1][1] + (long long)mn[ls[k]][0][1]); 
//		debug("%lld\n", sss); 
		ans[k] = sss; 
		mn[k][0][0] = min(mn[ls[k]][0][0], mn[rs[k]][0][0]); 
		mn[k][0][1] = min(mn[ls[k]][0][1], mn[rs[k]][0][1]); 
		mn[k][1][0] = min(mn[ls[k]][1][0], mn[rs[k]][1][0]); 
		mn[k][1][1] = min(mn[ls[k]][1][1], mn[rs[k]][1][1]); 
	}
	void add(int &k, int l, int r, int o, int h, int x, int y, int d) {
		if(!k) k = ++tot, Set(k); 
		if(l == r) {
			if(!mp[k]) mp[k] = ++tye; int i = mp[k]; ans[k] = 2e9; 
			if(d == 0) s1[i][o].erase(x), s2[i][o].erase(y); 
			else s1[i][o].insert(x), s2[i][o].insert(y); 
			if(!s1[i][o].empty()) mn[k][o][0] = *s1[i][o].begin(); else mn[k][o][0] = 2e9; 
			if(!s2[i][o].empty()) mn[k][o][1] = *s2[i][o].begin(); else mn[k][o][1] = 2e9; 
			if(!s1[i][0].empty() && !s1[i][1].empty()) ans[k] = min(ans[k], *s1[i][0].begin() + *s1[i][1].begin()); 
			if(!s2[i][0].empty() && !s2[i][1].empty()) ans[k] = min(ans[k], *s2[i][0].begin() + *s2[i][1].begin()); 
//			debug("[%d](%d %d)\n", h, mn[k][o][0], mn[k][o][1]); 
//			debug("%d\n", k); 
			return ; 
		}
		int mid = (l + r) >> 1; 
		if(h <= mid) add(ls[k], l, mid, o, h, x, y, d); 
		else add(rs[k], mid + 1, r, o, h, x, y, d); 
//		debug("For %d : ")
		push_up(k); 
	}
}Seg;

int a[N]; 
struct node {
	int o, d, x, y, h; 
}E[N];
//vector<node>E; 

signed main()
{
	#ifdef LOCAL
	  freopen("in.txt", "r", stdin);
	  freopen("out.txt", "w", stdout);
	#endif
//	srand(time(NULL));
//	T=read();
//	while(T--) {
//
//	}
	int q, o, d, x, y, h, rt = 0; 
	q = read(); Set(0); 
	for(i = 1; i <= q; ++i) {
		o = read(); d = read(); x = read(); y = read(); 
		a[i] = h = (d ? y - x : x - y); 
		E[i] = {o, d, x, y, h}; 
	}
	sort(a + 1, a + q + 1); //, [] (node x, node y) { return x.h < y.h; }); 
	for(i = 1; i <= q; ++i) {
		assert(x <= 1e9); 
		assert(y <= 1e9); 
		o = E[i].o; d = E[i].d; x = E[i].x; y = E[i].y; h = E[i].h; 
		h = lower_bound(a + 1, a + q + 1, h) - a; 
		Seg.add(rt, 1, q, d, h, x, y, o); 
		len[d] += (o ? 1 : -1); 
		if(!len[0] || !len[1]) { printf("-1\n"); continue; }
		printf("%d\n", ans[rt]); 
	}
	return 0;	
}