首页 > 代码库 > bzoj3489 A simple rmq problem
bzoj3489 A simple rmq problem
我是萌萌的传送门
智商还是不太够啊……差点又把主席树套主席树这个暴力无脑的做法给忘了……
记每个数的前驱为prev，后继为next，问题就变成了求区间中所有满足prev<l且next>r的数的最大值。
有三个限制，那么就上主席树套主席树，可持久化压掉prev，外层维护区间，里层维护next和最大值即可。
预处理$O(n\log^2n)$，单次询问$O(\log^2n)$，空间$O(n\log^2n)$。
1 /************************************************************** 2 Problem: 3489 3 User: hzoier 4 Language: C++ 5 Result: Accepted 6 Time:30080 ms 7 Memory:605568 kb 8 ****************************************************************/ 9 #include<cstdio> 10 #include<cstring> 11 #include<algorithm> 12 using namespace std; 13 const int maxn=100010,maxm=maxn*450; 14 struct node{ 15 int root; 16 node *lc,*rc; 17 node():root(0){} 18 }null[maxn<<6],*ptr=null,*root[maxn]; 19 struct A{ 20 int d,id,prev,next; 21 bool operator<(const A &a)const{return prev<a.prev;} 22 }a[maxn]; 23 void build(int,int,node*&,node*); 24 void query(int,int,node*); 25 void build(int,int,int&,int); 26 void query(int,int,int); 27 int mx[maxm]={0},lc[maxm]={0},rc[maxm]={0},cnt=0; 28 int n,m,s,t,last[maxn]={0},x,ans=0; 29 int main(){ 30 null->lc=null->rc=root[0]=null; 31 scanf("%d%d",&n,&m); 32 for(int i=1;i<=n;i++){ 33 scanf("%d",&a[i].d); 34 a[i].id=i; 35 a[i].prev=last[a[i].d]+1; 36 last[a[i].d]=i; 37 } 38 fill(last,last+n+1,n+1); 39 for(int i=n;i;i--){ 40 a[i].next=last[a[i].d]-1; 41 last[a[i].d]=i; 42 } 43 sort(a+1,a+n+1); 44 for(int i=1,cnt=1;i<=n;i++){//可持久化压掉prev 45 root[i]=root[i-1]; 46 while(cnt<=n&&a[cnt].prev<=i){ 47 x=cnt++; 48 build(1,n,root[i],root[i]); 49 } 50 } 51 while(m--){ 52 scanf("%d%d",&s,&t); 53 s=(s+ans)%n+1; 54 t=(t+ans)%n+1; 55 if(s>t)swap(s,t); 56 ans=0; 57 query(1,n,root[s]); 58 printf("%d\n",ans); 59 } 60 return 0; 61 } 62 void build(int l,int r,node *&rt,node *pr){//区间线段树 63 *(rt=++ptr)=*pr; 64 build(1,n,rt->root,pr->root); 65 if(l==r)return; 66 int mid=(l+r)>>1; 67 if(a[x].id<=mid)build(l,mid,rt->lc,pr->lc); 68 else build(mid+1,r,rt->rc,pr->rc); 69 } 70 void query(int l,int r,node *rt){//区间线段树 71 if(s<=l&&t>=r){ 72 query(1,n,rt->root); 73 return; 74 } 75 int mid=(l+r)>>1; 76 if(s<=mid)query(l,mid,rt->lc); 77 if(t>mid)query(mid+1,r,rt->rc); 78 } 79 void build(int l,int r,int &rt,int pr){//对next建线段树 80 mx[rt=++cnt]=max(mx[pr],a[x].d); 81 if(l==r)return; 82 lc[rt]=lc[pr];rc[rt]=rc[pr]; 83 int mid=(l+r)>>1; 84 if(a[x].next<=mid)build(l,mid,lc[rt],lc[pr]); 85 else build(mid+1,r,rc[rt],rc[pr]); 86 } 87 void query(int l,int r,int rt){//询问所有next>r的最大值 88 if(t<=l){ 89 ans=max(ans,mx[rt]); 90 return; 91 } 92 int mid=(l+r)>>1; 93 if(t<=mid)query(l,mid,lc[rt]); 94 query(mid+1,r,rc[rt]); 95 } 96 /* 97 记每个数的前驱为prev，后继为next， 98 问题就变成了求区间中所有满足prev<l且next>r的数的最大值。 99 这次有三个限制，主席树套主席树即可。 100 可持久化压掉prev，外层维护区间，里层维护next和最大值即可。 101 */ 102
还有一个脑洞级别的做法：
把序列分成$\sqrt{n}$块，设f[i][j]表示第i块到第j块所有出现恰好一次的数组成的hash表，如果多于$2\sqrt{n}$个那么只取最大的$2\sqrt{n}$个。
询问时取出完整块的hash表，扫描不完整块更新hash表，最后hash表中最大的元素即为答案。
预处理可以做到$O(n\sqrt{n})$，单次询问$O(\sqrt{n})$，空间显然是$O(n\sqrt{n})$的(总共有$O(\sqrt{n})*O(\sqrt{n})=O(n)$个hash表，而每个hash表中至多有$2\sqrt{n}$个元素)。
看着不错，然而可写性不大……仅作脑洞吧……
bzoj3489 A simple rmq problem
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。