【kd-tree】bzoj3489 A simple rmq problem-白红宇

【kd-tree】bzoj3489 A simple rmq problem

阅读量：5940 次

发布时间：2019-06-19

本文共 2452 字，大约阅读时间需要 8 分钟。

Orz zyf教给蒟蒻做法

　　蒟蒻并不会这题正解……（可持久化树套树？。。。Orz

　　对于每个点，我们可以求出pre[i],nex[i]，那么询问的答案就是：求max (a[i])，其中 i 满足

　　然后我们以(i,pre[i],nex[i])为坐标……将所有点抽象到三维空间中，每次查询就相当于是一次区域求最值！

这题我的感受：

因为前面做了两道区域求和的……然后思路不由自主又代入到搞【子树最大值】来更新答案……然而忘记了单点更新，也就是：虽然这个子树不合法，但是这一个点(根)还是可能合法的……

然后就是：KD-Tree如果可以搞整个子树的话，那么用整个子树的最值去更新，会优化很多……？

终于1A了一道KD-Tree啦~好开心（虽然不是自己想出的做法……）

——http://www.cnblogs.com/Tunix/p/4522925.html

#include
     
      #include
      
       #include
       
        using namespace std;#define N 100001#define INF 2147483647#define KD 3//Î¬¶ÈÊýint qp[2];int n,root,m;int dn;struct Node{    int minn[KD],maxx[KD],p[KD],w,maxv;    int ch[2];    void Init()      {        for(int i=0;i
        
         >1);    nth_element(T+l,T+m,T+r+1);    T[m].Init();    if(l!=m) T[m].ch[0]=Buildtree(l,m-1,(d+1)%KD);    if(m!=r) T[m].ch[1]=Buildtree(m+1,r,(d+1)%KD);    Update(m);    return m;}int ans;void Query(int rt=root){    if(T[rt].p[0] < qp[0] &&    T[rt].p[1] > qp[1] &&    qp[0] <= T[rt].p[2]  && T[rt].p[2] <= qp[1])      ans=max(ans,T[rt].w);    for(int i=0;i<2;++i)      if(T[rt].ch[i] &&      T[T[rt].ch[i]].minn[0] < qp[0] &&      T[T[rt].ch[i]].maxx[1] > qp[1] &&      qp[0] <= T[T[rt].ch[i]].maxx[2] && T[T[rt].ch[i]].minn[2] <= qp[1])        {          if(T[T[rt].ch[i]].maxx[0] < qp[0] &&          T[T[rt].ch[i]].minn[1] > qp[1] &&          qp[0] <= T[T[rt].ch[i]].minn[2] && T[T[rt].ch[i]].maxx[2] <= qp[1])            ans=max(ans,T[T[rt].ch[i]].maxv);          else if(T[T[rt].ch[i]].maxv > ans)            Query(T[rt].ch[i]);        }}int nex[N],pre[N],now[N];int main(){//  freopen("bzoj3489.in","r",stdin);//  freopen("bzoj3489.out","w",stdout);    scanf("%d%d",&n,&m);    for(int i=1;i<=n;++i)      scanf("%d",&T[i].w);    for(int i=1;i<=n;++i)      {        pre[i]=now[T[i].w];        now[T[i].w]=i;      }    for(int i=1;i<=n;++i)      now[i]=n+1;    for(int i=n;i;--i)      {        nex[i]=now[T[i].w];        now[T[i].w]=i;      }    for(int i=1;i<=n;++i)      {        T[i].p[0]=pre[i];        T[i].p[1]=nex[i];        T[i].p[2]=i;      }    Buildtree();    root=(1+n>>1);    int x,y;    for(;m;--m)      {        scanf("%d%d",&x,&y);        qp[0]=min((x+ans)%n+1,(y+ans)%n+1);        qp[1]=max((x+ans)%n+1,(y+ans)%n+1);//        qp[0]=x;//        qp[1]=y;        ans=0;        Query();        printf("%d\n",ans);      }    return 0;}