0x00 简介
-- 是的 , \(CDQ\) 分治是一款由女oier \(CDQ\) 引入的分治算法 , 可以利用分治让我们离线地解决一些在线数点问题
-- 你说的对 , 但是面对强制在线的题目 , \(CDQ\)就会寄掉
0x01 引入
题目大意 : 对于一个点有三个关键值 : \(a,b,c\) ; 我们定义一个点 \(i\) 比另一点 \(j\) 大 , 当且仅当$a_i\ge a_j 且 b_i\ge b_j 且 c_i\ge c_j $ , 设点 \(i\) 比 \(f(i)\) 个点大 , 求对于每个\(d\) , 有多少 \(f(i)\) 满足 \(f(i)=d\)
0x02 思路
我们的目标就是对满足$a_i\ge a_j 且 b_i\ge b_j 且 c_i\ge c_j $这三个条件的点对进行记数
三个条件没有优先级 , 是平等的
所以我们可以先选择一个条件来满足
就先满足有关 \(a\) 的吧 , 方法很简单 , 就是把点以 \(a\) 为第一关键字进行排序
bool comp(node a,node b) { // 第一次排序 : 对a进行排序
if(a.a==b.a && a.b==b.b)
return a.c<b.c;
if(a.a==b.a)
return a.b<b.b;
return a.a<b.a;
}
解决了 \(a\) , 下面处理 \(b\) 和 \(c\)
这时用到了 \(CDQ\) 分治的思想 , 把序列一分为二 , 分别统计
假设我们在处理的序列区间是\([l,r]\) , 把它分成 \([l,mid]\) 和 \([mid+1,r]\)
那么如何把两个区间合并起来计算答案呢 ?
首先 , 由于我们已经对 \(a\) 进行了排序 , 所以只可能是前半段对后半段做贡献
而且 , 前半段点的顺序是不会对贡献产生任何影响的
因此 , 我们再把两段分别以 \(b\) 为关键字进行排序 , 这样可以方便后面的计算
然后就是计算两段的贡献了 , 我们对两段序列都开一个指针 , 开始指向序列的第一个
接下来我们以右边序列的指针为基准 , 往后移动左边指针直到左指针的点的 \(b\) 比右指针指点的 \(b\) 大 , 我们把左边满足 \(b\) 要求的点放入 "待选集合"。由于我们已经对左右边的点按 \(b\) 排序过 , 所以我们右移右指针后 , 前一个数产生的待选集合中的点也都是满足 \(b\) 条件的 , 可以直接继承过来
然后就是判断 \(c\) 条件。假设右指针对应点的 \(c=c_R\) , 待选集合为$ S $ , 我们的目标是算 $\sum_{i\in S}(c_i\le c_r) $ , 如何快速算出这个东西呢 ? 很容易想到可以利用权值树状数组进行维护
最后注意 , 处理完当前区间后要清空树状数组 , 以免对后面产生影响
\(code\) \(of\) \(CDQ\)
void cdq(int l,int r){
if(l==r) return ;
int mid=l+r>>1;
cdq(l,mid);//分别处理左右区间
cdq(mid+1,r);
sort(s+l,s+mid+1,comp2);//按 b 排序
sort(s+mid+1,s+r+1,comp2);
int p1=1,p2=mid+1;// 左右指针
for(; p2<=r ; p2++){
while(p1<=mid && s[p1].b<=s[p2].b)
bit.add(s[p1].c,s[p1].cnt),p1++;//把左边的点加入待选集合 , 用树状数组维护
s[p2].ans+=bit.query(s[p2].c);//统计答案
}
for(int i=l;i<p1;i++) // 注意这里是i<p1!因为p1并没有被加入待选集合!
bit.add(s[i].c,-s[i].cnt);//撤销影响
return ;
}
在加上一些小东西就可以完成本题了 :
- 对于 \(a,b,c\) 完全相等的点 , 我们可以直接把他们压成一个 , 可以节省时间复杂度
- 好像没了 , 这条是凑数的
完整的 \(code\) :
#include <bits/stdc++.h>
using namespace std;
inline int read(){
char ch=getchar();
int s=0,f=1;
for(;!isdigit(ch);ch=getchar()) if(ch=='-') f*=-1;
for(; isdigit(ch);ch=getchar()) s*=10,s+=ch-'0';
return s*f;
}
inline int lowbit(int x){
return x&(-x);
}
const int N = 1e5+10;
struct node {
int a, b, c;
int cnt;
int ans;
}s[N];
int n,k;
struct Bit{// 权值树状数组
int a[N];
void add(int x,int y) {
for(;x<=k;x+=lowbit(x))
a[x]+=y;
}
int query(int x){
int ans=0;
for(;x;x-=lowbit(x))
ans+=a[x];
return ans;
}
}bit;
int ans[N];
bool comp(node a,node b) { // 第一次排序 : 对a进行排序
if(a.a==b.a && a.b==b.b)
return a.c<b.c;
if(a.a==b.a)
return a.b<b.b;
return a.a<b.a;
}
bool comp2(node a,node b){ // 第二次排序 : 对b进行排序
if(a.b==a.b)
return a.c<b.c;
return a.b<b.b;
}
void cdq(int l,int r){
if(l==r) return ;
int mid=l+r>>1;
cdq(l,mid);
cdq(mid+1,r);
sort(s+l,s+mid+1,comp2);
sort(s+mid+1,s+r+1,comp2);
int p1=1,p2=mid+1;
for(; p2<=r ; p2++){
while(p1<=mid && s[p1].b<=s[p2].b)
bit.add(s[p1].c,s[p1].cnt),p1++;
s[p2].ans+=bit.query(s[p2].c);
}
for(int i=l;i<p1;i++)
bit.add(s[i].c,-s[i].cnt);
return ;
}
int main(){
n=read(),k=read();
for(int i=1;i<=n;i++)
s[i].a=read(),s[i].b=read(),s[i].c=read();
sort(a+1,a+n+1,comp);
int tot=0,m=0;
for(int i=1;i<=n;i++){// 把相同点压缩
tot++;
if(s[i].a!=s[i-1].a || s[i].b!=s[i-1].b || s[i].c!=s[i-1].c){
s[++m]=s[i];
s[m].cnt=tot;
tot=0;
}
}
cdq(1,m);
for(int i=1;i<=m;i++)
ans[s[i].ans+s[i].cnt-1] += s[i].cnt;//注意和它完全相等的点也要统计答案 , 而自己不行 , 所以答案就是 s[i].ans+s[i].cnt-1
for(int i=0;i<n;i++){
printf("%d\n",ans[i]);
}
return 0;
}