前置技能：归并排序，树状数组。
cdq分治主要是用来离线解决一些奇怪的问题的。可以用来代替一些高级数据结构比如树套树或者KD-Tree之类的。。。
话说挑战2上的KD-Tree我到现在还没开始学。。。
cdq遇到在线的好像就死掉了？(雾
目前在博主的能力范围内：
主要用来解决多维(三维)偏序问题。
bzoj 陌上花开：给n朵花，每朵花有abc三个属性，问对于每朵花 i 满足 ai>=aj&&bi>=bj&&ci>=cj的花儿有多少。
我们使用cdq减掉一维同时复杂度乘以log。
回想归排求逆序对，其实也就是二维偏序问题，我们在对x排好序的前提下，x可以当成下标，求 xi<xj&&yi>yj的数的数目。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,a[],b[];ll ans;
void cdq(int l,int r){
if(l==r) return;
int m=l+r>>;
cdq(l,m);
cdq(m+,r);
int i=l,j=m+,st=l;
while (i<=m&&j<=r){
if(a[i]<=a[j]){
b[st++]=a[i++];
} else{
ans+=(m-i+);
b[st++]=a[j++];
}
}
while (i<=m) b[st++]=a[i++];
while (j<=r) b[st++]=a[j++];
for(int i=l;i<=r;i++){
a[i]=b[i];
}
}
int main(){
ios::sync_with_stdio(false);
cin>>n;
for(int i=;i<=n;i++)
cin>>a[i];
cdq(,n);
cout<<ans<<endl;
}
然后维护左区间对右区间每个数的影响，也就是 ans+=(m-i+1);这句话。
那么我们知道bit也可以解决二维偏序问题，所以我们使用 归并+bit就可以解决三维偏序问题。
关键代码处加了注释
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5+;
struct Flower{
int a,b,c,cnt,ans;
}a[N],A[N];
bool cmp2(const Flower &a, const Flower&b){
return a.a<b.a||(a.a==b.a&&a.b<b.b)||(a.a==b.a&&a.b==b.b&&a.c<b.c);
}
bool cmp1(const Flower& a,const Flower& b){
return a.b<b.b||(a.b==b.b&&a.c<b.c);
}
int n,k,c[N];
int lowbit(int k){ return k&-k;}
void add(int pos,int num){
while (pos<=k){
c[pos]+=num;pos+=lowbit(pos);
}
}
int sum(int x){
int ans = ;
while (x){ ans+=c[x];x-=lowbit(x); }
return ans;
}
Flower t[N];
void cdq(int l,int r){//l-r满足a非严格递增
if(l==r) return;
int m = l+r>>;
cdq(l,m);
cdq(m+,r);
int j=l;
for(int i=m+;i<=r;i++){
for(;j<=m&&A[j].b<=A[i].b;j++)
add(A[j].c,A[j].cnt);
A[i].ans+=sum(A[i].c);
}
for(int i=l;i<j;i++)
add(A[i].c,-A[i].cnt); int l1=l,l2=m+; int pos=l;
while(l1<=m||l2<=r) {
if(l2>r||(l1<=m&&cmp1(A[l1],A[l2]))) t[pos++]=A[l1++];
else t[pos++]=A[l2++];
}
for(int i=l;i<=r;i++) A[i]=t[i];
} int ans[N];
int main(){
ios::sync_with_stdio(false);
cin>>n>>k;
for(int i=;i<=n;i++){
cin>>a[i].a>>a[i].b>>a[i].c;
a[i].cnt=;
}
sort(a+,a++n,cmp2);//先保证a的大小关系
int cnt = ;
for(int i=;i<=n;i++){
if(i==||!(a[i].a==a[i-].a&&a[i].b==a[i-].b&&a[i].c==a[i - ].c))//处理abc三个属性全部一样的花
A[cnt++] = a[i];
else
A[cnt-].cnt++;
}
cdq(,cnt-);
for(int i = ; i <= cnt; i++)
ans[A[i].ans+A[i].cnt-] += A[i].cnt;
for(int i = ; i < n; i++)
cout<<ans[i]<<endl;
return ;
}
/**
10 3
3 3 3
2 3 3
2 3 1
3 1 1
3 1 2
1 3 1
1 1 2
1 2 2
1 3 2
1 2 1
*/
/**
3
1
3
0
1
0
1
0
0
1
*/
SHOI2007 园丁的烦恼
做法很多。。。这里讲一下cdq。和上一道题是一样的吧，可以这样想，把 t,x,y当成三个变量，t代表了操作时间，可以理解成 查询/添加，
然后对于 (x1,y1)到(x2,y2)可以差分一下，en...
那么这道题就变成了一个 求 满足 ti>tj,xi>=xj,yi>=yi 这样的一个三维偏序问题
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 35e5+;
struct Node{
int op,x,y,w,id;
}a[N],A[N];
int n,m,up,tot;
int c[N];
int lowbit(int x){
return x&-x;
}
void upd(int pos,int x){
while (pos<=up) {
c[pos]+=x;
pos+=lowbit(pos);
}
}
int sum(int x){
int res = ;
while (x){
res+=c[x];
x-=lowbit(x);
}
return res;
}
void clear(int x){
while(x<=up) {
if(c[x]) c[x]=;
else break;
x+=lowbit(x);
}
}
bool cmp(Node a,Node b){
return a.x<b.x||(a.x==b.x&&a.op<b.op);
}
int ans[N];
void cdq(int l,int r){
if(l==r) return;
int mid = l+r>>;
cdq(l,mid);
cdq(mid+,r);
int i=l,j=mid+,st=l;
while (i<=mid&&j<=r){
if(cmp(a[i],a[j])){
if(a[i].op==)
upd(a[i].y,);
A[st++]=a[i++];
} else{
if(a[j].op==)
ans[a[j].id]+=a[j].w*sum(a[j].y);
A[st++]=a[j++];
}
}
while (i<=mid) A[st++]=a[i++];
while (j<=r){
if(a[j].op==)
ans[a[j].id]+=a[j].w*sum(a[j].y);
A[st++] = a[j++];
}
for(int i=l;i<=r;i++){
clear(a[i].y);
a[i]=A[i];
}
}
void ins(int op,int x,int y,int w,int id){
tot++;
a[tot].op=op;a[tot].x=x;a[tot].y=y;a[tot].w=w;a[tot].id=id;
}
int main(){
scanf("%d%d",&n,&m);
int x,y;
for(int i=;i<=n;i++){
scanf("%d%d",&x,&y);;x++;y++;
ins(,x,y,,);
up = max(y,up);
}
int x2,y2;
for(int i=;i<=m;i++){
scanf("%d%d%d%d",&x,&y,&x2,&y2);
x++;y++;x2++;y2++;
ins(,x2,y2,,i);
ins(,x-,y2,-,i);
ins(,x2,y-,-,i);
ins(,x-,y-,,i);
up = max(max(y,y2),up);
}
cdq(,tot);
for(int i=;i<=m;i++)
printf("%d\n",ans[i]);
return ;
}
bzoj 3295 动态逆序对
这类问题我们有一个方法就是倒着来一遍吧。然后我们按照时间戳给所有元素标号，每个点 具有 t,x,y 三个属性，就又变成了一个三维偏序问题。
那么我们需要求的 就是 满足(令当前元素为i) t<ti,x<xi,y>yi的数目加上 t<ti, x>xi,y<yi的数目。
然后我们在归并的时候分别从左往右扫，从右往左扫一下就可以了。
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5+;
struct Node{
int t,x,y;
}a[N],A[N];
int ld[N],yx[N];
int n,m,c[N];
int lowbit(int x){ return x&-x;}
void upd(int pos,int x){
while (pos<=n){
c[pos]+=x;
pos+=lowbit(pos);
}
}
void clear(int x){
while (x<=n){
if(c[x]) c[x]=,x+=lowbit(x);
else break;
}
}
int sum(int x){
int res = ;
while (x){
res+=c[x];
x-=lowbit(x);
}
return res;
}
void cdq(int l,int r){//保证x单调增
if(l==r) return;
int mid = l+r>>;
int s1=l,s2=mid+;
for(int i=l;i<=r;i++){//左边的t全部小于右边的，同时x单调
if(a[i].t<=mid)
A[s1++]=a[i];
else
A[s2++]=a[i];
}
for(int i=l;i<=r;i++)
a[i]=A[i];
s1=l;s2=mid+;
while (s2<=r){//
while (s1<=mid&&a[s1].x<a[s2].x){//x小y大
upd(a[s1].y,);s1++;
}
ld[a[s2].t]+=(s1-l)-sum(a[s2].y);//左边y比他大的
s2++;
}
for(int i=l;i<=mid;i++)
clear(a[i].y);
s1=mid;s2=r;
while (s2>=mid+){
while (s1>=l&&a[s1].x>a[s2].x){//x大y小
upd(a[s1].y,);
--s1;
}
yx[a[s2].t]+=sum(a[s2].y-);
s2--;
}
for(int i=l;i<=mid;i++)
clear(a[i].y);
cdq(l,mid);cdq(mid+,r);
}
int pos[N];
long long ans[N];
int main(){
ios::sync_with_stdio(false);
cin>>n>>m;
for(int i=;i<=n;i++){
cin>>a[i].y;a[i].x=i;pos[a[i].y]=i;
}
int x,all=n;
for(int i=;i<=m;i++){
cin>>x;
a[pos[x]].t=all--;
}
for(int i=;i<=n;i++){
if(!a[i].t)
a[i].t=all--;//
}
cdq(,n);
for(int i=;i<=n;i++){
ans[i]=ans[i-]+yx[i]+ld[i];
}
for(int i=n;i>=n-m+;i--){
cout<<ans[i]<<endl;
}
}