总所周知

扫描线中的线段树只需要扩大8倍 但是我这边为什么只有扩大16倍才可以过

这边我左移3就会RE

非常的不解

这是因为我离散化使用map从而导致空间不够

但这钟东西我不到啊

注：本代码只需要把sgt[N << 3]改为sgt[N << 4] 就可以过了

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <map>
#define ls (p << 1)
#define rs (ls | 1)
using namespace std;

typedef long long ll;
const int N = 1e5 + 10;
struct Line
{
	ll x, y1, y2, k;
} a[N << 1];
struct SGT
{
	ll l, r, cnt, len;
	#define l(x) sgt[x].l
	#define r(x) sgt[x].r
	#define cnt(x) sgt[x].cnt
	#define len(x) sgt[x].len
}sgt[N << 3];//TODO
ll raw[N << 1];
map<ll, ll> val;

bool cmp(Line a, Line b) {return a.x < b.x;}

void build(ll p, ll l, ll r)
{
	l(p) = l; r(p) = r; cnt(p) = 0, len(p) = 0;//TODO
	if (l == r) return;
	ll mid = (l(p) + r(p)) >> 1;
	build(ls, l, mid); build(rs, mid + 1, r);
}

void change(ll p, ll l, ll r, ll k)
{
	if (l <= l(p) && r >= r(p))
	{
		cnt(p) += k;
		if (cnt(p)) len(p) = raw[r(p) + 1] - raw[l(p)];
		else 
		{
			if (l == r) len(p) = 0;
			else len(p) = len(ls) + len(rs);//TODO
		}
		return;//TODO
	}
	ll mid = (l(p) + r(p)) >> 1;
	if (l <= mid) change(ls, l, r, k);
	if (r > mid) change(rs, l, r, k);
	if (cnt(p)) len(p) = raw[r(p) + 1] - raw[l(p)];
	else len(p) = len(ls) + len(rs);
}

signed main()
{
	ll n;
	scanf("%lld", &n);
	for (ll i = 1; i <= n; ++ i)
	{
		ll x1, x2, y1, y2, k = i << 1;
		scanf("%lld %lld %lld %lld", &a[k - 1].x, &y1, &a[k].x, &y2);
		raw[k - 1] = a[k - 1].y1 = a[k].y1 = y1;
		raw[k] = a[k - 1].y2 = a[k].y2 = y2;
		a[k - 1].k = 1; a[k].k = -1;
	}
	n <<= 1;
	sort(raw + 1, raw + n + 1);
	ll m = unique(raw + 1, raw + n + 1) - (raw + 1);
	for (ll i = 1; i <= m; ++ i) val[raw[i]] = i;
	sort(a + 1, a + 1 + n, cmp);
	build(1, 1, m - 1);//TODO
	ll ans = 0;
	for (ll i = 1; i < n; ++ i)
	{
		ll y1 = val[a[i].y1], y2 = val[a[i].y2] - 1;
		change(1, y1, y2, a[i].k);
		ans += len(1) * (a[i + 1].x - a[i].x);
	}
	printf("%lld\n", ans);
	return 0;
}