stars

題目大意：
在一個三維空間當中，每次進行一個操作，添加一個點或者統計空間中的某一個長方體范圍內的所有點

三維空間中我們用兩個點即可確定一個長方體。

首先效仿平面二維數點的方法，根據容斥原理可以把詢問拆分成8個以原點$O(0,0,0)$為一個頂點長方體的內部點的數量，像這樣的長方體可以用一個坐標$(x,y,z)$表示

假設當前有一個點在$t_0$時刻插入位置為$(x_0,y_0,z_0)$，如果這個點在$t$時刻一個以原點為一個端點的長方體$(x,y,z)$內部條件：$$t_0<t,x_0\le x,y_0\le y,z_0\le z$$
由上面條件不難看出是一個4維偏序問題。
對于3維偏序三維偏序（陌上花開）只需要用cdq分治+樹狀數組即可解決，當然同樣可以用cdq分治套cdq分治解決（強烈建議寫此題前，用cdq套cdq寫一下三維偏序（陌上花開））

4維偏序只需要 cdq套cdq+樹狀數組

注意需要對z進行離散化

#include<cstring> #include<iostream> #include<algorithm> using namespace std; constexpr int N=50010; struct node {int op;int x,y,z;int sign,id;int part; }q[8*N]; int n,nn,cnt; int b[2*N],c[N]; int ans[N]; int fw[2*N]; int lowbit(int x){return x&-x;} void update(int k,int x){for(;k<=nn;k+=lowbit(k)) fw[k]+=x;} int query(int k){int res=0;for(;k;k-=lowbit(k)) res+=fw[k];return res;}void cdq(int l,int r) {if(l>=r) return;int mid=l+r>>1;cdq(l,mid),cdq(mid+1,r);int i=l;for(int j=mid+1;j<=r;j++){while(i<=mid&&q[i].y<=q[j].y){if(q[i].op==0&&q[i].part==0) update(q[i].z,1);i++;}if(q[j].op==1&&q[j].part==1) ans[q[j].id]+=q[j].sign*query(q[j].z);}while(i>l) {i--;if(q[i].op==0&&q[i].part==0) update(q[i].z,-1);}inplace_merge(q+l,q+mid+1,q+r+1,[](const node&a,const node&b){return a.y<b.y;});} void solve(int l,int r) {if(l>=r) return;int mid=l+r>>1;solve(l,mid),solve(mid+1,r);for(int i=l;i<=mid;i++) q[i].part=0;for(int i=mid+1;i<=r;i++) q[i].part=1;stable_sort(q+l,q+r+1,[](const node&a,const node&b){return a.x<b.x;});cdq(l,r); } int main() {ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);int T;cin>>T;while(T--){cin>>n;cnt=nn=0;for(int i=1;i<=n;i++) ans[i]=0,c[i]=0;for(int i=1;i<=n;i++){int op;cin>>op;if(op==1){int x,y,z;cin>>x>>y>>z;q[++cnt]={0,x,y,z};b[++nn]=z;}else{c[i]=1;int x1,y1,z1,x2,y2,z2;cin>>x1>>y1>>z1>>x2>>y2>>z2;q[++cnt]={1,x2,y2,z2,1,i};q[++cnt]={1,x1-1,y2,z2,-1,i};q[++cnt]={1,x2,y1-1,z2,-1,i};q[++cnt]={1,x2,y2,z1-1,-1,i};q[++cnt]={1,x1-1,y1-1,z2,1,i};q[++cnt]={1,x1-1,y2,z1-1,1,i};q[++cnt]={1,x2,y1-1,z1-1,1,i};q[++cnt]={1,x1-1,y1-1,z1-1,-1,i};b[++nn]=z1-1;b[++nn]=z2;}}sort(b+1,b+1+nn);nn=unique(b+1,b+1+nn)-b-1;for(int i=1;i<=cnt;i++) q[i].z=lower_bound(b+1,b+1+nn,q[i].z)-b;solve(1,cnt);for(int i=1;i<=n;i++)if(c[i]) cout<<ans[i]<<'\n';}return 0; }

感覺網上此題的題解都好久遠，難道沒人水水這題嗎？？？
1A非常開心，要加油哦~

總結

以上是生活随笔為你收集整理的HDU5126 stars（4维偏序-＞cdq套cdq+树状数组）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。