Catshao

用户名：Catshao

访问量：28830

签　名：

stO KHIN Orz

等　　级
排　　名	161
经　　验	7130
参赛次数	6
文章发表	46
年　　龄	12
在职情况	学生
学　　校	双语
专　　业

　　自我简介：

TA的其他文章

蓝桥杯2020年第十一届省赛真题-整数小拼接
浏览：1472

蓝桥杯2020年第十一届省赛真题-BST插入节点问题
浏览：547

蓝桥杯2020年第十一届省赛真题-八次求和
浏览：556

你可能喜欢

2005年春浙江省计算机等级考试二级C 编程题(3) （C语言代码）

四维偏序：CDQ解法

　　作者: Catshao　　　　发表时间：2022-02-23 13:43:11 浏览：55　|　评论：0　

原题链接：四维偏序

CDQ 跟八叉树一样都是 $$O(n \log^3 n)$$ 的。CDQ 内尽可能用归并排序，常数较小，在某 OJ 跑到了第三优解（八叉树是第五优），可惜 dotcpp 上 CDQ 跑不过八叉树。

既然优质题解已经没了我就不讲了，各位看看乐呵就好。

```cpp
//
// Created by Cat-shao on 2022/2/23.
//

#include <bits/stdc++.h>
using namespace std;

const int MAX_N = 5e4 + 5;
typedef tuple<int, int, int, int, int, int> TII;

int n, hw[MAX_N], kw, ka;
long long dp[MAX_N];
TII a[MAX_N], b[MAX_N], temp[MAX_N];

bool cmp1(TII &x, TII &y) {
    return get<1>(x) < get<1>(y) || (get<1>(x) == get<1>(y) && (get<2>(x) < get<2>(y) || (get<2>(x) == get<2>(y) && (get<3>(x) < get<3>(y) || (get<3>(x) == get<3>(y) && get<0>(x) < get<0>(y))))));
}

inline int lowbit(int x) {
    return x & -x;
}

class BIT {
public:
    long long node[MAX_N];
    int n;

BIT(int _n) {
        memset(node, 0, sizeof(node));
        n = _n;
    }

long long query(int index) {
        long long res = 0;
        while (index > 0) {
            res = max(res, node[index]);
            index -= lowbit(index);
        }
        return res;
    }

void add(int index, long long value) {
        while (index <= n) {
            node[index] = max(node[index], value);
            index += lowbit(index);
        }
    }

void clear(int index) {
        while (index <= n) {
            node[index] = 0;
            index += lowbit(index);
        }
    }
};

void solve2(int l, int r) { // 三维偏序作为子问题，不需要考虑 dp 的前后关系
    if (l + 1 >= r) {
        return;
    }
    int mid = (l + r) >> 1, i, j ,k;
    solve2(l, mid);
    solve2(mid, r);
    static BIT tree(kw);
    for (i = l, j = mid; j < r; ++j) {
        while (i < mid && get<2>(b[i]) <= get<2>(b[j])) {
            if (get<0>(b[i]) == 0) {
                tree.add(get<3>(b[i]), dp[get<5>(b[i])]);
            }
            i++;
        }
        if (get<0>(b[j])) {
            dp[get<5>(b[j])] = max(dp[get<5>(b[j])], tree.query(get<3>(b[j])) + get<4>(b[j]));
        }
    }
    while (--i >= l) {
        tree.clear(get<3>(b[i]));
    }
    for (i = l, j = mid, k = l; i < mid || j < r; temp[k++] = i >= mid ? b[j++] : (j >= r ? b[i++] : (get<2>(b[i]) <= get<2>(b[j]) ? b[i++] : b[j++])));
    memcpy(b + l, temp + l, (r - l) * sizeof(TII));
}

void solve1(int l, int r) {
    if (l + 1 >= r) {
        return;
    }
    int mid = (l + r) >> 1;
    solve1(l, mid);
    memcpy(b + l, a + l, (r - l) * sizeof(TII)); // 未定义行为，可能会引发错误
    for (int i = l; i < mid; ++i) {
        get<0>(b[i]) = 0;
    }
    for (int i = mid; i < r; ++i) {
        get<0>(b[i]) = 1;
    }
    sort(b + l, b + r, cmp1);
    solve2(l, r);
    solve1(mid, r);
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        cin >> get<0>(a[i]) >> get<1>(a[i]) >> get<2>(a[i]) >> get<3>(a[i]) >> get<4>(a[i]);
        hw[i] = get<3>(a[i]);
    }
    sort(hw + 1, hw + n + 1);
    kw = unique(hw + 1, hw + n + 1) - (hw + 1);
    for_each(a + 1, a + n + 1, [&](TII &x) { get<3>(x) = lower_bound(hw + 1, hw + kw + 1, get<3>(x)) - hw; });
    sort(a + 1, a + n + 1);
    ka = 1;
    for (int i = 2; i <= n; ++i) {
        if (get<0>(a[i - 1]) != get<0>(a[i]) || get<1>(a[i - 1]) != get<1>(a[i]) || get<2>(a[i - 1]) != get<2>(a[i]) || get<3>(a[i - 1]) != get<3>(a[i])) {
            a[++ka] = a[i];
        } else {
            get<4>(a[ka]) += get<4>(a[i]);
        }
    }
    for (int i = 1; i <= ka; ++i) {
        get<5>(a[i]) = i;
    }
    for (int i = 1; i <= ka; ++i) {
        dp[i] = get<4>(a[i]);
    }
    solve1(1, ka + 1);
    cout << *max_element(dp + 1, dp + n + 1) << endl;
    return 0;
}
```

0.0分

0 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

Catshao

TA的其他文章

你可能喜欢

2005年春浙江省计算机等级考试二级C 编程题(3) （C语言代码）

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

C二级辅导-同因查找（C语言代码）

剔除相关数（C语言代码）

C语言训练-自守数问题（C语言代码） long long

四维偏序：CDQ解法

评论区

精彩推荐

C语言训练-求s=a+aa+aaa+aaaa+aa...a的值（C语言代码）

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

C二级辅导-计负均正（C语言代码）

九宫重排（C++代码）

小明A+B （C语言代码）

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

【蟠桃记】（C语言代码）

K-进制数（C语言描述，蓝桥杯）

1013题解

1050题解（结构体数组与结构体指针的使用）

Catshao

TA的其他文章

你可能喜欢

2005年春浙江省计算机等级考试二级C 编程题(3) （C语言代码）

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

C二级辅导-同因查找 （C语言代码）

剔除相关数 （C语言代码）

C语言训练-自守数问题 （C语言代码） long long

四维偏序：CDQ解法

评论区

精彩推荐

C语言训练-求s=a+aa+aaa+aaaa+aa...a的值 （C语言代码）

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

C二级辅导-计负均正 （C语言代码）

九宫重排 （C++代码）

小明A+B （C语言代码）

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

【蟠桃记】 （C语言代码）

K-进制数 （C语言描述，蓝桥杯）

1013题解

1050题解（结构体数组与结构体指针的使用）

C二级辅导-同因查找（C语言代码）

剔除相关数（C语言代码）

C语言训练-自守数问题（C语言代码） long long

　　评论区

C语言训练-求s=a+aa+aaa+aaaa+aa...a的值（C语言代码）

C二级辅导-计负均正（C语言代码）

九宫重排（C++代码）

【蟠桃记】（C语言代码）

K-进制数（C语言描述，蓝桥杯）