【題解】文體陌上花開(kāi)

全國(guó)人民謝罪了

陌上花開(kāi)可緩緩歸矣

\(cdq\)做的，待會(huì)發(fā)\(kd-tree\)

多維偏序如何做的本質(zhì)是按照時(shí)間分治，時(shí)間在前面的對(duì)時(shí)間在后面的有影響，所以可以用樹(shù)狀數(shù)組統(tǒng)計(jì)答案。

和其他分治差不多，就是保證一維有序，從而為我們從中間分開(kāi)分治提供可能。這類(lèi)分治的一個(gè)基本原則就是盡量保證一定范圍的有序以讓我便于統(tǒng)計(jì)答案。因?yàn)橛行驗(yàn)槲覀冊(cè)O(shè)計(jì)算法提供太多的可能！

解釋一下我是什么意思，我對(duì)局部有序的理解就是可以保證一個(gè)范圍\(S\)中的所有元素會(huì)比另一個(gè)范圍\(C_US\)的任意元素都要小。這樣就可以在第二維上進(jìn)行排序，開(kāi)花，這樣我們保證小范圍內(nèi)的第二維有序之后，我們就可以基于時(shí)間對(duì)第三維設(shè)計(jì)算法了。

但是\(cdq?\)有個(gè)致命的地方，無(wú)法處理兩個(gè)元素完全相等這種情況，我們可以使用類(lèi)似離散化的思想，把所有相同的元素合并在一起。統(tǒng)計(jì)答案的時(shí)候另外設(shè)計(jì)算法。

待會(huì)加\(kd-tree?\)的

我咕了對(duì)不起我一個(gè)晚上學(xué)不會(huì)kd-treeQAQ

\(cdq\)一遍寫(xiě)過(guò)的我非常自豪，而且沒(méi)看題解QAQ！！(你tm拿暴力拍了10000組還要怎么樣)

現(xiàn)在我要向又短又快的代碼看齊

#include<bits/stdc++.h>using namespace std;typedef long long ll; #define DRP(t,a,b) for(register int t=(a),edd=(b);t>=edd;--t) #define RP(t,a,b) for(register int t=(a),edd=(b);t<=edd;++t) #define ERP(t,a) for(register int t=head[a];t;t=e[t].nx) #define midd register int mid=(l+r)>>1 #define TMP template < class ccf > #define lef l,mid #define rgt mid+1,r #define lb(x) ((x)&(-(x))) #define pushup(pos) (seg[pos]=seg[pos<<1]+seg[pos<<1|1]) TMP inline ccf qr(ccf b){register char c=getchar();register int q=1;register ccf x=0;while(c<48||c>57)q=c==45?-1:q,c=getchar();while(c>=48&&c<=57)x=x*10+c-48,c=getchar();return q==-1?-x:x;} TMP inline ccf Max(ccf a,ccf b){return a<b?b:a;} TMP inline ccf Min(ccf a,ccf b){return a<b?a:b;} TMP inline ccf Max(ccf a,ccf b,ccf c){return Max(a,Max(b,c));} TMP inline ccf Min(ccf a,ccf b,ccf c){return Min(a,Min(b,c));} TMP inline ccf READ(ccf* _arr,int _n){RP(t,1,_n)_arr[t]=qr((ccf)1);} //----------------------template&IO--------------------------- const int maxn=1e5+15; int seg[maxn<<1]; int buk[maxn]; struct NODE{int x,y,z,T,ape;inline bool operator < (NODE a)const{return x==a.x?(y==a.y?(z<a.z):(y<a.y)):(x<a.x);}inline bool operator ==(NODE a)const{return x==a.x and y==a.y and z==a.z;}inline void scan(){x=qr(1)+1;y=qr(1)+1;z=qr(1)+1;T=1;} }oj[maxn],data[maxn],temp[maxn]; // move right 1 unit int n,k,sz; int ans[maxn]; int q1[maxn],q2[maxn],cnt;inline void add(int now,int v){++cnt;q1[cnt]=now;q2[cnt]=v;for(register int t=now;t<=k;t+=lb(t)) seg[t]+=v; } inline void rec(){RP(t,1,cnt) add(q1[t],-q2[t]);cnt=0; } inline int que(int now){register int ret=0;for(register int t=now;t;t-=lb(t)) ret+=seg[t];return ret; }void cdq(int l,int r){midd;if(l==r){data[l].ape+=data[l].T-1;return;}cdq(lef);cdq(rgt);register int L=l,R=mid+1,K=l;while(L<=mid&&R<=r){if(data[L].y<=data[R].y){add(data[L].z,data[L].T);temp[K++]=data[L++];}else{data[R].ape+=que(data[R].z);temp[K++]=data[R++];}}while(L<=mid) add(data[L].z,data[L].T),temp[K++]=data[L++];while(R<=r) data[R].ape+=que(data[R].z),temp[K++]=data[R++];RP(t,l,r) data[t]=temp[t];rec(); }int main(){ #ifndef ONLINE_JUDGEfreopen("in.in","r",stdin);freopen("out.out","w",stdout); #endifn=qr(1);k=qr(1)+1;RP(t,1,n) oj[t].scan();sort(oj+1,oj+n+1);for(register int t=1;t<=n; ){data[++sz]=oj[t++];while(t<=n&&oj[t]==data[sz]) ++t,++data[sz].T;}cdq(1,sz);RP(t,1,sz) buk[data[t].ape]+=data[t].T;RP(t,0,n-1) printf("%d\n",buk[t]);return 0; }

轉(zhuǎn)載于:https://www.cnblogs.com/winlere/p/10490695.html

總結(jié)

以上是生活随笔為你收集整理的【题解】文体(划掉)陌上花开的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。