P3810 【模板】三维偏序（陌上花开）（cdq分治）

思路

看到这种偏序类的题目，而且不要求强制在线，可以立刻想到cdq分治

注意这题有一个问题，就是询问的是小于等于而不是小于，如果相等的话两个元素会相互贡献，而cdq的特点是右区间不能对左边有影响，所以要先去重，再然后就是板子

代码

#include <cstdio>

#include <cstring>

#include <algorithm>

using namespace std;

int n,maxn;

namespace BIT{

    int bit[200100];

    int lowbit(int x){

        return x&(-x);

    }

    void add(int pos,int val){

        while(pos<=maxn){

            bit[pos]+=val;

            pos+=lowbit(pos);

        }

    }

    int query(int pos){

        int ans=0;

        while(pos){

            ans+=bit[pos];

            pos-=lowbit(pos);

        }

        return ans;

    }

    void clear(int pos){

        while(pos<=maxn){

            if(bit[pos])

                bit[pos]=0;

            else

                break;

            pos+=lowbit(pos);

        }

    }

}

struct Num{

    int a,b,c,val;

    bool operator == (const Num &bx) const{

        if(a==bx.a&&b==bx.b&&c==bx.c)

            return true;

        return false;

    }

    bool operator < (const Num &bx) const{

        if(a<bx.a)

            return true;

        else if(a==bx.a&&b<bx.b)

            return true;

        else if(a==bx.a&&b==bx.b&&c<bx.c)

            return true;

        else return false;

    }

}a[100100],num[100100];

int ans[100100],d[100100];

int cntnum=0,qid,aid;

struct Query{

    int posx,valy,val,aid;

}query[100100<<1];

Query tmp[100100<<1];

void cdq(int L,int R){

    // printf("%d %d\n",L,R);

    if(R<=L+1)

        return;

    int mid=(L+R)>>1;

    cdq(L,mid);

    cdq(mid,R);

    int l=L,r=mid,tot=0;

    while(l<mid&&r<R){

        if(query[l].posx<=query[r].posx){

            BIT::add(query[l].valy,query[l].val);

            tmp[++tot]=query[l++];

        }

        else{

            ans[query[r].aid]+=BIT::query(query[r].valy);

            tmp[++tot]=query[r++];

        }

    }

    while(l<mid)

        tmp[++tot]=query[l++];

    while(r<R){

        ans[query[r].aid]+=BIT::query(query[r].valy);

        tmp[++tot]=query[r++];

    }

    for(int i=1;i<=tot;i++){

        BIT::clear(tmp[i].valy);

        query[i+L-1]=tmp[i];

    }

}

int main(){

    scanf("%d %d",&n,&maxn);

    for(int i=1;i<=n;i++)

        scanf("%d %d %d",&a[i].a,&a[i].b,&a[i].c),a[i].val=1;

    sort(a+1,a+n+1);

    // printf("ok\n");

    // for(int i=1;i<=n;i++)

    //     printf("%d %d %d\n",a[i].a,a[i].b,a[i].c);

    num[++cntnum]=a[1];

    for(int i=1;i<=n-1;i++){

        if(a[i]==a[i+1])

            num[cntnum].val++;

        else

            num[++cntnum]=a[i+1];

    }

    for(int i=1;i<=cntnum;i++){

        query[++qid].posx=num[i].b;

        query[qid].aid=++aid;

        query[qid].valy=num[i].c;

        query[qid].val=num[i].val;

    }

    // printf("ok\n");

    cdq(1,qid+1);

    for(int i=1;i<=qid;i++){

        d[ans[query[i].aid]+query[i].val-1]+=query[i].val;

    }

    for(int i=0;i<=n-1;i++)

        printf("%d\n",d[i]);

    return 0;

}

巴特西

P3810 【模板】三维偏序（陌上花开）（cdq分治）

思路

代码

最新文章

热门文章