萌新 cdq 分治求调
查看原帖
萌新 cdq 分治求调
503792
Svemit楼主2024/11/1 16:04

rt

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 5e4 + 5;

int n;
vector<int> ds;

int c[N];

void add(int x, int v) {
	for (; x <= n; x += x & -x) c[x] = max(c[x], v);
}

void del(int x) {
	for (; x <= n; x += x & -x) c[x] = 0;
}

int query(int x) {
	int res = 0;
	for (; x; x -= x & -x) res = max(res, c[x]);
	return res;
}

struct node {
	int a, b, c, d, w, ans, op;
	bool operator == (const node &t) const {
		return a == t.a && b == t.b && c == t.c && d == t.d;
	}
} p[N];

bool cmpa(node x, node y) {
	if (x.a != y.a) return x.a < y.a;
	else if (x.b != y.b) return x.b < y.b;
	else if (x.c != y.c) return x.c < y.c;	
	else return x.d < y.d;
}

bool cmpb(node x, node y) {
	if (x.b != y.b) return x.b < y.b;
	else if (x.a != y.a) return x.a < y.a;
	else if (x.c != y.c) return x.c < y.c;	
	else return x.d < y.d;
}

bool cmpc(node x, node y) {
	if (x.c != y.c) return x.c < y.c;
	else if (x.b != y.b) return x.b < y.b;
	else if (x.a != y.a) return x.a < y.a;	
	else return x.d < y.d;
}

void cdq2(int l, int r) {
	if (l == r) return;
	int mid = (l + r) / 2;
	cdq2(l, mid), cdq2(mid + 1, r);
	sort(p + l, p + mid + 1, cmpc);
	sort(p + mid + 1, p + r + 1, cmpc);
	int i = l, j = mid + 1;
	while (i <= mid && j <= r) {
		if (p[i].c <= p[j].c) {
			if (p[i].op == 0) add(p[i].d, p[i].ans);
			i ++;
		} else {
			if (p[j].op == 1) p[j].ans = max(p[j].ans, query(p[j].d) + p[j].w);
			j ++;
		}
	}
	while (i <= mid) {
		if (p[i].op == 0) add(p[i].d, p[i].ans);
		i ++;
	}
	while (j <= r) {
		if (p[j].op == 1) p[j].ans = max(p[j].ans, query(p[j].d) + p[j].w);
		j ++;
	}
	for (i = l; i <= mid; i ++) {
		del(p[i].d);
	}
}

void cdq1(int l, int r) {
	if (l == r) return;
	int mid = (l + r) / 2;
	cdq1(l, mid), cdq2(mid + 1, r);
	for (int i = l; i <= r; i ++) p[i].op = (i > mid);
	sort(p + l, p + r + 1, cmpb);
	cdq2(l, r);
}


int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    cin >> n;
    for (int i = 1; i <= n; i ++) {
    	cin >> p[i].a >> p[i].b >> p[i].c >> p[i].d;
    	ds.push_back(p[i].d);
    	p[i].w = 1;
    }
    sort(p + 1, p + 1 + n, cmpa);
    int m = 0;
    for (int i = 1; i <= n; i ++) {
    	if (p[i] == p[m]) p[m].w ++;
    	else p[++ m] = p[i];
    }
    sort(ds.begin(), ds.end());
    ds.erase(unique(ds.begin(), ds.end()), ds.end());
    for (int i = 1; i <= m; i ++) {
    	p[i].ans = p[i].w;
    	p[i].d = lower_bound(ds.begin(), ds.end(), p[i].d) - ds.begin() + 1;
    }

    cdq1(1, m);
    int ans = 0;
    for (int i = 1; i <= m; i ++) ans = max(ans, p[i].ans);

    cout << ans << "\n";


    return 0;
}
2024/11/1 16:04
加载中...