洛谷P3810 【模板】三维偏序(陌上花开)
程序员文章站
2022-05-14 18:41:27
...
题解:
这题我看没有树的题解,我就来一发
三维树应该是过不了的,我T掉了5个点
我们可以把排序,和用树维护,每次计算当前位置前面有多少个和符合条件(均小于当前位置的和)
但是,这实际上是错误的,当一些相等时,要查询的范围可能在当前位置之后,于是,我们可以建两棵树,分别维护,然后就大功告成了,时间复杂度
标程:
//T维护在当前位置前,有多少个x和y符合条件
//K维护所有z值相等的点中,有多少个x和y符合条件
#include<cstdio>
#include<algorithm>
using namespace std;
const int N=100002;
int n,m,ans,D,i,f[N],k,j,t;
inline char gc(){
static char buf[100000],*p1=buf,*p2=buf;
return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
#define gc getchar
inline int read(){
int x=0,fl=1;char ch=gc();
for (;ch<48||ch>57;ch=gc())if(ch=='-')fl=-1;
for (;48<=ch&&ch<=57;ch=gc())x=(x<<3)+(x<<1)+(ch^48);
return x*fl;
}
inline void wri(int a){if(a>=10)wri(a/10);putchar(a%10|48);}
inline void wln(int a){if(a<0)a=-a,putchar('-');wri(a);puts("");}
inline void Min(int &x,int y){if (y<x) x=y;}
inline void Max(int &x,int y){if (y>x) x=y;}
struct kk{
int x,y,z;
}a[N];
struct P{
int l,r,d[2],mn[2],mx[2],v,sum;
int &operator[](int x){
return d[x];
}
friend bool operator==(P a,P b){
return a.d[0]==b.d[0] && a.d[1]==b.d[1];
}
friend bool operator<(P a,P b){
return a[D]<b[D];
}
}p[N];
bool in(int x1,int y1,int x2,int y2,int X1,int Y1,int X2,int Y2){
return x1<=X1 && X2<=x2 && y1<=Y1 && Y2<=y2;
}
bool out(int x1,int y1,int x2,int y2,int X1,int Y1,int X2,int Y2){
return X2<x1 || X1>x2 || Y2<y1 || Y1>y2;
}
struct node{
P now,t[N];
int rt,cnt;
void update(int k){
int l=t[k].l,r=t[k].r;
for (int i=0;i<2;i++){
t[k].mn[i]=t[k].mx[i]=t[k][i];
if (l) Min(t[k].mn[i],t[l].mn[i]),Max(t[k].mx[i],t[l].mx[i]);
if (r) Min(t[k].mn[i],t[r].mn[i]),Max(t[k].mx[i],t[r].mx[i]);
}
t[k].sum=t[k].v+t[l].sum+t[r].sum;
}
void ins(int &k,bool D){
if (!k){
k=++cnt;
t[k][0]=t[k].mn[0]=t[k].mx[0]=now[0];
t[k][1]=t[k].mn[1]=t[k].mx[1]=now[1];
}
if (now==t[k]){
t[k].v+=now.v;t[k].sum+=now.v;
return;
}
if (now[D]<t[k][D]) ins(t[k].l,D^1);
else ins(t[k].r,D^1);
update(k);
}
int query(int k,int x1,int y1,int x2,int y2){
if (!k) return 0;
int tmp=0;
if (in(x1,y1,x2,y2,t[k].mn[0],t[k].mn[1],t[k].mx[0],t[k].mx[1])) return t[k].sum;
if (out(x1,y1,x2,y2,t[k].mn[0],t[k].mn[1],t[k].mx[0],t[k].mx[1])) return 0;
if (in(x1,y1,x2,y2,t[k][0],t[k][1],t[k][0],t[k][1])) tmp+=t[k].v;
tmp+=query(t[k].l,x1,y1,x2,y2)+query(t[k].r,x1,y1,x2,y2);
return tmp;
}
int build(int l,int r,bool f){
if (l>r) return 0;
int mid=l+r>>1;
D=f;nth_element(p+l,p+mid,p+r+1);
t[mid]=p[mid];
t[mid].l=build(l,mid-1,f^1);
t[mid].r=build(mid+1,r,f^1);
update(mid);
return mid;
}
}T,K;
bool cmp(kk a,kk b){
return a.z<b.z;
}
int main(){
n=read();k=read();m=10000;
for (i=1;i<=n;i++) a[i].x=read(),a[i].y=read(),a[i].z=read();
sort(a+1,a+n+1,cmp);
for (i=1;i<=n;i++){
k=i;
while (k<n && a[k].z==a[k+1].z) k++;
for (j=i;j<=k;j++) p[j-i+1][0]=a[j].x,p[j-i+1][1]=a[j].y,p[j-i+1].v=p[j-i+1].sum=1;
K.rt=K.build(1,k-i+1,0);
for (j=i;j<=k;j++){
ans=T.query(T.rt,1,1,a[j].x,a[j].y)+K.query(K.rt,1,1,a[j].x,a[j].y);
f[ans]++;//把当前位置也算进去了,所以f的输出范围是[1,n]
}
for (j=i;j<=k;j++){
T.now[0]=a[j].x,T.now[1]=a[j].y,T.now.v=T.now.sum=1,T.ins(T.rt,0);
if (T.cnt==m){
for (t=1;t<=T.cnt;t++) p[t]=T.t[t];
T.rt=T.build(1,T.cnt,0);m+=10000;
}
}
i=k;
}
for (i=1;i<=n;i++) wln(f[i]);
}
推荐阅读
-
陌上花开 HYSBZ - 3262 三维偏序问题 CDQ分治+树状数组
-
BZOJ 3262: 陌上花开 (cdq分治,三维偏序)
-
bzoj 3262 :陌上花开 (cdq分治 三维偏序)
-
【bzoj3262】陌上花开(cdq分治解决三维偏序问题)一些总结
-
BZOJ - 3262 陌上花开 CDQ分治 三维偏序
-
BZOJ3262: 陌上花开【三维偏序】
-
BZOJ 3262 陌上花开 三维偏序,CDQ分治
-
三维偏序(陌上花开)---洛谷P3810&&BZOJ3262(cdq分治--归并排序+树状数组)
-
P3810 -三维偏序(陌上花开)cdq-分治
-
Luogu P3810 【模板】三维偏序(陌上花开) CDQ分治 树状数组