陌上花开

题意

三维偏序模板题。

思路

第一维排序，第二维CDQ分治，第三维树状数组。

代码

#include <bits/stdc++.h>

using namespace std;

namespace StandardIO {
    
    template<typename T> inline void read (T &x) {
        x=0;T f=1;char c=getchar();
        for (; c<'0'||c>'9'; c=getchar()) if (c=='-') f=-1;
        for (; c>='0'&&c<='9'; c=getchar()) x=x*10+c-'0';
        x*=f;
    }
    template<typename T> inline void write (T x) {
        if (x<0) putchar('-'),x=-x;
        if (x>=10) write(x/10);
        putchar(x%10+'0');
    }
    
}

using namespace StandardIO;

namespace Solve {
    
    const int N=100001;
    
    int n,k,cnt=1;
    struct node {
        int a,b,c,ans,vis;
    } f[N],w[N];
    int tree[N*2],ans[N];
    
    inline bool cmpa (const node &a,const node &b) {
        if (a.a!=b.a) return a.a<b.a;
        if (a.b!=b.b) return a.b<b.b;
        return a.c<b.c;
    }
    inline bool cmpb (const node &a,const node &b) {
        if (a.b!=b.b) return a.b<b.b;
        return a.c<b.c;
    }
    inline int lowbit (int x) {
        return x&(-x);
    }
    inline void update (int x,int v) {
        for (register int i=x; i<=k; i+=lowbit(i)) {
            tree[i]+=v;
        }
    }
    inline int query (int x) {
        int res=0;
        for (register int i=x; i; i-=lowbit(i)) {
            res+=tree[i];
        }
        return res;
    }
    void CDQ (int l,int r) { 
        if (l==r) return;
        int mid=(l+r)>>1;
        CDQ(l,mid),CDQ(mid+1,r);
        sort(w+l,w+mid+1,cmpb),sort(w+mid+1,w+r+1,cmpb);
        int ptr=l-1;
        for (register int i=mid+1; i<=r; ++i) {
            while (ptr<mid&&w[ptr+1].b<=w[i].b) {
                ++ptr;
                update(w[ptr].c,w[ptr].vis);
            }
            w[i].ans+=query(w[i].c);
        }
        for (register int i=l; i<=ptr; ++i) {
            update(w[i].c,-w[i].vis);
        }
    }
    
    inline void MAIN () {
        read(n),read(k);
        for (register int i=1; i<=n; ++i) {
            read(f[i].a),read(f[i].b),read(f[i].c);
        }
        sort(f+1,f+n+1,cmpa);
        w[1]=f[1],w[1].vis=1;
        for (register int i=2; i<=n; ++i) {
            if (f[i].a==w[cnt].a&&f[i].b==w[cnt].b&&f[i].c==w[cnt].c) {
                ++w[cnt].vis;
            } else {
                w[++cnt]=f[i];
                w[cnt].vis=1;
            }
        }
        CDQ(1,cnt);
        for (register int i=1; i<=cnt; ++i) {
            ans[w[i].ans+w[i].vis-1]+=w[i].vis;
        }
        for (register int i=0; i<n; ++i) {
            write(ans[i]),putchar('\n');
        }
    }
    
}

int main () {
    Solve::MAIN();
}

陌上花开

原文：https://www.cnblogs.com/ilverene/p/11365875.html