Topic link

Train of thought

CDQ divide and conquer naked question. First, the three attribute values are discretized for CDQ divide-and-conquer. Let a[I].diea[I].diea[I].die be the number of persons capable of killing the third person, that is, the number of JJJ such that xj>xi,yj>yi,zj>zix_j>x_i,y_j>y_i,z_j>z_ixj>xi,yj>yi,zj>zi, If a[I].die>0a[I].die>0a[I].die>0, the third person is killed. In fact, xi=xj,yj>yi, Zj >zix_i=x_j,y_j>y_i, Z_j > z_Ixi = Xj,yj>yi,zj>zi exist in the solved answers. (In the process of partition and conquer, it is not guaranteed that the minimum value of the left interval XXX is strictly greater than the maximum value of the left interval. There are cases where the two are equal), so subtract those cases extra.

First, sort x,y,zx,y,zx,y, y,z as the first, second and third keywords respectively, consider a certain segment [L,r][L,r][L,r] with the same XXX value separately. That is, the number of JJJ of yj>yi,zj>ziy_j>y_i,z_j>z_iyj>yi,zj>zi for all iii in this paragraph, and the tree array optimization is used in the process of finding. In addition, if x, YX,yx, and y are all equal, they need to maintain the answer together, and they need to maintain the answer together in the tree array, otherwise they’re going to count each other’s contributions.

This one uses longlong to solve T. /kk

code

#include<bits/stdc++.h>
#define lb(x) x&-x
#definerep(i,st,ed) for(int i=st; i<=ed; ++i)
#definebl(u,i) for(int i=head[u]; i; i=e[i].nxt)
#define LLM LONG_LONG_MAX
#define LLm LONG_LONG_MIN
#define pii pair<ll,ll> 
typedef int ll;
typedef double db;
using namespace std;
const ll INF=0x3f3f3f3f;
void read(a) {}
void say(a) {}
void say_(a) {}
template <typename T, typename. T2>inline void read(T &_, T2 &... oth)
{
    int__ =0; _ =0;
    char ch=getchar(a);while(!isdigit(ch))
    {
        if(ch==The '-') __ =1;
        ch=getchar(a); }while(isdigit(ch))
    {
        _=_*10+ch- 48;
        ch=getchar(a); } _ = __? - _ : _;read(oth...) ; }template <typename T>
void Out(T _)
{
    if(_ <0)
    {
        putchar(The '-'); _ = - _; }if(_ > =10)
       Out(_ /10);
    putchar(_ %10+'0');
}
template <typename T, typename. T2>inline void say(T _, T2... oth)
{
	Out(_).putchar('\n');
	say(oth...) ; }template <typename T, typename. T2>inline void say_(T _, T2... oth)
{
	Out(_).putchar(' ');
	say_(oth...) ; }/ * # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # * /
const ll N=5E5+10;
ll n,m,ans;
ll t[N],vx[N],vy[N],vz[N];
struct Node{
	ll x,y,z,die;
	void pt(a)
	{
		say_(x,y,z,die);
		puts("");
	}
}a[N];
void add(ll x,ll val)
{
	while(x<=m)
	{
		t[x]+=val;
		x+=lb(x); }}ll query(ll x)
{
	ll ret=0;
	while(x)
	{
		ret+=t[x];
		x-=lb(x);
	}
	return ret;
}
void cdq(ll l,ll r)
{
	if(l==r)
		return;
	ll mid=(l+r)>>1;
	cdq(l,mid);
	cdq(mid+1,r);
	sort(a+l,a+mid+1[] (const Node &u,const Node &v)
	{
		if(u.y==v.y)
			return u.z>v.z;
		return u.y>v.y;
	});
	sort(a+mid+1,a+r+1[] (const Node &u,const Node &v)
	{
		if(u.y==v.y)
			return u.z>v.z;
		return u.y>v.y;
	});
	ll ind=l;
	rep(i,mid+1,r)
	{
		while(ind<=mid && a[ind].y>a[i].y)
		{
			add(a[ind].z,1);
			++ind;
		}
		a[i].die+=query(m)-query(a[i].z);
	}
	rep(i,l,ind- 1)
		add(a[i].z,- 1);
}
void print(a)
{}int main(a)
{
	read(n);
	rep(i,1,n)
	{
		read(a[i].x);
		vx[i]=a[i].x;
	}
	rep(i,1,n)
	{
		read(a[i].y);
		vy[i]=a[i].y;
	}
	rep(i,1,n)
	{
		read(a[i].z);
		vz[i]=a[i].z;
	}
	sort(vx+1,vx+n+1);
	ll nx=unique(vx+1,vx+n+1)-vx- 1;
	sort(vy+1,vy+n+1);
	ll ny=unique(vy+1,vy+n+1)-vy- 1;
	sort(vz+1,vz+n+1);
	ll nz=unique(vz+1,vz+n+1)-vz- 1;
	m=nz;
	rep(i,1,n)
	{
		a[i].x=lower_bound(vx+1,vx+nx+1,a[i].x)-vx;
		a[i].y=lower_bound(vy+1,vy+ny+1,a[i].y)-vy;
		a[i].z=lower_bound(vz+1,vz+nz+1,a[i].z)-vz;
	}
	sort(a+1,a+n+1[] (const Node &u,const Node &v)
	{
		if(u.x==v.x)
		{
			if(u.y==v.y)
				return u.z>v.z;
			return u.y>v.y;
		}
		return u.x>v.x;
	});
	ll l=1,r=0;
	while(l<=n)
	{
		while(r<n && a[r+1].x==a[l].x)
			++r;
		rep(i,l,r)
		{
			ll ind=i;
			while(ind<r && a[i].y==a[ind+1].y)
				++ind;
			rep(j,i,ind)
				a[j].die-=query(m)-query(a[j].z);
			rep(j,i,ind)
				add(a[j].z,1);
			i=ind;
		}
		rep(i,l,r)
			add(a[i].z,- 1);
		l=r+1;
	}
	cdq(1,n);
	rep(i,1,n)
		ans+=a[i].die>0?1:0;
	//print();
	say(ans);
}
Copy the code