[BZOJ3489]A simple rmq problem

题解：

并没有想到。。

我们用前驱后继来表示出题目要求

即pre[i]<l且scc[i]>r且l<=i<=r

即4维偏序

使用树套树可以用主席树套线段树（很毒瘤？？）

那么会kd-tree就比较简单了，3维空间查找

代码写完编译运行一遍过就很爽了

代码：

#include <bits/stdc++.h>
using namespace std;
#define IL inline
#define rint register int 
#define rep(i,h,t) for (rint i=h;i<=t;i++)
#define dep(i,t,h) for (rint i=t;i>=h;i--)
#define mid ((h+t)/2)
const int INF=1e9;
const int N=3e5;
int n,m;
char ss[1<<24],*A=ss,*B=ss;
IL char gc()
{
  return A==B&&(B=(A=ss)+fread(ss,1,1<<24,stdin),A==B)?EOF:*A++;
}
template<class T>void read(T &x)
{
  rint f=1,c; while (c=gc(),c<48||c>57) if (c=='-') f=-1; x=(c^48);
  while (c=gc(),c>47&&c<58) x=(x<<3)+(x<<1)+(c^48); x*=f;
}
IL void umax(int &x,int y)
{
  if (x<y) x=y;
}
IL void umin(int &x,int y)
{
  if (x>y) x=y;
}
struct re
{
  int d[3],num;
}p[N];
int cmp_d,ans,a[N];
bool cmp(re x,re y)
{
  return(x.d[cmp_d]<y.d[cmp_d]);
}
struct kd
{
  int ls[N],rs[N],Mx[N],My[N],Mz[N],Nx[N],Ny[N],Nz[N],maxn[N];
  void updata(int x)
  {
    if (ls[x])
    {
      umax(Mx[x],Mx[ls[x]]);
      umax(My[x],My[ls[x]]);
      umax(Mz[x],Mz[ls[x]]);
      umin(Nx[x],Nx[ls[x]]);
      umin(Ny[x],Ny[ls[x]]);
      umin(Nz[x],Nz[ls[x]]);
      umax(maxn[x],maxn[ls[x]]);
    }
    if (rs[x])
    {
      umax(Mx[x],Mx[rs[x]]);
      umax(My[x],My[rs[x]]);
      umax(Mz[x],Mz[rs[x]]);
      umin(Nx[x],Nx[rs[x]]);
      umin(Ny[x],Ny[rs[x]]);
      umin(Nz[x],Nz[rs[x]]);
      umax(maxn[x],maxn[rs[x]]);
    }
  }
  int build(int h,int t,int o)
  {
    cmp_d=o; nth_element(p+h,p+mid,p+t+1,cmp);
    int x=mid;
    Mx[x]=Nx[x]=p[x].d[0];
    My[x]=Ny[x]=p[x].d[1];
    Mz[x]=Nz[x]=p[x].d[2];
    maxn[x]=p[x].num;
    if (h!=x) ls[x]=build(h,mid-1,(o+1)%3); else ls[x]=0;
    if (t!=x) rs[x]=build(mid+1,t,(o+1)%3); else rs[x]=0;
    updata(x);
    return x;
  }
  void query(int k,int x1,int x2,int y,int z)
  {
    if (!k||maxn[k]<ans||Mx[k]<x1||Nx[k]>x2||Ny[k]>=y||Mz[k]<=z) return;
    if (p[k].d[0]>=x1&&p[k].d[0]<=x2&&p[k].d[1]<y&&p[k].d[2]>z&&p[k].num>ans)
      ans=p[k].num;
    query(ls[k],x1,x2,y,z); query(rs[k],x1,x2,y,z);
  }
}kd;
map<int,int> M;
int pre[N],scc[N];
int main()
{
  freopen("1.in","r",stdin);
  freopen("1.out","w",stdout);
  read(n); read(m);
  rep(i,1,n)
  { 
    read(a[i]);
    int kk=M[a[i]];
    if (kk)
    {
      scc[kk]=i; pre[i]=kk;
    }
    M[a[i]]=i;
  }
  rep(i,1,n) if (!scc[i]) scc[i]=n+1;
  rep(i,1,n) p[i].num=a[i],p[i].d[0]=i,p[i].d[1]=pre[i],p[i].d[2]=scc[i];
  int rt=kd.build(1,n,0);
  rep(i,1,m)
  {
    int x,y;
    read(x); read(y);
    x=(ans+x)%n+1,y=(ans+y)%n+1;
    if (x>y) swap(x,y);
    ans=0;
    kd.query(rt,x,y,x,y);
    printf("%d
",ans); 
  }
  return 0;
}