如题，最后一个点 TLE。

本人写了一个线段树，维护区间最大最小值，毕竟蒟蒻想不出怎么维护被覆盖的区间长度，只能这样变相地统计了。

用了动态开点，于是放心大胆地没有用离散化

然后放心大胆地喜提了 TLE

#include <bits/extc++.h>

#define inline __always_inline

inline void read(int &x)
{
	char ch;
	for (ch = getchar(); !isdigit(ch); ch = getchar());
	for (x = 0; isdigit(ch); ch = getchar())	x = x * 10 + ch - '0';
}

inline void read(int64_t &x)
{
	char ch;
	for (ch = getchar(); !isdigit(ch); ch = getchar());
	for (x = 0; isdigit(ch); ch = getchar())	x = x * 10 + ch - '0';
}

class segment_tree_t
{
public:
	struct segment_t
	{
		int64_t l, r;
		inline int64_t size() const { return r - l; }
		inline int64_t mid() const { return l + r >> 1; }
		inline segment_t left() const { return {l, mid()}; }
		inline segment_t right() const { return {mid(), r}; }
		inline bool in(const segment_t &s) const { return s.l <= l && r <= s.r; }
		inline bool out(const segment_t &s) const { return s.r <= l || r <= s.l; }
	};
	struct node_t
	{
		node_t *left, *right;
		segment_t s;
		int64_t value_max, value_min, mark;
		inline int64_t max() const { return value_max + mark; };
		inline int64_t min() const { return value_min + mark; };
	};
	node_t *stack, *nil, *root, *top;
	segment_tree_t(segment_t s, int size = 0x100000)
	{
		nil = stack = (node_t *)calloc(size, sizeof(node_t));
		*nil = {nil, nil};
		root = top = stack + 1;
		*root = {nil, nil, s};
		top++;
	}
	~segment_tree_t() { free(stack); }
	inline void check(node_t *it)
	{
		if (it->left == nil)
		{
			it->left = top++;
			*it->left = {nil, nil, it->s.left()};
		}
		if (it->right == nil)
		{
			it->right = top++;
			*it->right = {nil, nil, it->s.right()};
		}
	}
	inline void push_down(node_t *it)
	{
		it->left->mark += it->mark;
		it->right->mark += it->mark;
		it->mark = 0;
	}
	inline void push_up(node_t *it)
	{
		it->value_max = std::max(it->left->max(), it->right->max());
		it->value_min = std::min(it->left->min(), it->right->min());
	}
	void add(node_t *it, segment_t s, int value)
	{
		if (it->s.out(s))
			return;
		if (it->s.in(s))
			it->mark += value;
		else
		{
			check(it);
			push_down(it);
			add(it->left, s, value);
			add(it->right, s, value);
			push_up(it);
		}
	}
	int64_t query(node_t *it, segment_t s)
	{
		if (it->s.out(s))
			return 0;
		if (it->s.in(s))
		{
			check(it);
			push_down(it);
			push_up(it);
			if (it->max() == 0)
				return 0;
			if (it->min() != 0)
				return it->s.size();
			return query(it->left, s) + query(it->right, s);
		}
		else
		{
			check(it);
			push_down(it);
			push_up(it);
			if (it->max() == 0)
				return 0;
			// if (it->min() == 0)		// can be optimized
				// return it->s.size();
			return query(it->left, s) + query(it->right, s);
		}
	}
};
int n;

struct query_t
{
	segment_tree_t::segment_t s;
	int64_t y;
	bool op;
	inline bool operator<(const query_t q) const
	{
		return y < q.y;
	}
};

query_t query[200000];
#define LIMIT	1000000000
segment_tree_t tree({0, LIMIT}, 10000000);

int main()
{
	freopen64("P5490_11.in", "r", stdin);
	read(n);
	int64_t a, b, c, d;
	for (int i = 0; i < n; i++)
	{
		read(a), read(b), read(c), read(d);
		query[i << 1] = {{std::min(a, c), std::max(a, c)}, b, 0};
		query[i << 1 | 1] = {{std::min(a, c), std::max(a, c)}, d, 1};
	}
	std::sort(query, query + (n << 1));
	uint64_t ans = 0;
	uint64_t prev = query[0].y;
	for (int i = 0; i < n << 1; i++)
	{
		ans += tree.query(tree.root, {0, LIMIT}) * (query[i].y - prev);
		prev = query[i].y;
		if (query[i].op)
			tree.add(tree.root, query[i].s, -1);
		else
			tree.add(tree.root, query[i].s, 1);
	}
	printf("%lu", ans);
	return 0;
}

但我认为这样做应当是可行的，倒数第二个点（500ms）并没有比其他人慢多少（200ms），无非是常数的问题，但最后一个点在本地 1h+ 让我非常震惊。

求大佬能否提示如何优化，或者指出程序中的错误，抑或是分析我的时间复杂度，证明我在最坏情况下时间复杂度会退化至 $o(n \log n)$。

个人盲猜是细节的地方多递归了几次，毕竟就算是暴力的 $O(n^2)$ 也不至于跑 1h