关于 cdq 求三维偏序
查看原帖
关于 cdq 求三维偏序
857626
_RainCappuccino_楼主2024/7/1 19:33

为什么不能将 cdq(mid + 1, r) 在计算完跨块贡献后执行。

void cdq (int l, int r) {
    if(l == r) return;
    int mid = (l + r) / 2;
    cdq (l, mid);
    cdq (mid + 1, r);
    sort(a + l, a + mid + 1, cmpb), sort(a + mid + 1, a + r + 1, cmpb);
    int i = l;
    // cout << mid + 1 << ' ' << r << endl;
    for (int j = mid + 1; j <= r; j ++) {
        while(i <= mid && a[i].b <= a[j].b) {
            t.add(a[i].c, 1);
            i ++;
        } 
        cnt[a[j].id] += t.getx(a[j].c);
    }
    for (int p = l; p < i; p ++) t.add(a[p].c, -1);
}

2024/7/1 19:33
加载中...