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

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 LOCALfreopen("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;	
}