首页 > 其他分享 >【CDQ分治】【模板】三维偏序(陌上花开)

【CDQ分治】【模板】三维偏序(陌上花开)

时间:2024-08-06 20:29:27浏览次数:18  
标签:偏序 begin return int auto 陌上 mid CDQ BIT

P3810 【模板】三维偏序(陌上花开) - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

#include <bits/stdc++.h>

using namespace std;

using i64 = long long;

template<typename T>
struct BIT {
#ifndef lowbit
#define lowbit(x) (x & (-x));
#endif
    int n;
    vector<T> t;

    BIT () {}
    BIT (int _n): n(_n) { t.resize(_n + 1); }
    BIT (int _n, vector<T>& a): n(_n) {
        t.resize(_n + 1);
        for (int i = 1; i <= n; ++ i) {
            t[i] += a[i];
            int j = i + lowbit(i);
            if (j <= n) t[j] += t[i];
        }
    }
    //单点修改
    void update(int i, T x) {
        while (i <= n) {
            t[i] += x;
            i += lowbit(i);
        }
    }
    //区间查询
    T sum(int i) {
        T ans = 0;
        while (i > 0) {
            ans += t[i];
            i -= lowbit(i);
        }
        return ans;
    }

    T query(int i, int j) {
        return sum(j) - sum(i - 1);
    }
    //区间修改则存入差分数组,[l, r] + k则update(x,k),update(y+1,-k)
    //单点查询则直接求前缀和sum(x)

    //求逆序对
    /*
    iota(d.begin(), d.end(), 0);
    stable_sort(d.begin(), d.end(), [&](int x, int y) {
        return a[x] < a[y];
    });去重排序

    BIT<i64> tree(n);
    i64 ans = 0;
    for (int i = 1; i <= n; i ++) {
        tree.update(d[i], 1);
        ans += i - tree.sum(d[i]);
    }
    */
};

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

    int n, k;
    cin >> n >> k;

    vector<array<int, 3>> a(n);
    for (auto &[x, y, z] : a)
        cin >> x >> y >> z;

    sort(a.begin(), a.end());

    vector<array<int, 5>> A;
    for (int i = 0; i < n; i ++) {
        int j = i;
        while (j + 1 < n && a[j + 1] == a[j]) {
            j ++;
        }
        A.push_back({a[j][0], a[j][1], a[j][2], j - i + 1, 0});
        i = j;
    }

    BIT<i64> bit(k);
    auto cdq = [&](auto && self, int l, int r)->void{
        if (l == r)
            return ;
        int mid = l + r >> 1;
        self(self, l, mid);
        self(self, mid + 1, r);

        sort(A.begin() + l, A.begin() + mid + 1, [](auto x, auto y) {
            if (x[1] == y[1]) return x[2] < y[2];
            return x[1] < y[1];
        });

        sort(A.begin() + mid + 1, A.begin() + r + 1, [](auto x, auto y) {
            if (x[1] == y[1]) return x[2] < y[2];
            return x[1] < y[1];
        });

        int i = l, j = mid + 1;
        while (j <= r) {
            while (i <= mid && A[i][1] <= A[j][1]) {
                bit.update(A[i][2], A[i][3]);
                i ++;
            }
            A[j][4] += bit.sum(A[j][2]);
            j ++;
        }

        for (int k = l; k < i; k ++)
            bit.update(A[k][2], -A[k][3]);
    };

    cdq(cdq, 0, A.size() - 1);

    vector<i64> f(n + 1);
    for (auto &[a, b, c, cnt, d] : A) {
        f[d + cnt - 1] += cnt;
    }

    for (int i = 0; i < n; i ++)
        cout << f[i] << "\n";

    return 0;
}

标签:偏序,begin,return,int,auto,陌上,mid,CDQ,BIT
From: https://www.cnblogs.com/Kescholar/p/18345928

