【题意】给你n个三元组 让你对每个三元组，找出每个元素都>=改三元组的数量,找出(x1,y1,z1)满足x1>=x,y1>=y,z1>=z
【题解】cdq分治。先对三元组按xyz升序排,x为第一关键字,y为第二关键字,z为第三关键字,然后进行分治,每次分治的时候,将[l,r]中的三元组复制出来,对[l,mid][mid+1,r]进行yz升序的sort,y为第一关键字,z为第二关键字,然后对于每一个tmp[i].y（mid+1<=i<=r)找出所有tmp[pos].y(l<=pos<=mid),使得tmp[pos].y<=tmp[i].y,并将tmp[pos].z插入一个树状数组中,然后在树状数组询问tmp[i].z就是当前三元组的答案的一部分了,因为首先[l,mid][mid+1,r]中我们是分开sort的,所以由于第一次sort的关系[l,mid]中的x关键字肯定是小于等于[mid+1,r]中的x关键字的,然后我们有每次之插入小于[l,mid]区间中y关键字小于当前三元组的y关键字的z关键字(有点绕),这样我们query肯定是答案的一部分,然后我们把区间多次二分、累加之后就是最终每个三元组的答案了
#include<set> #include<map> #include<cmath> #include<stack> #include<queue> #include<bitset> #include<vector> #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #define PB push_back #define MP make_pair #define ll __int64 #define MS(a,b) memset(a,b,sizeof(a)) #define LL (rt<<1) #define RR (rt<<1|1) #define lson l,mid,LL #define rson mid+1,r,RR #define pii pair<int,int> #define lowbit(x) (x&(-x)) using namespace std; const int MAXN=1e5+10; const int MBIT=1e5+10; const int inf=0x3f3f3f3f; const int mod=1e9+7; struct node { int id,x,y,z; }a[MAXN],tmp[MAXN]; int ans[MAXN]; int Bit[MBIT]; bool cmp1(node a,node b) { if(a.x!=b.x)return a.x<b.x; if(a.y!=b.y)return a.y<b.y; return a.z<b.z; } bool cmp2(node a,node b) { if(a.y!=b.y)return a.y<b.y; return a.z<b.z; } void add(int x,int y) { while(x<MBIT){Bit[x]+=y;x+=lowbit(x);} } void modify(int x) { while(x<MBIT){Bit[x]=0;x+=lowbit(x);} } int query(int x) { int sum=0; while(x>0){sum+=Bit[x];x-=lowbit(x);} return sum; } void solve(int l,int r) { int mid=(l+r)>>1; if(l==r)return; solve(l,mid); for(int i=l;i<=r;i++)tmp[i]=a[i]; sort(tmp+l,tmp+mid+1,cmp2); sort(tmp+mid+1,tmp+r+1,cmp2); int pos=l; for(int i=mid+1;i<=r;i++){ while(tmp[pos].y<=tmp[i].y&&pos<=mid)add(tmp[pos++].z,1); ans[tmp[i].id]+=query(tmp[i].z); } for(int i=l;i<=mid;i++)modify(tmp[i].z); solve(mid+1,r); } int main() { int T,n; scanf("%d",&T); while(T--){ MS(Bit,0); scanf("%d",&n); for(int i=0;i<n;i++) scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].z),a[i].id=i,ans[i]=0; sort(a,a+n,cmp1); solve(0,n-1); for(int i=n-2;i>=0;i--) if(a[i].x==a[i+1].x&&a[i].y==a[i+1].y&&a[i].z==a[i+1].z) ans[a[i].id]=ans[a[i+1].id]; for(int i=0;i<n;i++)printf("%d\n",ans[i]); } return 0; }