花儿们已经很累了——

无论是花形、颜色、还是气味，

都不是为了给人们摆出来欣赏的，

更不是为了当做出题的素材的，

她们并不想自己这些属性被没有生命的数字量化，

并不想和其它的花攀比，

并无意分出个三六九等，

它们只想静静地开放，

完成自己这一生的使命，

而你(出题人)考虑过这些吗？

不，你只关心你自己！

题目的传送门会有的，先不要着急...

首先来看一道大水题.

给定\(n\)个元组\((x)\), 询问对于每个元组\(i\), 有多少个元组\(j\)满足\(x_i<x_j\). (一维偏序)

那不就是sort一遍就水过去了么←_←

有追求一点?

那就写个权值树状数组吧...

那我们看一道升级版.

给定\(n\)个元组\((x,y)\), 询问对于每个元组\(i\), 有多少个元组\(j\)满足\(x_i<x_j\)且\(y_i<y_j\) (二维偏序)

Emmmm.... 以\(x\)为关键字排序, 以\(y\)为关键字建树状数组好像可做.

那\(y\)权值大一点呢? 我们可以离散啊XD

好像也不难, 这样就水过去了.

那再升升级?

给定\(n\)个元组\((x,y,z)\), 询问对于每个元组\(i\), 有多少个元组\(j\)满足\(x_i<x_j,y_i<y_j\)且\(z_i<z_j\)

这就是著名的三维偏序问题. 怎么样, 不是很好做了吧?

为什么会有这样的题啊喂!!! 可是确实有的题.. (你看我说会有传送门嘛←_←)

冷静分析, 仔细思考, 我们可以:

排序+............树套树???

说得好像你会树套树一样...

这玩意看上去就巨tm难写啊, 有没有什么好做一点的方法啊...

cdq大爷说, 我们可以用一种特殊的分治方式水过去. orz

啥啥啥啥啥??? 分治???

分治我见过啊, 好像是个挺常见的算法...

常见的分治算法:

• 归并排序
• 快速排序
• 快速凸包算法
• 线段树

一般的分治都有着如下流程:

SOLVE(L,R)      //好像是首打油诗-> MID=(L+R)>>1 //找到区间的中点-> SOLVE(L,MID) //递归处理左半边-> SOLVE(MID+1) //递归处理右半边-> MERGE(L,R)   //合并区间的操作

而且一般情况下能拥有一个不错的复杂度:

T(n) = 2T(n/2)+O(kn), T(n) = O(knlogn)T(n) = 2T(n/2)+O(knlogn), T(n) = O(knlog^2n)T(n) = 2T(n/2)+O(k), T(n) = O(kn)

分治中主要需要考虑的就是合并区间时要进行什么操作.

回到我们的三维偏序问题. 我们考虑分治解决问题.

我们对\(x\)这一维进行分治, 这样剩下的就是我们会的二维偏序了.

然后来思考合并区间时候的操作.

那么假设我们已经处理好了\([L,mid]\)和\((mid,R]\)这两个区间了.

但是这是不够滴, 我们还要考虑到, \([L,mid]\)中的点对于\((mid,R]\)来说, 也会对答案有贡献.

我们对\([L,R]\)按\(y\)排序, 对\(z\)建树状数组(该离散就离散..)

然后扫一遍, 如果\(x\in[L,mid]\), 单点加, 否则就查询.

复杂度应该是\(O(nlog^2n)\)的.

woc细节调到心态爆炸...估计还是自己码力太弱了...把注释写的详细一点吧..

#include 
    
     #include 
     
      using namespace std;const int N=1e5+10;struct flower{    int x,y,z;    int cnt,ans; //个数(会重不是),答案}a[N];inline bool operator<(const flower& a,const flower &b){    if(a.y==b.y){        if(a.z==b.z) return a.x
      
       '9';c=getchar());    for(;c>47&&c<58;c=getchar())a=a*10+c-48; return a;}//cdq分治!!void solve(int l,int r){    if(l==r) {        a[l].ans+=a[l].cnt-1; //有重复        return;    }    int mid=(l+r)>>1;    //分治    solve(l,mid);    solve(mid+1,r);        //分别排序    sort(a+l,a+mid+1);    sort(a+mid+1,a+r+1);    int j=l;    //对于后半段的每个点    for(int i=mid+1;i<=r;++i){        //如果前半段的y比较小了就可以查询到了        while(j<=mid&&a[j].y<=a[i].y)            add(a[j].z,a[j].cnt),++j;        a[i].ans+=query(a[i].z);    }    //因为还要递归下去继续处理所以要消除影响..    for(int i=l;i
       
        1&&a[i]==a[i-1]) ++a[m].cnt;        else a[++m]=a[i],a[m].cnt=1;    solve(1,m);    //统计答案即可    for(int i=1;i<=n;++i) ans[a[i].ans]+=a[i].cnt;    for(int i=0;i
       
      
     
    

就这样吧...

一定记得消除影响, 注意变量名和变量的作用域, 注意枚举的先后顺序.

别的也就没啥了OvO