相关文章

  • 【CDQ分治】[P5094 [USACO04OPEN] MooFest G 加强版
    P5094[USACO04OPEN]MooFestG加强版-洛谷|计算机科学教育新生态(luogu.com.cn)#include<bits/stdc++.h>usingnamespacestd;usingi64=longlong;intmain(){ios::sync_with_stdio(false);cin.tie(nullptr);intn;cin>>n;vecto......
  • CDQ分治
    CDQ分治CDQ分治是一种思想而不是具体的算法,与动态规划类似。目前这个思想的拓展十分广泛,依原理与写法的不同,大致分为三类:解决和点对有关的问题。1D动态规划的优化与转移。通过CDQ分治,将一些动态问题转化为静态问题。解决和点对有关的问题这类问题多数类似于「给定一......
  • cdq分治
    cdq分治主要思想为分治,分为三个部分:左区间内部。左区间对右区间。右区间内部。一个保险的标准顺序是先处理左区间,再处理左区间对右区间的贡献,最后处理右区间,这样就可以保证时序性了。注意这种写法在处理左区间对右区间贡献是要先按标号排序分出正确的左右区间,如果是先递归......
  • cdq分治 提高篇
    优化动态规划序列首先要会最长上升子序列的转移,这里就不说了。我们\(i\)位置的初始值为\(a_i\),可能变成的最大值为\(mx_i\),可能变成的最小值为\(mn_i\)。然后如果\(j\)要转移到\(i\),则需要满足:\(j<i,mx_j\lea_i,a_j\lemn_i\)。然后考虑把\([l,mid]\)按照\(mx\)......
  • cdq分治
    简介前置芝士:归并排序。\(cdq\)分治是个离线算法,可以解决三维偏序或者优化\(dp\)。题目直接上个题目:陌上花开。维护三维偏序有个口诀:一维排序,二维归并,三位数据结构。考虑第一维直接排序解决掉,然后还剩两维。我们考虑第二维用归并排序解决掉。然后假设当前区间\([l,r]\),......
  • 离线分治算法:cdq 分治
    \(\texttt{0x00}\):前置芝士归并排序;树状数组;重载运算符(这个大概都会吧)。\(\texttt{0x01}\):介绍cdq分治是一种离线分治算法,可用来处理以下几种问题:解决和点对有关的问题。1D动态规划的优化与转移。通过CDQ分治,将一些动态问题转化为静态问题。它们的本质都是通过一......
  • CDQ分治
    该分治算法由CDQ提出,主要用于解决三维偏序问题。下面的内容就三维偏序例题来讲。题目给你一个序列,每个元素有\(a,b,c\)三个属性,问满足\(a_i>a_j,b_i>b_j,c_i>c_j\)的数对\(i,j\)的数量。分析将原序列按照\(a\)值排序,将其变为下标。CDQ分治的主要步骤是对于一个需要......
  • CDQ 分治学习笔记
    CDQ分治的流程大致是将对于区间\([l,r]\)中点\(x,y\)的计数分为两类处理:\(x,y\)均位于\([l,mid]\)或\([mid+1,r]\)中,这样的点对贡献可以递归解决。\(x,y\)分别位于\([l,mid]\)和\([mid+1,r]\)中,这样的点对通过一些操作来统计贡献。显然这两类贡献之和即为......
  • cdq分治
    cdq分治其大致形式为递归左右半边考虑左半边对右半边的影响二维偏序(归并排序):计算数对\((i,j)\)满足\(a_i<a_j\)并且\(b_i<b_j\)的数对数量先以\(a_i\)排序,这样条件被转换为\(i<j\)且\(b_i<b_j\)考虑cdq分治先递归左右半边对左右两边各开一个指针,若\(b_i<b_......
  • 三维偏序的优秀做法
    感觉挺厉害的。我们使用\(f_i\)表示恰有\(i\)维满足偏序的数对\((x,y)\)的个数,\(g_i\)表示钦定\(i\)维满足偏序对的数对\((x,y)\)的个数。那么对于三维偏序:\[g_0=\dbinom{0}{0}f_0+\dbinom{1}{0}f_1+\dbinom{2}{0}f_2+\dbinom{3}{0}f_3=f_0+f_1+f_2+f_3\]\[g_1=\db......