cdq分治

发布于 2020-10-11  75 次阅读


CDQ分治

cdq分治是一种分治思想,其实就是归并排序,,,。解决一个区间问题,分而治之,[l, r]->[l, mid] + [mid+1, r]。同时在解决完子问题后,还要考虑这两个子问题之间的相互影响,求一个子问题对另一个子问题的贡献。

P3810 三维偏序

在解决离线三维偏序问题时,我们可以先把原来的元素按第一关键词,第二关键词,第三关键词升序排序,这样可以保证一个元素后面的元素对它不会有贡献(注意先去重)。然后分而治之,在两个子问题都被解决之后,这两个子区间内的元素应已经按第二关键词排好序了,然后我们依照归并排序的方式一次拿下两子区间的元素,同时把元素的第三关键词的值加入树状数组。那么对于右区间的每一个元素,当轮到它被拿下时,在树状数组里寻找第三关键字值比它小的元素个数,加入到它的贡献里即可。

#include <bits/stdc++.h>

using namespace std;
const int maxn = 1e5+5, maxk = 2e5+5;
int n, k, m;
struct zyh{
    int a, b, c;
    int w, t;
}nums[maxn], tmp[maxn];
int c[maxk], ans[maxn];
inline int lowbit(int i){
    return i & (-i);
}
void add(int i, int d){
    while (i<=k){
        c[i] += d;
        i += lowbit(i);
    }
    return;
}
int sum(int i){
    int ans = 0;
    while (i){
        ans += c[i];
        i -= lowbit(i);
    }
    return ans;
}
void cdq(int l, int r){
    if (l==r)   return;
    int mid = (l+r) >> 1;
    cdq(l, mid);    cdq(mid+1, r);
    int i = l, j = mid+1, cnt = 0;
    for ( ; j<=r; j++){
        while (i<=mid && nums[i].b<=nums[j].b)  add(nums[i++].c, nums[i].t);
        nums[j].w += sum(nums[j].c);
        //add(nums[j].c, 1);
    }
    //for (j=mid+1; j<=r; j++)    add(nums[j].c, -1);
    for (i--; i>=l; i--)  add(nums[i].c, -nums[i].t);
    i = mid;
    //while (nums[i].a)
    i = l, j = mid+1;
    while (i<=mid && j<=r){
        if (nums[i].b <= nums[j].b) tmp[++cnt] = nums[i++];
        else    tmp[++cnt] = nums[j++];
    }
    while (i<=mid)  tmp[++cnt] = nums[i++];
    while (j<=r)    tmp[++cnt] = nums[j++];
    for (i=l, j=1; i<=r; i++, j++)  nums[i] = tmp[j];
    return;
}
inline bool cmp(struct zyh x, struct zyh y){
    if (x.a != y.a) return x.a < y.a;
    if (x.b != y.b) return x.b < y.b;
    return x.c < y.c;
}
inline bool equal(struct zyh x, struct zyh y){
    if (x.a==y.a && x.b==y.b && x.c==y.c)   return true;
    return false;
}
int main(){
    scanf ("%d %d", &n, &k);
    for (int i=1; i<=n; i++){
        scanf ("%d %d %d", &nums[i].a, &nums[i].b, &nums[i].c);
        nums[i].w = 0, nums[i].t = 1;
    }
    sort (nums+1, nums+n+1, cmp);
    int cnt = 1;
    tmp[1] = nums[1];
    for (int i=2; i<=n; i++){
        if (!equal(nums[i], nums[i-1])) tmp[++cnt] = nums[i];
        else    tmp[cnt].t++;
    }
    m = n, n = cnt;
    for (int i=1; i<=n; i++)    nums[i] = tmp[i], nums[i].w = nums[i].t-1;
    cdq(1, n);
    for (int i=1; i<=n; i++)    ans[nums[i].w] += nums[i].t;
    for (int i=0; i<m; i++)
        printf ("%d\n", ans[i]);
    return 0;
}

一沙一世界,一花一天堂。君掌盛无边,刹那成永恒。