分治在数集维护上用处很大，常用的是 cdq 分治，整体二分，线段树分治
cdq 分治
基本思想
-
将区间 \(l\) 到 \(r\) 分成 \(l\) 到 \(mid\) 和 \(mid+1\) 到 \(r\)
-
递归处理左右两边
-
统计左边对右边的贡献
可以解决 \(3\) 类问题
-
解决和偏序有关的问题
-
1D/1D 动态规划的优化与转移
-
一些动态问题转化为静态问题
先对第一维排序，再分治第二维
回溯时需用双指针统计左边对右边的贡献，流程如下
先对左右两边按第二维分别排序，在左右两边各放一个指针，若右边对应的值大于左边，则将左边的指针向右移一位，直到不能移动为止，可知当右边指针向后移动时，左边的指针及其之前的值第二维都小于新指的值
此时对于每个右指针，左指针及其之前的数都前两维小于右指针，偏序只可能在这之间产生，考虑使用树状数组维护，只需单点加，查询前缀和即可
对于这题，应先排序去重，再进行分治，对于一个 有 \(ans\) 个不同的偏序，\(sum\) 个相同的数，则在
\(ans+sum-1\) 处贡献了 \(sum\) 个值，处理一下即可
点击查看代码
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<vector>
#include<queue>
#include<string>
#include<cstring>
using namespace std;
struct node{
int a,b,c,num,ans;
}in[200100],sol[200100];
int n,Max,m,rt,id,sum[200100];
int c[200100];
int lowbit(int x)
{
return x&(-x);
}
void add(int x,int y)
{
while(x<=Max)
{
c[x]+=y;
x+=lowbit(x);
}
}
int query(int x)
{
int sum=0;
while(x)
{
sum+=c[x];
x-=lowbit(x);
}
return sum;
}
bool cmp1(node x,node y)
{
if(x.a==y.a&&x.b==y.b) return x.c<y.c;
else if(x.a==y.a) return x.b<y.b;
return x.a<y.a;
}
bool cmp2(node x,node y)
{
if(x.b==y.b) return x.c<y.c;
return x.b<y.b;
}
void cdq(int li,int ri)
{
if(li==ri) return ;
int mid=(li+ri)>>1;
cdq(li,mid);cdq(mid+1,ri);
sort(sol+li,sol+mid+1,cmp2);
sort(sol+mid+1,sol+ri+1,cmp2);
int i=li,j=mid+1;
for(;j<=ri;j++)
{
while(sol[i].b<=sol[j].b&&i<=mid)
{
add(sol[i].c,sol[i].num);
i++;
}
sol[j].ans+=query(sol[j].c);
}
for(int k=li;k<i;k++)
{
add(sol[k].c,-sol[k].num);
}
rt=id=0;
}
int main()
{
cin>>n>>Max;
for(int i=1;i<=n;i++)
{
cin>>in[i].a>>in[i].b>>in[i].c;
}
sort(in+1,in+1+n,cmp1);
int top=0;
for(int i=1;i<=n;i++)
{
top++;
if(in[i].a!=in[i+1].a||in[i].b!=in[i+1].b||in[i].c!=in[i+1].c)
{
m++;
sol[m]={in[i].a,in[i].b,in[i].c,top,0};
top=0;
}
}
cdq(1,m);
for(int i=1;i<=m;i++)
{
sum[sol[i].ans+sol[i].num-1]+=sol[i].num;
}
for(int i=0;i<n;i++)
{
cout<<sum[i]<<endl;
}
return 0;
}