[bzoj3489] A simple rmq problem 解题报告

本文主要是介绍[bzoj3489] A simple rmq problem 解题报告，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

说几种比较傻逼的做法：
考虑一个点i，设它前面第一个和它相等的点的位置是 $last_i$ （若没有就是0），设它后面第一个和它相等的点的位置是 $next_i$ （如果没有就是n+1），则它会产生贡献的区间[l,r]要求 $last_i+1\le l \le i,i\le r \le next_i-1$ 。所以如果把询问的区间看作平面上的点，这就相当于是对一个矩形产生贡献，考虑到这题要求离线，所以我们就可以用二维可持久化线段树来搞。。
就这样跑了17s。。

我们反过来考虑，考虑一次询问对点的要求，是 $i\in [l,r],last_i\in [1,l),next_i\in (i,n]$ ，所以我们可以就可以用三维k-d树搞出这个东西来。注意到 $last_i$ 和 $next_i$ 都是一个类似前缀和的东西，所以我们前缀和一维，用二维可持久化k-d树。
就这样跑了10s。。

代码（可持久化k-d树）：

#include<cstdio>
#include<iostream>
using namespace std;
#include<algorithm>
#include<cstring>
#include<cmath>
const int N=1e5+5,M=2e5+5;
int a[N];
int pos[N];void in(int &x){char c=getchar();while(c<'0'||c>'9')c=getchar();for(x=0;c>='0'&&c<='9';c=getchar())x=x*10+(c^'0');
}const int Log=18;
struct KS{int ls,rs;int lx,rx,ly,ry;int max;
}kdt[N*(Log+2)];
int root[N];
int ktot=1;
struct PS{int x,y;
}point[N];
bool cmpx(const PS & a,const PS & b){return a.x<b.x;
}
bool cmpy(const PS & a,const PS & b){return a.y<b.y;
}
bool inrange(int lx,int rx,int ly,int ry,int Lx,int Rx,int Ly,int Ry){return Lx<=lx&&rx<=Rx&&Ly<=ly&&ry<=Ry;
}
void out(int node){printf("%d{[%d,%d]-[%d,%d] max=%d}\n",node,kdt[node].lx,kdt[node].rx,kdt[node].ly,kdt[node].ry,kdt[node].max);
}
void build(int &node,int pl,int pr,bool depth){node=ktot++;kdt[node].lx=kdt[node].rx=point[pl].x;kdt[node].ly=kdt[node].ry=point[pl].y;for(int i=pl+1;i<=pr;++i){kdt[node].lx=min(kdt[node].lx,point[i].x);kdt[node].rx=max(kdt[node].rx,point[i].x);kdt[node].ly=min(kdt[node].ly,point[i].y);kdt[node].ry=max(kdt[node].ry,point[i].y);}//printf("[%d,%d]=",pl,pr);//out(node);if(pl!=pr){int pm=pl+pr>>1;if(depth)nth_element(point+pl,point+pm,point+pr+1,cmpx);else nth_element(point+pl,point+pm,point+pr+1,cmpy);//for(int i=pl;i<=pr;++i)printf("(%d,%d) ",point[i].x,point[i].y);//puts("");build(kdt[node].ls,pl,pm,depth^1);build(kdt[node].rs,pm+1,pr,depth^1);}
}
void add(int &node,int pl,int pr,int x,int A){//printf("Add (%d) at ",A);kdt[ktot]=kdt[node];//out(node);node=ktot++;kdt[node].max=max(kdt[node].max,A);//out(node);if(pl!=pr){//out(kdt[node].ls),out(kdt[node].rs);if(x<=pl+pr>>1)add(kdt[node].ls,pl,pl+pr>>1,x,A);else add(kdt[node].rs,(pl+pr>>1)+1,pr,x,A);}
}
int lastans;
void query(int node,int Lx,int Rx,int Ly,int Ry){if(kdt[node].rx<Lx||kdt[node].lx>Rx||kdt[node].ly>Ry||kdt[node].ry<Ly)return;if(inrange(kdt[node].lx,kdt[node].rx,kdt[node].ly,kdt[node].ry,Lx,Rx,Ly,Ry)){//printf("Get:");//out(node);lastans=max(lastans,kdt[node].max);}if(kdt[node].max<=lastans)return;query(kdt[node].ls,Lx,Rx,Ly,Ry),query(kdt[node].rs,Lx,Rx,Ly,Ry);
}struct PointS{int last,i,next;bool operator < (const PointS & o)const{return last<o.last;}
}pnt[N];
int main(){freopen("bzoj_3489.in","r",stdin);int n,m;in(n),in(m);for(int i=1;i<=n;++i)in(a[i]);for(int i=1;i<=n;++i){pnt[i].last=pos[a[i]]+1;pos[a[i]]=i;}for(int i=n;i;--i)pos[a[i]]=n+1;for(int i=n;i;--i){pnt[i].next=pos[a[i]]-1;pos[a[i]]=i;}for(int i=n;i;--i)pnt[i].i=i;for(int i=n;i;--i)point[i]=(PS){i,pnt[i].next};sort(pnt+1,pnt+n+1);build(root[0],1,n,0);for(int i=n;i;--i)pos[point[i].x]=i;for(int i=1,j=1;i<=n;++i){//printf("---%d---\n",i);root[i]=root[i-1];for(;pnt[j].last==i;++j){//printf("%d ",pnt[j].i);add(root[i],1,n,pos[pnt[j].i],a[pnt[j].i]);}//puts("");}//cout<<ktot<<endl;int l,r;while(m--){in(l),in(r);l=(l+lastans)%n+1,r=(r+lastans)%n+1;if(l>r)swap(l,r);lastans=0;query(root[l],l,r,r,n);printf("%d\n",lastans);}
}