【BZOJ3489】A simple rmq problem（KD-Tree）

【BZOJ3489】A simple rmq problem（KD-Tree）

题面

BZOJ

题解

直接做肯定不好做，首先我们知道我们是一个二维平面数点，但是限制区间只能出现一次很不好办，那么我们给每个数记录一下和它相等的上一个位置和下一个位置，那么这两个位置的限定范围就在区间以外，于是变成了一个\(4\)维数点问题，直接\(KD-Tree\)了。

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
#define inf 1000000000
#define ls t[o].ch[0]
#define rs t[o].ch[1]
#define MAX 100100
inline int read()
{
    int x=0;bool t=false;char ch=getchar();
    while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();
    if(ch=='-')t=true,ch=getchar();
    while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();
    return t?-x:x;
}
int n,m,lt[MAX],b[MAX],rt,D;
struct Node{int d[4];}a[MAX];
struct KDNode{int mn[4],mx[4],ch[4];Node a;}t[MAX];
bool operator<(Node a,Node b){return a.d[D]<b.d[D];}
void cmin(int &x,int y){x=min(x,y);}
void cmax(int &x,int y){x=max(x,y);}
void pushup(int x,int y)
{
    for(int i=0;i<4;++i)
        cmin(t[x].mn[i],t[y].mn[i]),cmax(t[x].mx[i],t[y].mx[i]);
}
int Build(int l,int r,int nd)
{
    D=nd;int o=(l+r)>>1;nth_element(&a[l],&a[o],&a[r+1]);
    t[o].mn[0]=t[o].mx[0]=t[o].a.d[0]=a[o].d[0];
    t[o].mn[1]=t[o].mx[1]=t[o].a.d[1]=a[o].d[1];
    t[o].mn[2]=t[o].mx[2]=t[o].a.d[2]=a[o].d[2];
    t[o].mn[3]=t[o].mx[3]=t[o].a.d[3]=a[o].d[3];
    if(l<o)ls=Build(l,o-1,(nd+1)%4),pushup(o,ls);
    if(r>o)rs=Build(o+1,r,(nd+1)%4),pushup(o,rs);
    return o;
}
bool check(Node l,Node r,Node a)
{
    for(int i=0;i<4;++i)
        if(!(l.d[i]<=a.d[i]&&a.d[i]<=r.d[i]))
            return false;
    return true;
}
int ans;
Node L,R;
void Query(int o)
{
    for(int i=0;i<4;++i)if(t[o].mn[i]>R.d[i]||t[o].mx[i]<L.d[i])return;
    if(check(L,R,t[o].a))L.d[2]=max(L.d[2],t[o].a.d[2]);
    if(ls)Query(ls);if(rs)Query(rs);
}
int main()
{
    n=read();m=read();
    for(int i=1;i<=n;++i)
    {
        b[i]=read();
        a[i]=(Node){{lt[b[i]],i,b[i],0}};
        lt[b[i]]=i;
    }
    for(int i=1;i<=n;++i)lt[i]=n+1;
    for(int i=n;i>=1;--i)
    {
        a[i].d[3]=lt[b[i]];
        lt[b[i]]=i;
    }
    rt=Build(1,n,0);
    while(m--)
    {
        int l=(read()+ans)%n+1,r=(read()+ans)%n+1;
        if(l>r)swap(l,r);
        L=(Node){0,l,0,r+1};
        R=(Node){l-1,r,inf,n+1};
        Query(rt);
        printf("%d\n",ans=L.d[2]);
    }
    return 0;
}