首页 > 代码库 > [bzoj3489]A simple rmq problem
[bzoj3489]A simple rmq problem
来自FallDream的博客，未经允许，请勿转载，谢谢。
因为是OJ上的题，就简单点好了。给出一个长度为n的序列，给出M个询问：在[l,r]之间找到一个在这个区间里只出现过一次的数，并且要求找的这个数尽可能大。如果找不到这样的数，则直接输出0。我会采取一些措施强制在线。
N<=100000，M<=200000
对于每一个ai，找到它的上一个和下一个，假设是l和r，那么右区间在[i,r-1]，左区间在[l+1,i]时的答案对ai取max。
这个可以线段树套线段树实现。外层表示右区间，内层表示左区间，标记永久化即可。复杂度nlog^2n
#include<iostream>#include<cstdio>#include<algorithm>#include<cstring>#define ll long long#define N 131072#define MN 100000using namespace std;inline int read(){ int x = 0 , f = 1; char ch = getchar(); while(ch < ‘0‘ || ch > ‘9‘){ if(ch == ‘-‘) f = -1; ch = getchar();} while(ch >= ‘0‘ && ch <= ‘9‘){x = x * 10 + ch - ‘0‘;ch = getchar();} return x * f;}struct Tree{int l,r,x,val;}T[MN*350];int n,m,cnt=0,a[MN+5],lastans=0,Last[MN+5],Pre[MN+5],La[MN+5],t[N*2+5],ans=0;inline int Node(int x){return !x?++cnt:x;}void Query(int x,int l,int r,int v){ if(!x||T[x].x<=ans) return; ans=max(ans,T[x].val); if(l==r) {ans=max(ans,T[x].x);return;} int mid=l+r>>1; if(v<=mid) Query(T[x].l,l,mid,v); else Query(T[x].r,mid+1,r,v);} void Modify(int x,int l,int r,int lt,int rt,int v){ T[x].x=max(T[x].x,v); if(l==lt&&r==rt) { T[x].val=max(T[x].val,v); return; } int mid=l+r>>1; if(rt<=mid) Modify(T[x].l=Node(T[x].l),l,mid,lt,rt,v); else if(lt>mid) Modify(T[x].r=Node(T[x].r),mid+1,r,lt,rt,v); else Modify(T[x].l=Node(T[x].l),l,mid,lt,mid,v), Modify(T[x].r=Node(T[x].r),mid+1,r,mid+1,rt,v);}void modify(int l,int r,int lt,int rt,int v){ for(l+=N-1,r+=N+1;l^r^1;l>>=1,r>>=1) { if(~l&1) Modify(t[l+1],1,n,lt,rt,v); if( r&1) Modify(t[r-1],1,n,lt,rt,v); }}int Query(int x,int l){ ans=0; for(x+=N;x;x>>=1) Query(t[x],1,n,l);}int main(){ n=read();m=read(); for(int i=1;i<=N<<1;++i) t[i]=++cnt; for(int i=1;i<=n;++i) a[i]=read(); for(int i=1;i<=n;++i) Pre[i]=La[a[i]],La[a[i]]=i; for(int i=1;i<=n;++i) La[i]=n+1; for(int i=n;i;--i) Last[i]=La[a[i]],La[a[i]]=i; for(int i=1;i<=n;++i) modify(i,Last[i]-1,Pre[i]+1,i,a[i]); for(int i=1;i<=m;++i) { int l=(read()+lastans)%n+1,r=(read()+lastans)%n+1; if(l>r) swap(l,r); printf("%d\n",(Query(r,l),lastans=ans)); } return 0;}
[bzoj3489]A simple rmq problem
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。