[bzoj3489]A simple rmq problem

kd-tree

题面

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

• $n\leq10^5,m\leq2*10^5,a_i\leq n$

解析

只出现过一次，就是上一次出现在位置$l$之前，下一次出现在位置$r$之后。
这个有点像三维偏序，但这里有一维是区间啊。
树套树续一下应该能过。

然而，对于维数较高的范围计数问题，$kd-tree$是更佳选择。
其复杂度稳定$O(kn^{1-\frac{1}{k}})$（$k$为维数），而且空间线性。

一般框架：

• 如果当前节点存的点被询问范围包括,用这个点贡献答案
• 如果当前节点的范围完全被询问范围包括,直接用整个节点贡献答案
• 如果当前节点的范围(一个超立方体)和询问范围没有交,返回
• 否则,递归进入左右儿子

对一个新加入的点，先自己更新自己的范围，再用儿子更新自己的范围。

把上一次，这一次，下一次这个数出现的位置看作三个维度就可以了。

#include<iostream>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#define ll long long
#define re register
#define il inline
#define ls t[k].l
#define rs t[k].r
#define fp(i,a,b) for(re int i=a;i<=b;i++)
#define fq(i,a,b) for(re int i=a;i>=b;i--)
using namespace std;
const int N=2e5+100;
int n,m,b[N],R[N],L[N],now,app[N],rt,ans;
il ll gi()
{
  re ll x=0,t=1;
  re char ch=getchar();
  while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
  if(ch=='-') t=-1,ch=getchar();
  while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();
  return x*t;
}
il void cmin(re int &x,re int y){x=min(x,y);}
il void cmax(re int &x,re int y){x=max(x,y);}
struct dat
{
  int d[3],w,max;
  il bool operator < (const dat &o) const{return d[now]<o.d[now];}
}a[N];
struct node
{
  dat a;
  int l,r,mn[3],mx[3];
}t[N];
struct kd_tree
{
  il void upd(re int k,re int p)
  {
    fp(i,0,2) cmin(t[k].mn[i],t[p].mn[i]),cmax(t[k].mx[i],t[p].mx[i]);
    t[k].a.max=max(t[k].a.max,t[p].a.max);
  }
  il void pushup(re int k)
  {
    fp(i,0,2) t[k].mn[i]=t[k].mx[i]=t[k].a.d[i];
    if(ls) upd(k,ls);if(rs) upd(k,rs);
  }
  il void Build(re int &k,re int l,re int r,re int tag)
  {
    re int mid=l+r>>1;now=tag;
    nth_element(a+l,a+mid,a+r+1);k=mid;
    t[k].a=a[mid];
    if(l<mid) Build(ls,l,mid-1,(tag+1)%3);else ls=0;
    if(mid<r) Build(rs,mid+1,r,(tag+2)%3);else rs=0;
    pushup(k);
  }
  il void Query(re int k,re int l,re int r)
  {
    if(!k||t[k].a.max<ans) return;
    if(t[k].a.d[1]>=l&&t[k].a.d[1]<=r&&t[k].a.d[0]<l&&t[k].a.d[2]>r) ans=max(ans,t[k].a.w);
    if(t[k].mn[1]>=l&&t[k].mx[1]<=r&&t[k].mx[0]<l&&t[k].mn[2]>r) ans=max(ans,t[k].a.max);
    if(t[k].mn[1]>r||t[k].mx[1]<l||t[k].mn[0]>=l||t[k].mx[2]<=r) return;
    Query(ls,l,r);Query(rs,l,r);
  }
}kd;
int main()
{
  n=gi();m=gi();
  fp(i,1,n) b[i]=gi(),L[i]=app[b[i]],app[b[i]]=i,R[i]=n+1;
  fp(i,0,n) app[i]=n+1;
  fq(i,n,1) R[i]=app[b[i]],app[b[i]]=i;
  fp(i,1,n) a[i].d[0]=L[i],a[i].d[1]=i,a[i].d[2]=R[i],a[i].max=a[i].w=b[i];
  kd.Build(rt,1,n,0);
  while(m--)
    {
      re int l=gi(),r=gi();
      l=(l+ans)%n+1,r=(r+ans)%n+1;
      if(l>r) swap(l,r);
      ans=0;kd.Query(rt,l,r);
      printf("%d\n",ans);
    }
  return 0;
}