WA#9找不出bug求调

#include <iostream>
#include <math.h>
#include <map>
#include <algorithm>
using namespace std;
typedef unsigned long long ull;
const int N = 100001;
const ull INF = 1000000000;
int dp[N];
map<ull, ull>shadow;
map<ull, int>ans;
int n, p;
struct pt {
	int x, y;
	friend bool operator !=(const pt&a, const pt&b) {
		if (a.x == b.x && a.y == b.y)return false;
		return true;
	}
} all[N * 2 + 50], now[N * 2 + 50];
int cnt = 0;
struct node {
	int rnd, x, y, num, minn;
	node *ch[2];
	void init(int xin, int yin) {
		x = xin, y = yin;
		num = minn = 0;
		rnd = rand();
		ch[0] = ch[1] = nullptr;
	}
	void upd() {
		minn = num;
		if (ch[0] != nullptr) {
			minn = min(ch[0]->minn, minn);
		}
		if (ch[1] != nullptr) {
			minn = min(ch[1]->minn, minn);
		}
	}
}*root;

bool cm_p(pt a, pt b) {
	if (a.x == b.x)return a.y < b.y;
	return a.x < b.x;
}
typedef pair<node*, node *> pr;
pr split(node *cur, int val) {
	if (cur == nullptr)return {nullptr, nullptr};
	if (cur->y <= val) {
		auto ntr = split(cur->ch[1], val);
		cur->ch[1] = ntr.first;
		cur->upd();
		return {cur, ntr.second};
	} else {
		auto ntr = split(cur->ch[0], val);
		cur->ch[0] = ntr.second;
		cur->upd();
		return {ntr.first, cur};
	}
}

node *merge(node *cur1, node *cur2) {
	if (cur1 == nullptr || cur2 == nullptr) {
		if (cur1 == nullptr)return cur2;
		return cur1;
	}
	if (cur1->rnd <= cur2->rnd) {
		cur1->ch[1] = merge(cur1->ch[1], cur2);
		cur1->upd();
		return cur1;
	} else {
		cur2->ch[0] = merge(cur1, cur2->ch[0]);
		cur2->upd();
		return cur2;
	}
}


void insert(int x, int y) {
	int val = 0;
	ull toval = x * INF * 10ull + y;
	if (shadow.find(toval) != shadow.end())
		if (ans.find(shadow[toval]) != ans.end()) {
			ull tmp = shadow[toval];
			int xt = shadow[toval] / 10ull / INF, yt = shadow[toval] % (10ull * INF);
			val = ans[shadow[x * INF * 10 + y]] - x - y + xt + yt;
		}
	auto ntr1 = split(root, y);
	if (ntr1.first != nullptr)
		val = min(val, ntr1.first->minn);
	auto ntr2 = split(ntr1.first, y - 1);
	node*cur = new node;
	cur->init(x, y);
	cur->num = ans[toval] = val;
	ntr2.second = merge(ntr2.second, cur);
	auto ntr = merge(ntr2.first, ntr2.second);
	root = merge(ntr, ntr1.second);
}

int main() {
	ios::sync_with_stdio(0);
	cin >> n >> p;
	for (int i = 1; i <= p * 2; i += 2) {
		cin >> all[i].x >> all[i].y >> all[i + 1].x >> all[i + 1].y;
		ull t1 = all[i + 1].x * INF * 10ull + all[i + 1].y, t2 = all[i].x * INF * 10ull + all[i].y;
		shadow[t1] = t2;
	}
	all[p * 2 + 1].x = 0, all[p * 2 + 1].y = 0, all[p * 2 + 2].x = n, all[p * 2 + 2].y = n;
	sort(all + 1, all + 1 * 2 * p + 2, cm_p);
	for (int i = 1; i <= 2 * p + 2; i++) {
		if (all[i] != all[i + 1] ) {
			now[++now[0].x] = all[i];
		}
	}
	for (int i = 1; i <= now[0].x; i++) {
		insert(now[i].x, now[i].y);
//		cout << now[i].x << " " << now[i].y << " " << ans[now[i].x * 10ull * INF + now[i].y] << "\n";
	}
	cout << ans[n * INF * 10 + n] + n + n << "\n";
	return 0;
}