洛谷3769[CH弱省胡策R2]TATT (KDTree)(四维LIS)

真是一个自闭的题目（调了一个上午+大半个下午）

从\(WA\)到\(WA+TLE\)到\(TLE\)到\(AC\)

真的艰辛。

首先，这个题，我们可以考虑直接上四维KDTree来解决。

对于kdtree上的每个节点，我们维护三个值，分别表示各个维度的\(mn\)，当前节点的\(val\)（这个是用来每次更新\(ans\)的），子树的\(val\)的最大值（用来做估价函数）

首先\(build\)出整个kdtree

void up(int root)

{

    for (int i=0;i<=3;i++)

    {

     if (t[root].l)

          t[root].mn[i]=min(t[root].mn[i],t[t[root].l].mn[i]);

        if (t[root].r)

          t[root].mn[i]=min(t[root].mn[i],t[t[root].r].mn[i]);

    }

    t[root].val=max(t[root].cao,max(t[t[root].l].val,t[t[root].r].val));

}

void build(int &x,int l,int r,int fa,int dd)

{

    ymh = dd;

    int mid = l+r >> 1;

    dd++;

    if (dd==4) dd=0;

    x = mid;

    nth_element(t+l,t+x,t+r+1);

    t[x].fa=fa;

    t[x].cao=0;

    for (int i=0;i<=3;i++) t[x].mn[i]=t[x].d[i];

    back[t[x].num]=x;

    if (l<x) build(t[x].l,l,mid-1,mid,dd);

    if (x<r) build(t[x].r,mid+1,r,mid,dd);

    up(x);

}

然后，我们用kdtree来维护一个做lis的过程

其中，我们先对所有点进行排序，然后依次枚举他们。

对于一次\(query\)，我们首先\(check\)一下当前点能不能更新\(ans\)，然后通过子树max来估价，判断先进入哪个子树，或者进不进入当前子树

bool get(KD a,KD b)

{

    for (int i=0;i<=3;i++)

      if (a.d[i]>b.d[i]) return 0;

    return 1;

}

int calc(int x,KD b)

{

    if (!x) return 0;

    for (int i=0;i<=3;i++)

      if (t[x].mn[i]>b.d[i]) return 0;

    return 1;

}

void query(int x,KD caonima,int dd)

{

    if (!x) return ;

   // cout<<x<<" "<<t[x].d[0]<<" "<<t[x].d[1]<<" "<<t[x].d[2]<<" "<<t[x].d[3]<<endl;

    //cout<<"*** "<<t[x].l<<" "<<t[x].r<<endl;

    int d1 = calc(t[x].l,now);

    int d2 = calc(t[x].r,now);

    int d=get(t[x],now);

    if (d && tmp<t[x].cao) tmp=t[x].cao;

    if (t[t[x].l].val>=t[t[x].r].val)

    {

        if (d1 && t[t[x].l].val>tmp) query(t[x].l,caonima,(dd+1)%4);

        if (d2 && t[t[x].r].val>tmp) query(t[x].r,caonima,(dd+1)%4);

    }

    else

    {

      if (d2 && t[t[x].r].val>tmp) query(t[x].r,caonima,(dd+1)%4);

      if (d1 && t[t[x].l].val>tmp) query(t[x].l,caonima,(dd+1)%4);

    }

}

下面是这个题的重点

就是因为\(lis\)，所以我们要修改当前点的\(val\)以及他子树内的\(val\)，为了下一个点的统计。

这里我们修改的方式是找到这个点对应的kdtree上的节点，然后不停的暴力向上跳。

我们首先把这个对应节点的\(val\)弄成这次我们\(query\)的答案+1，然后依次修改祖先们的子树\(max\)

void upp(int x)

{

    //t[x].val=max(t[x].val,t[x].cao);

    t[x].val=max(t[x].cao,max(t[t[x].l].val,t[t[x].r].val));

}

void update(int x,int pp)

{

    t[x].cao=pp;

    upp(x);

    x=t[x].fa;

    while (x)

    {

     //cout<<"****"<<t[x].d[0]<<" "<<t[x].d[1]<<" "<<t[x].d[2]<<" "<<t[x].d[3]<<endl;

        upp(x);

        x=t[x].fa;

    }

}

那么其实这个题就应该差不多了

不得不说细节真的是很多的qwq

具体还是看代码吧

kdtree真神奇！

// luogu-judger-enable-o2

// luogu-judger-enable-o2

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<cstring>

#include<cmath>

#include<queue>

#include<map>

#include<set>

#define mk makr_pair

#define ll long long

using namespace std;

inline int read()

