【bzoj3489】 A simple rmq problem k-d树

由于某些原因，我先打了一个错误的树套树，后来打起了$k-d$。接着因不明原因在思路上被卡了很久，在今天中午蹲坑时恍然大悟......

对于一个数字$a_i$，我们可以用一组三维坐标$(i,pre,nxt)$来表示，其中$i$表示该数字下标，$pre$表示在区间$[1,i)$中满足$a[j]=a[i]$的最大$j$，若不存在，则$pre=0$。$nxt$表示在区间$(i,n]$中满足$a[j]=a[i]$的最小$j$，若不存在，则$nxt=n+1$。

接着我们种一棵3-d树去存储这n个点。对于任意一个节点，需存储该节点的数字，以该节点为根的字数中最大的数字，每一维的最小值和最大值。对于一组询问$[l,r]$，答案即为满足第一维在区间$[l,r]$，第二维在区间$[0,l)$，第三维在区间$(r,n+1)$中的所有点上的最大数字。在查询时，直接按照$k-d$的正常查询策略更新答案即可。

时间复杂度:$O(n log n+n^\frac{5}{3})$

警告：若采用此方法，此题建议各位加一个微小的剪枝：假定当前所得到的最大答案为$ans$，若当前访问的字树中最大答案$≤ans$，直接跳过这棵字树即可。（借助该方法极限数据耗时从17.5s降低至1.4s）

 #include<bits/stdc++.h>

 #define M 210000

 using namespace std;

 int n,m,D,root;

 struct kd{

     int a[],max[],min[],now,ans,l,r;

     kd(){a[]=a[]=a[]=now=l=r=;min[]=min[]=min[]=;}

     kd(int xx,int yy,int zz,int kk){a[]=xx;a[]=yy;a[]=zz;now=kk;}

     friend bool operator <(kd a,kd b){

         return a.a[D]<b.a[D];

     }

 }a[M];

 void upd(kd &x,kd &y){

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

         x.max[i]=max(x.max[i],y.max[i]),

         x.min[i]=min(x.min[i],y.min[i]);

 }

 inline int nx(int d){if(d==) return ; return d+;}

 void build(int &x,int l,int r,int d){

     if(l>r) return; int mid=(l+r)>>;

     D=d; nth_element(a+l,a+mid,a+r+); x=mid;

     for(int i=;i<;i++) a[x].max[i]=a[x].min[i]=a[x].a[i];

     build(a[x].l,l,mid-,nx(d));

     build(a[x].r,mid+,r,nx(d));

     upd(a[x],a[a[x].l]); upd(a[x],a[a[x].r]);

     a[x].ans=max(a[x].now,max(a[a[x].l].ans,a[a[x].r].ans));

 }

 int ans=;

 void query(int x,int l,int r){

     if(x==||ans>=a[x].ans||r<a[x].min[]||a[x].max[]<l||l-<a[x].min[]||a[x].max[]<r+) return;

     if(l<=a[x].min[]&&a[x].max[]<=r&&a[x].max[]<l&&r<a[x].min[])

     {ans=max(ans,a[x].ans); return;}

     if(l<=a[x].a[]&&a[x].a[]<=r&&a[x].a[]<l&&r<a[x].a[]) ans=max(ans,a[x].now);

     query(a[x].l,l,r); query(a[x].r,l,r);

 }

 int last[M]={};

 int main(){

     scanf("%d%d",&n,&m);

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

         int x; scanf("%d",&x);

         a[i].a[]=i; a[i].now=x;

         a[i].a[]=last[x];

         a[last[x]].a[]=i;

         last[x]=i;

     }

     for(int i=;i<=n;i++) if(a[i].a[]==) a[i].a[]=n+;

     build(root,,n,);

     while(m--){

         int x,y,l,r; scanf("%d%d",&x,&y);

         l=(x+ans)%n+; r=(y+ans)%n+; if(l>r) swap(l,r);

         ans=; query(root,l,r);

         printf("%d\n",ans);

     }

 }

巴特西

【bzoj3489】 A simple rmq problem k-d树

最新文章

热门文章