传送门

先是计算f。

显然第一维排序。

然后第二维CDQ分治。

CDQ分治时用树状数组处理第三维。

具体是这样的:

显然树状数组的两个操作分别是$add(a,b)$和$sum(a)$,意义显然。

首先一样的点合并。(显然)

设和第i个点重合的点个数为$Tot_i$,第i个点的三维分别为$A_i,B_i,C_i$.

然后按照第一维,第二维,第三维为第一二三个关键字升序排序。

然后CDQ分治。

CDQ分治是这样的:
CDQ(l,r):

CDQ(l,mid)
CDQ(mid+1,r)
处理$[l,mid]$区间对$(mid,r]$区间的贡献。

处理贡献时可以这样做:

首先很显然$[l,mid]$区间和$(mid,r]$区间的第二维是有序的(保持有序可以在之后归并维护),并且左区间的第一维全部严格小于右区间的。
然后归并。
假设正在比较左区间的x点和右区间的y点。
如果$B_x\le B_y$,则$add(C_x,Tot_x)$。
否则$f(y)+=sum(C_y)$
注意初始化的时候千万不能把树状数组全部置为0,要把加入树状数组的一个个减回去。
前一种方法复杂度 $O(k)$ ,后一种复杂度 $O(m log_2 k)$ ,其中m为加进去的个数。
则初始化的总复杂度为第一种$O(nk)$,后一种为$O(n log_2 n log_2 k)$
若一开始对第三维离散化,则复杂度为$O(n log_2^2 n)$
/*
Author: CNYALI_LK
LANG: C++
PROG: 3810.cpp
Mail: cnyalilk@vip.qq.com
*/
#include<bits/stdc++.h>
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define DEBUG printf("Passing [%s] in LINE %d\n",__FUNCTION__,__LINE__)
#define Debug debug("Passing [%s] in LINE %d\n",__FUNCTION__,__LINE__)
#define all(x) x.begin(),x.end()
using namespace std;
const double eps=1e-8;
const double PI=acos(-1.0);
typedef long long ll;
template<class T>int chkmin(T &a,T b){return a>b?a=b,1:0;}
template<class T>int chkmax(T &a,T b){return a<b?a=b,1:0;}
template<class T>T sqr(T a){return a*a;}
template<class T>T mmin(T a,T b){return a<b?a:b;}
template<class T>T mmax(T a,T b){return a>b?a:b;}
template<class T>T aabs(T a){return a<0?-a:a;}
#define min mmin
#define max mmax
#define abs aabs
int n,k;
inline int read(){
    char c;
    int s=0;
    while(!isdigit(c=getchar()));
    while(isdigit(c)){s=s*10+c-'0';c=getchar();}
    return s;
}
struct node{
    int a,b,c,cnt;
    int ans;
    void init(int d){a=read();b=read();c=read();}
};
int a_cmp(node a,node b){return a.a<b.a||(a.a==b.a&&(a.b<b.b||(a.b==b.b&&a.c<b.c)));}
node a[102424],b[102424];
int ans[102424];
int c[204848];
#define lowbit(x) x&(-x)
inline void add(int x,int y){
    while(x<=k){
        c[x]+=y;
        x+=lowbit(x);
    }
}
inline int sum(int x){
    int cnt=0;
    while(x){
        cnt+=c[x];
        x^=lowbit(x);
    }
    return cnt;
}
inline void cdq(int l,int r){
    if(l==r){a[l].ans=a[l].cnt;return;}
    int mid=(l+r)>>1;
    cdq(l,mid);
    cdq(mid+1,r);
    int sa=l,sb=mid+1,t=l-1;
    while(sb<=r){ 
        while(sa<=mid&&a[sa].b<=a[sb].b){
            b[++t]=a[sa];
            add(a[sa].c,a[sa].cnt);
            ++sa;
        }
        b[++t]=a[sb];
        b[t].ans+=sum(b[t].c);
        ++sb;
    }
    for(int i=l;i<sa;++i)add(a[i].c,-a[i].cnt);
    while(sa<=mid){
        b[++t]=a[sa];
        ++sa;
    }
    for(int i=l;i<=r;++i)a[i]=b[i];

}
inline int same(node a,node b){return a.a==b.a&&a.b==b.b&&a.c==b.c;}
int hv[233333];
int main(){
#ifdef cnyali_lk
    freopen("3810.in","r",stdin);
    freopen("3810.out","w",stdout);
#endif
    n=read();k=read();
    for(int i=1;i<=n;++i){
        b[i].init(i);
        hv[b[i].c]=1;
    }
    sort(b+1,b+n+1,a_cmp);
    int m=0,l=0;
    for(int i=1;i<=k;++i)if(hv[i])hv[i]=++l;
    k=l;
    for(int i=1;i<=n;++i)if(same(b[i],a[m])){
        ++a[m].cnt;
    }
    else {a[++m]=b[i];a[m].cnt=1;}
    for(int i=1;i<=n;++i)a[i].c=hv[a[i].c];
    n^=m^=n^=m;
    cdq(1,n);
    for(int i=1;i<=n;++i)ans[a[i].ans]+=a[i].cnt;
    for(int i=1;i<=m;++i)printf("%d\n",ans[i]);
    return 0;
}

标签: CDQ分治

添加新评论