萌新求助cdq分治做三维偏序
  • 板块CF12D Ball
  • 楼主BqtMtsZDnlpsT
  • 当前回复2
  • 已保存回复2
  • 发布时间2021/11/30 16:02
  • 上次更新2023/11/3 23:13:37
查看原帖
萌新求助cdq分治做三维偏序
185864
BqtMtsZDnlpsT楼主2021/11/30 16:02

WA on test 35.

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<queue>
#include<bitset>
#include<set>
#include<map>
#include<cmath>
#include<algorithm>
#define int long long
using namespace std;
//char cc[1<<21],*uu=cc,*vv=cc;
//#define getchar() (uu==vv&&(vv=(uu=cc)+fread(cc,1,1<<21,stdin),uu==vv)?EOF:*uu++)
inline int read(){
	char ch=getchar();int X=0;bool fl=0;
	while(ch<'0'||ch>'9'){if(ch=='-')fl=1;ch=getchar();}
	while(ch>='0'&&ch<='9'){X=(X<<1)+(X<<3)+ch-'0';ch=getchar();}
	if(fl)return ~(X-1);
	return X;
}
char buf[1<<21],ccc[20];
int pu,p2=-1;
void flush(){fwrite(buf,1,p2+1,stdout);p2=-1;}
void puc(char ch){buf[++p2]=ch;if(p2>1<<20)flush();}
void pus(const char *k,char ch=-1){
	for(int i=0;i<(int)strlen(k);i++)buf[++p2]=k[i];
	if(ch!=-1)buf[++p2]=ch;
	if(p2>1<<20)flush();
}
void write(int x,char ch=-1){
	if(x<0)buf[++p2]=45,x=-x;
	do{ccc[++pu]=(x%10)|48;}while(x/=10);do{buf[++p2]=ccc[pu];}while(--pu);
	if(ch!=-1)buf[++p2]=ch;
	if(p2>1<<20)flush();
}
int n,m,k;
struct N{
	int a,b,c,s,ans;
	bool operator!=(const N&U)const{
		return a!=U.a||b!=U.b||c!=U.c;
	}
}a[500005],tmp[500005];
struct BIT{
	int tr[500005],N;
	#define lowbit(x) (x&(-(x)))
	void clear(int _N){N=_N;for(int i=1;i<=_N;i++)tr[i]=0;}
	void add(int x,int d){
		for(;x<=N;x+=lowbit(x))tr[x]+=d;
	}
	int query(int x){
		int res=0;
		for(;x;x-=lowbit(x))res+=tr[x];
		return res;
	}
}t;
int v[500005],le,res[500005];
void CDQ(int l,int r){
	if(l==r)return;
	int mid=(l+r)>>1;
	CDQ(l,mid);CDQ(mid+1,r);
	sort(a+l,a+mid+1,[](N u,N v){return u.b<v.b||(u.b==v.b&&u.c>v.c);});
	sort(a+mid+1,a+r+1,[](N u,N v){return u.b<v.b||(u.b==v.b&&u.c>v.c);});
	le=0;
	for(int i=l;i<=r;i++)v[++le]=a[i].c;
	t.clear(le);
	sort(v+1,v+1+le);
	int j=l;
	for(int i=mid+1;i<=r;i++){
		while(a[j].b<a[i].b&&j<=mid){
			int p=lower_bound(v+1,v+1+le,a[j].c)-v;
			t.add(p,a[j].s);++j;
		}
		int p=lower_bound(v+1,v+1+le,a[i].c)-v;
		a[i].ans+=t.query(p-1);
//		cout<<a[i].a<<' '<<a[i].b<<' '<<a[i].c<<' '<<t.query(p-1)<<'\n';
	}
}
signed main(){
	m=read();t.clear(m);
	for(int i=1;i<=m;i++)tmp[i].a=-read();
	for(int i=1;i<=m;i++)tmp[i].b=-read();
	for(int i=1;i<=m;i++)tmp[i].c=-read(),tmp[i].s=tmp[i].ans=0;
	sort(tmp+1,tmp+1+m,[](N u,N v){return u.a<v.a||(u.a==v.a&&(u.b>v.b||(u.b==v.b&&u.c>v.c)));});
	int cnt=0;tmp[m+1]=(N){-1,-1,-1,-1,-1};
	for(int i=1;i<=m;i++){
		++cnt;
//		cout<<tmp[i].a<<' '<<tmp[i].b<<' '<<tmp[i].c<<'\n';
		if(tmp[i]!=tmp[i+1])a[++n]=tmp[i],a[n].s=cnt,cnt=0;
	}
	CDQ(1,n);
	int res=0;
	for(int i=1;i<=n;i++)
		if(a[i].ans>0)++res/*,cout<<a[i].a<<' '<<a[i].b<<' '<<a[i].c<<' '<<i<<' '<<a[i].ans<<'\n'*/;
	write(res,'\n');flush();
}

2021/11/30 16:02
加载中...