bzoj 3489: A simple rmq problem-白红宇

bzoj 3489: A simple rmq problem

阅读量：6280 次

发布时间：2019-06-22

本文共 1643 字，大约阅读时间需要 5 分钟。

1 #include
     
        2 #include
      
         3 #include
       
          4 #define M 200009  5 using namespace std;  6 struct A  7 {  8     int d[3],mx[3],mn[3],l,r,v,mx1;  9 }a[M]; 10 int n,b[M],v[M],N,ans,root,m; 11 bool cmp(A a1,A a2) 12 { 13     return a1.d[N]
        
         >1; 34     N=now; 35     nth_element(a+l,a+mid,a+r+1,cmp); 36     if(l
         
          mid) 41       a[mid].r=jian(mid+1,r,(now+1)%3); 42     else 43       a[mid].r=0; 44     updata(mid); 45     return mid; 46 } 47 void xun(int k,int l,int r) 48 { 49     if(!k) 50       return; 51     if(a[k].mx[0]
          
           r&&a[k].mn[1]>=l&&a[k].mx[1]<=r) 52 { 53 ans=max(a[k].mx1,ans); 54 return; 55 } 56 if(a[k].mn[0]>=l||a[k].mx[2]<=r||a[k].mx[1]
           
            r) 57 return; 58 if(a[k].d[0]
            
             r&&a[k].d[1]>=l&&a[k].d[1]<=r) 59 ans=max(ans,a[k].v); 60 int l1=a[a[k].l].mx1,r1=a[a[k].r].mx1; 61 if(l1>r1) 62 { 63 if(l1>ans) 64 xun(a[k].l,l,r); 65 if(r1>ans) 66 xun(a[k].r,l,r); 67 } 68 else 69 { 70 if(r1>ans) 71 xun(a[k].r,l,r); 72 if(l1>ans) 73 xun(a[k].l,l,r); 74 } 75 return; 76 } 77 int main() 78 { 79 scanf("%d%d",&n,&m); 80 for(int i=1;i<=n;i++) 81 { 82 scanf("%d",&b[i]); 83 a[i].mx1=a[i].v=b[i]; 84 a[i].d[1]=i; 85 a[i].d[2]=n+1; 86 if(v[b[i]]) 87 { 88 a[i].d[0]=v[b[i]]; 89 a[v[b[i]]].d[2]=i; 90 } 91 v[b[i]]=i; 92 } 93 root=jian(1,n,0); 94 for(int i=1;i<=m;i++) 95 { 96 int x,y,l,r; 97 scanf("%d%d",&x,&y); 98 l=min((x+ans)%n+1,(y+ans)%n+1); 99 r=max((x+ans)%n+1,(y+ans)%n+1);100 ans=0;101 xun(root,l,r);102 printf("%d\n",ans);103 }104 return 0;105 }