92pts WA #2 求调
查看原帖
92pts WA #2 求调
469388
鳶一折纸楼主2024/9/18 20:26
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 5e4 + 10;
namespace fenwick
{
#define lb(x) ((x) & -x)
    const int F = 2e5 + 10;
    int fw[F];
    void add(int x, int val)
    {
        while (x < F)
            fw[x] = max(fw[x], val), x += lb(x);
    }
    int query(int x, int res = 0)
    {
        while (x)
            res = max(res, fw[x]), x -= lb(x);
        return res;
    }
    void upd(int x)
    {
        while (x < F)
            fw[x] = 0, x += lb(x);
    }
}
using namespace fenwick;
struct node
{
    int a, b, c, d, id, pos;
} e[N];
int n, tot, ans;
int cnt[N << 2], dp[N];
bool cmp(node a, node b)
{
    if (a.a != b.a)
        return a.a < b.a;
    if (a.b != b.b)
        return a.b < b.b;
    if (a.c != b.c)
        return a.c < b.c;
    return a.d < b.d;
}
bool cmp2(node a, node b)
{
    if (a.b != b.b)
        return a.b < b.b;
    if (a.c != b.c)
        return a.c < b.c;
    if (a.d != b.d)
        return a.d < b.d;
    return a.a < b.a;
}
bool cmp3(node a, node b)
{
    if (a.c != b.c)
        return a.c < b.c;
    if (a.d != b.d)
        return a.d < b.d;
    if (a.a != b.a)
        return a.a < b.a;
    return a.b < b.b;
}
void cdq2(int l, int r)
{
    if (l == r)
        return;
    int mid = l + r >> 1;
    cdq2(l, mid);
    sort(e + l, e + mid + 1, cmp3);
    sort(e + mid + 1, e + r + 1, cmp3);
    int j = l;
    for (int i = mid + 1; i <= r; ++i)
    {
        while (j <= mid && e[i].c >= e[j].c)
        {
            if (!e[j].pos)
                add(e[j].d, dp[e[j].id]);
            ++j;
        }
        if (e[i].pos)
            dp[e[i].id] = max(dp[e[i].id], query(e[i].d) + 1ll);
    }
    for (int i = l; i < j; ++i)
        if (!e[i].pos)
            upd(e[i].d);
    sort(e + mid + 1, e + r + 1, cmp2);
    cdq2(mid + 1, r);
}
void cdq1(int l, int r)
{
    if (l == r)
        return;
    int mid = l + r >> 1;
    cdq1(l, mid);
    for (int i = l; i <= mid; ++i)
        e[i].pos = 0;
    for (int i = r; i > mid; --i)
        e[i].pos = 1;
    sort(e + l, e + r + 1, cmp2);
    cdq2(l, r);
    sort(e + l, e + r + 1, cmp);
    cdq1(mid + 1, r);
}
signed main()
{
    ios::sync_with_stdio(0);
    cin >> n;
    for (int i = 1; i <= n; ++i)
    {
        auto &[a, b, c, d, id, pos] = e[i];
        cin >> a >> b >> c >> d, id = i;
        cnt[++tot] = a, cnt[++tot] = b, cnt[++tot] = c, cnt[++tot] = d, pos = 0;
        dp[i] = 1;
    }
    sort(cnt + 1, cnt + 1 + tot);
    tot = unique(cnt + 1, cnt + 1 + tot) - cnt - 1;
    for (int i = 1; i <= n; ++i)
    {
        auto &[a, b, c, d, id, pos] = e[i];
        a = lower_bound(cnt + 1, cnt + 1 + tot, a) - cnt;
        b = lower_bound(cnt + 1, cnt + 1 + tot, b) - cnt;
        c = lower_bound(cnt + 1, cnt + 1 + tot, c) - cnt;
        d = lower_bound(cnt + 1, cnt + 1 + tot, d) - cnt;
    }
    sort(e + 1, e + 1 + n, cmp);
    cdq1(1, n);
    for (int i = 1; i <= n; ++i)
        ans = max(ans, dp[i]);
    cout << ans << endl;
    return 0;
}
2024/9/18 20:26
加载中...