CDQ分治第一道题。。
这里我主要想说几个细节。。坑了我很久。
结构体里面的标号$id$应是按第一维$a$排完序之后的。。
然后就是CDQ里面排序时应按如下规则排序。。
------------------------------------
bool cmp2(const Node &i,const Node &j){
if(i.b!=j.b) return i.b<j.b;
if(i.c!=j.c) return i.c<j.c;
return i.id<j.id;
}
-----------------------------------
先是第二维,再是第三维,最后是编号。。
因为首先要保证$b$是有序的,而$b$相同时,为防止漏解,应保证$c$有序,而$b$ , $c$ 相同时,同样应使编号小的在前面,防止漏解。。
在CDQ之前要去重(显然这和去重并没有什么关系,不知道为什么都这么说,只是一种情况。。)
由于我们在进行CDQ时都是统计前面对后面的贡献,所以当两个向量完全相同时,后面对前面也是有贡献的,
而我们在CDQ里面进行排序时,当$b$ , $c$ 都相同时,是按编号排序,所以并不会统计到完全相同时后面对前面的贡献,所以要提前统计一下。。
sort是前闭后开QAQ。。
不说了,上代码。还是非常友好的。
#include<iostream> #include<algorithm> #include<cstdio> #define N 100010 using namespace std; int n,k,tree[N*2],ans[N]; struct Node{ int a,b,c,id,v; bool operator == (const Node &i){ if(i.a==a && i.b==b && i.c==c) return true; else return false; } }t[N]; Node last; bool cmp(const Node &i,const Node &j){ if(i.a==j.a && i.b==j.b) return i.c<j.c; if(i.a==j.a) return i.b<j.b; return i.a<j.a; } bool cmp2(const Node &i,const Node &j){ if(i.b!=j.b) return i.b<j.b; if(i.c!=j.c) return i.c<j.c; return i.id<j.id; } inline int read(){ char c=getchar();int x=0,flag=1; while(c<'0' || c>'9'){if(c=='-') flag=-1;c=getchar();} while(c>='0' && c<='9') x=(x<<1)+(x<<3)+c-'0',c=getchar(); return x*flag; } void add(int x,int y){ for(;x<=k;x+=x&-x) tree[x]+=y; } int ask(int x){ int res=0; for(;x;x-=x&-x) res+=tree[x]; return res; } void solve(int l,int r){ if(l==r) return; int mid=(l+r)>>1; solve(l,mid);solve(mid+1,r); sort(t+l,t+r+1,cmp2); for(int i=l;i<=r;i++){ if(t[i].id<=mid) add(t[i].c,1); else t[i].v+=ask(t[i].c); } for(int i=l;i<=r;i++) if(t[i].id<=mid) add(t[i].c,-1); } int main(){ n=read();k=read(); for(int i=1;i<=n;i++) t[i].a=read(),t[i].b=read(),t[i].c=read(); sort(t+1,t+n+1,cmp);int cnt=0; for(int i=n;i>=1;i--){ t[i].id=i; if(t[i]==last){t[i].v+=cnt;cnt++;} else last=t[i],cnt=1; } solve(1,n); for(int i=1;i<=n;i++) ans[t[i].v]++; for(int i=0;i<n;i++) printf("%d\n",ans[i]);return 0; }
呃呃呃,博客园没有Markdown。。。