BZOJ 3489 A simple rmq problem

题目大意

给出一个长度为n的序列，给出m个询问：在[l,r]之间找到一个在这个区间里只出现过一次的数，并且要求找的这个数尽可能大。如果找不到这样的数，则直接输出0。强制在线。

K-Demention Tree，K维树是一种维护多维空间内点的一种数据结构，它是一颗二叉搜索树，每一层都按照一维进行排序，对于每一层的元素都满足：左子树的某维的值的大小＜根节点的某维的值的大小＜右子树的某维的值的大小。

具体方法就是：build(l,r,now)表示建立一棵K-D Tree,现在的维度是$now$,需要维护的区间为$[l,r]$.

使用一个STL函数nth_element(*l,*mid,*r),其作用就是将排序后应在$mid$位置的数放在那里并将比它小的放在它前面，比它大的放在它后面。

之后递归进行操作,build(l,mid-1,(now+1)%m),build(mid+1,r,(now+1)%m+1).

之后需要进行pushup()，维护该子树所表示的多维空间区域。

查询的时候就是二叉搜索树查询，树上二分即可；插入也是树上二分；删除是打delete标记，如果删除次数过多就进行一次重构。修改是先删除后插入。

在[l,r]里只出现一次等价于这个数上一次出现的位置$\lt l$, $l \le$这次出现的位置$\le r$，下一次出现的位置$\gt r$.用三维KDTree维护一下每个数出现的位置就可以了。

#include <cstdio>
#include <cctype>
#include <cstring>
#include <algorithm>
using namespace std;
#define R register
#define N 100000
int n,m,a[N+1],pre[N+1],bef[N+1],aft[N+1],LA,l,r,rt;
int sw;
struct node
{
    int v[3],mx[3],mn[3],ls,rs,as;
    bool operator<(const node &tg)const {return v[sw]<tg.v[sw];}
}p[N+1];
inline char nc()
{
    static char buf[100000],*p1,*p2;
    return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
inline int RI()
{
    R int ret=0;R char tmp=nc();
    while(!isdigit(tmp)) tmp=nc();
    while(isdigit(tmp)) ret=ret*10+(tmp^'0'),tmp=nc();
    return ret;
}
inline void Initiate()
{
    memset(aft,0x3f,sizeof aft);
    for(int i=1;i<=n;++i)
    {
        if(pre[a[i]]) aft[pre[a[i]]]=i,bef[i]=pre[a[i]];
        pre[a[i]]=i;
    }
    for(int i=1;i<=n;++i) p[i].v[0]=bef[i],p[i].v[1]=i,p[i].v[2]=aft[i];
}
inline void pushup(int pos)
{
    p[pos].mx[0]=max(max(p[p[pos].ls].mx[0],p[p[pos].rs].mx[0]),p[pos].v[0]);
    p[pos].mx[1]=max(max(p[p[pos].ls].mx[1],p[p[pos].rs].mx[1]),p[pos].v[1]);
    p[pos].mx[2]=max(max(p[p[pos].ls].mx[2],p[p[pos].rs].mx[2]),p[pos].v[2]);
    p[pos].mn[0]=min(min(p[p[pos].ls].mn[0],p[p[pos].rs].mn[0]),p[pos].v[0]);
    p[pos].mn[1]=min(min(p[p[pos].ls].mn[1],p[p[pos].rs].mn[1]),p[pos].v[1]);
    p[pos].mn[2]=min(min(p[p[pos].ls].mn[2],p[p[pos].rs].mn[2]),p[pos].v[2]);
    p[pos].as=max(max(p[p[pos].ls].as,p[p[pos].rs].as),a[p[pos].v[1]]);
}
int Build(int l,int r,int now)
{
    if(l>r) return 0;
    int mid=(l+r)>>1;
    sw=now;
    nth_element(p+l,p+mid,p+r+1);
    now=(now+1)%3;
    p[mid].ls=Build(l,mid-1,now);
    p[mid].rs=Build(mid+1,r,now);
    pushup(mid);
    return mid;
}
void Query(int pos)
{
    if(p[pos].as<LA) return;
    if(!pos||p[pos].mn[0]>=l||p[pos].mx[1]<l||p[pos].mn[1]>r||p[pos].mx[2]<=r) return;
    if(p[pos].mx[0]<l&&p[pos].mn[1]>=l&&p[pos].mx[1]<=r&&p[pos].mn[2]>r) {LA=max(LA,p[pos].as);return;}
    if(p[pos].v[0]<l&&p[pos].v[1]>=l&&p[pos].v[1]<=r&&p[pos].v[2]>r) LA=max(LA,a[p[pos].v[1]]);
    Query(p[pos].ls),Query(p[pos].rs);
}
int main()
{
    n=RI(),m=RI();
    for(int i=1;i<=n;++i) a[i]=RI();
    Initiate();
    p[0].mx[0]=p[0].mx[1]=p[0].mx[2]=-0x3f3f3f3f,p[0].mn[0]=p[0].mn[1]=p[0].mn[2]=0x3f3f3f3f;
    rt=Build(1,n,0);
    while(m--)
    {
        l=(RI()+LA)%n+1,r=(RI()+LA)%n+1;
        if(l>r) swap(l,r);
        LA=0;
        Query(rt);
        printf("%d\n",LA);
    }
    return 0;
}