The three dimensional partial order

There are NNN elements, and each element pip_IPi has three attributes ai, BI, CIa_i, B_i,c_iai,bi,ci, Find the number of point pairs (I,j)(I,j)(I,j) satisfying ai≤aja_i\leq a_jai≤ AJ and BI ≤ bjb_I \leq b_jbi≤ BJ and CI ≤ CJc_i \leq c_jCI ≤cj.

CDQ partition

One dimensional sort, two dimensional divide-and-conquer, three dimensional BIT. First, the sequence is sorted by ai, BI, CIa_i,b_i, C_iai,bi and CI as the first, second and third keywords respectively, and then CDQ partition and rule is performed on the obtained sequence. Now deal with the interal (l, r) (l, r) (l, r), intermediate point mid = (l + r) > > 1 mid = (l + r) > > 1 mid = (l + r) > > 1. Because I’ve been sorted by aiA_iAI, So now we just need to query how many elements satisfy bi≤bj ci≤ cjB_i \leq b_j\ \ c_i\leq c_jBI ≤ BJ CI ≤cj (where I ∈ [l, mid], j ∈ (mids + 1, r] I \ [l, mid], in j \ [mid + 1, r] in the I ∈ [l, mid], j ∈ / mid + 1, r). The left and right intervals are sorted by bi, CIb_i, C_ibi and CI as the first and second keywords respectively. Bib_ibi is strictly non-regressive within the left and right interval. Define two Pointers I,ji,ji,j to refer to the left interval and the right interval respectively. I scan the left and right interval, moving I,ji,ji,j back. If there is bi≤bjb_i\leq b_jbi≤bj, the answer can be directly maintained with all the elements KKK that appeared previously (KKK satisfies ck≤ CJC_k \leq c_jck≤cj). Consider tree array optimization, time complexity O(nlog^2n)O(nlog ^2n)O(nlog2n).

sample

Bzoj blooms on strangers

Answer key

Require flower JJJ grade. That is, find the number of flowers that satisfy ai≤aj,bi≤bj, CI ≤ Cja_i \leq A_j, B_I \leq b_j,c_i\leq c_jai≤ AJ, BI ≤ BJ, CI ≤cj. It’s a naked three dimensional partial order.

duplicate removal

Suppose there are WWW elements with equal value of three attributes, and the grade of each flower is equal to the number of flowers smaller than it in three dimensions plus W − 1W-1W −1. However, in the process of CDQ divide and conquer, only the contribution of the left element to the right is calculated, which leads to different grades of the same flower. So you can pre-process all the same flowers before you divide and conquer, count them, and treat them as one flower. Add the total number of flowers when maintaining the answer with BIT.

code

#include<bits/stdc++.h>
#definerep(i,st,ed) for(int i=st; i<=ed; ++i)
#define lb x&-x
using namespace std;
const int N=1E5+10;
struct Node{
	int x,y,z,num,ans;
}p[N],a[N];
int n,k,tot;
int anss[2*N],t[2*N];
inline int read(a)
{
	int ret=0,flag=1;char ch=getchar(a);while(ch<'0' || ch>'9')
	{
		if(ch==The '-')flag=- 1;
		ch=getchar(a); }while(ch>='0' && ch<='9')ret=ret*10+ch-'0',ch=getchar(a);return ret*flag;
}
bool cmpx(const Node &a,const Node &b)
{
	if(a.x==b.x)
	{
		if(a.y==b.y)
			return a.z<b.z;
		return a.y<b.y;
	}
	return a.x<b.x;
}
bool cmpy(const Node &a,const Node &b)
{
	if(a.y==b.y)
		return a.z<b.z;
	return a.y<b.y;
}
void add(int x,int val)
{
	while(x<=k) { t[x]+=val; x+=lb; }}int query(int x)
{
	int ret=0;
	while(x)
	{
		ret+=t[x];
		x-=lb;
	}
	return ret;
}
void solve(int l,int r)
{
	if(l==r)
		return;
	int mid=(l+r)>>1;
	solve(l,mid);solve(mid+1,r);
	sort(a+l,a+mid+1,cmpy);
	sort(a+mid+1,a+r+1,cmpy);
	int ind=l;
	rep(i,mid+1,r)
	{
		while(ind<=mid && a[ind].y<=a[i].y)
		{
			add(a[ind].z,a[ind].num);
			++ind;
		}
		a[i].ans+=query(a[i].z);
	}
	rep(i,l,ind- 1)
		add(a[i].z,-a[i].num);
}
void print(a)
{
	rep(i,1,tot)
	{
		printf("%d %d %d %d\n",a[i].x,a[i].y,a[i].z,a[i].num); }}int main(a)
{
	n=read(a); k=read(a);rep(i,1,n)
	{
		p[i].x=read(a); p[i].y=read(a); p[i].z=read(a); }sort(p+1,p+n+1,cmpx);
	Node now=p[1];
	int cnt=0;
	rep(i,1,n) 
	{
		++cnt;
		Node nxt=p[i+1];
		if(nxt.x! =now.x || nxt.y! =now.y || nxt.z! =now.z) { a[++tot]=now; a[tot].num=cnt; cnt=0;
		}
		now=nxt;
	}
//	print();
	solve(1,tot);
	rep(i,1,tot)
	{
		anss[a[i].ans+a[i].num- 1]+=a[i].num;
	}
	rep(i,0,n- 1) { cout<<anss[i]<<endl; }}Copy the code