30pts求条
查看原帖
30pts求条
1046406
Unpt_V3楼主2025/1/21 19:26
#include <bits/stdc++.h>

using namespace std;

#define int long long

const int N = 4e5 + 5000;
int n, m, f[N], ans, tot2, li[N];

struct node {
	int idx, v, mnv, mxv;
} a[N];

struct BIT {
	int a[4 * N + 50];
	
	int _lb(int x) {
		return x & (-x);
	}
	
	void add(int p, int v) {
		for (int i = p; i <= 4 * N; i += _lb(i))
			this->a[i] = max(a[i], v);
	}
	
	void clear(int p) {
		for (int i = p; i <= 4 * N; i += _lb(i))
			this->a[i] = 0;
	}
	
	int query(int p) {
		int res = 0;
		for (int i = p; i; i -= _lb(i))
			res = max(res, this->a[i]);
		return res;
	}
} t;

bool cmp1(const node &a, const node &b) {
	return a.idx < b.idx;
}

bool cmp2(const node &a, const node &b) {
	return a.v < b.v;
}

bool cmp3(const node &a, const node &b) {
	return a.mxv < b.mxv;
}

void cdq(int l, int r) {
	if (l == r) {
		f[l] = max(f[l], 1LL);
		return;
	}
	int mid = (l + r) / 2;
	cdq(l, mid);
	sort(a + l, a + mid + 1, cmp3);
	sort(a + mid + 1, a + r + 1, cmp2);
	int i = l, j = mid + 1;
	while (j <= r) {
		while (i <= mid && a[i].mxv <= a[j].v) {
			t.add(a[i].v, f[a[i].idx]);
			i++;
		}
		f[a[j].idx] = max(f[a[j].idx], t.query(a[j].mnv) + 1);
		j++;
	}
	for (int u = l; u <= mid; u++)
		t.clear(a[u].v);
	sort(a + l, a + r + 1, cmp1);
	cdq(mid + 1, r);
}

signed main() {
	cin >> n;
	tot2 = 0;
	for (int i = 1; i <= n; i++) {
		int l, s, w, aa;
		cin >> l >> s >> w >> aa;
		a[i].idx = l, a[i].v = aa, a[i].mnv = s, a[i].mxv = w;
		li[++tot2] = l,li[++tot2] = s, li[++tot2] = w, li[++tot2] = aa;
	}
	sort(li + 1, li + tot2 + 1);
	tot2 = unique(li + 1, li + tot2 + 1) - li - 1;
	for (int i = 1; i <= n; i++) {
		a[i].idx = lower_bound (li + 1, li + tot2 + 1, a[i].idx) - li;
		a[i].v = lower_bound(li + 1, li + tot2 + 1, a[i].v) - li;
		a[i].mnv = lower_bound(li + 1, li + tot2 + 1, a[i].mnv) - li;
		a[i].mxv = lower_bound(li + 1, li + tot2 + 1, a[i].mxv) - li;
	}
	sort(a + 1, a + n + 1, cmp1);
	cdq(1, n);
	for (int i = 1; i <= n; i++)
		ans = max(ans, f[i]);
	cout << ans;
	return 0;
}
2025/1/21 19:26
加载中...