{

  int x=0,f=1;char ch=getchar();

  while (!isdigit(ch)) {if (ch=='-') f=-1;ch=getchar();}

  while (isdigit(ch)) {x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}

  return x*f;

}

const int maxn = 2e5+1e2;

struct KD{

    int mn[4];

    int val;

    int l,r,fa;

    int d[4];

    int num;

    int cao;

};

KD t[maxn],now;

int a[maxn];

int n,m,root,ans,tmp,mval;

int back[maxn];

int ymh;

bool operator<(KD a,KD b)

{

    return a.d[ymh]<b.d[ymh];

}

void up(int root)

{

    for (int i=0;i<=3;i++)

    {

     if (t[root].l)

          t[root].mn[i]=min(t[root].mn[i],t[t[root].l].mn[i]);

        if (t[root].r)

          t[root].mn[i]=min(t[root].mn[i],t[t[root].r].mn[i]);

    }

    t[root].val=max(t[root].cao,max(t[t[root].l].val,t[t[root].r].val));

}

void build(int &x,int l,int r,int fa,int dd)

{

    ymh = dd;

    int mid = l+r >> 1;

    dd++;

    if (dd==4) dd=0;

    x = mid;

    nth_element(t+l,t+x,t+r+1);

    t[x].fa=fa;

    t[x].cao=0;

    for (int i=0;i<=3;i++) t[x].mn[i]=t[x].d[i];

    back[t[x].num]=x;

    if (l<x) build(t[x].l,l,mid-1,mid,dd);

    if (x<r) build(t[x].r,mid+1,r,mid,dd);

    up(x);

}

bool get(KD a,KD b)

{

    for (int i=0;i<=3;i++)

      if (a.d[i]>b.d[i]) return 0;

    return 1;

}

int calc(int x,KD b)

{

    if (!x) return 0;

    for (int i=0;i<=3;i++)

      if (t[x].mn[i]>b.d[i]) return 0;

    return 1;

}

void query(int x,KD caonima,int dd)

{

    if (!x) return ;

   // cout<<x<<" "<<t[x].d[0]<<" "<<t[x].d[1]<<" "<<t[x].d[2]<<" "<<t[x].d[3]<<endl;

    //cout<<"*** "<<t[x].l<<" "<<t[x].r<<endl;

    int d1 = calc(t[x].l,now);

    int d2 = calc(t[x].r,now);

    int d=get(t[x],now);

    if (d && tmp<t[x].cao) tmp=t[x].cao;

    if (t[t[x].l].val>=t[t[x].r].val)

    {

        if (d1 && t[t[x].l].val>tmp) query(t[x].l,caonima,(dd+1)%4);

        if (d2 && t[t[x].r].val>tmp) query(t[x].r,caonima,(dd+1)%4);

    }

    else

    {

      if (d2 && t[t[x].r].val>tmp) query(t[x].r,caonima,(dd+1)%4);

      if (d1 && t[t[x].l].val>tmp) query(t[x].l,caonima,(dd+1)%4);

    }

}

void upp(int x)

{

    //t[x].val=max(t[x].val,t[x].cao);

    t[x].val=max(t[x].cao,max(t[t[x].l].val,t[t[x].r].val));

}

void update(int x,int pp)

{

    t[x].cao=pp;

    upp(x);

    x=t[x].fa;

    while (x)

    {

     //cout<<"****"<<t[x].d[0]<<" "<<t[x].d[1]<<" "<<t[x].d[2]<<" "<<t[x].d[3]<<endl;

        upp(x);

        x=t[x].fa;

    }

}

bool cmp(int a,int b)

{

    for (int i=0;i<=3;i++)

      if (t[a].d[i]!=t[b].d[i]) return t[a].d[i]<t[b].d[i];

    return t[a].d[0]<t[b].d[0];

}

int main()

{

 // freopen("a.in","r",stdin);

 // freopen("a.out","w",stdout);

  n=read();

  for (int i=1;i<=n;i++)

  {

     for (int j=0;j<=3;j++) t[i].d[j]=read();

     a[i]=t[i].num=i;

  }

  build(root,1,n,0,0);

  sort(a+1,a+1+n,cmp);

  for (int i=1;i<=n;i++)

  {

    tmp=0;

    now = t[a[i]];

    //for (int j=0;j<=3;j++) cout<<t[a[i]].d[j]<<" ";

    //cout<<endl;

    query(root,now,0);

    ans=max(ans,tmp);

    update(back[now.num],tmp+1);//cout<<tmp<<endl;

    //cout<<endl;

  }

  cout<<t[root].val;

  return 0;

}

巴特西

洛谷3769[CH弱省胡策R2]TATT (KDTree)(四维LIS)

最新文章

热门文章