uva1608(Non-boring sequences) - c++编程基础

题意：如果一个序列的任意连续子序列中至少有一个只出现一次的元素，则称这个序列是不无聊的。判断一个长度为ｎ（ｎ＜＝２０００００）的序列是不是无聊的。

解法：搞个ｍａｐ记录每个数前一个数的位置，判断以每个数结尾的所有区间是否合法，其中用到线段树访问区间最小值。

代码：

/******************************************************
* @author:xiefubao
*******************************************************/
#pragma comment(linker, "/STACK:102400000,102400000")
#include 
  
   
#include 
   
     #include 
    
      #include 
     
       #include 
      
        #include 
       
         #include 
        
          #include 
         
           #include 
           #include 
           
             #include 
            
              #include 
             
               //freopen ("in.txt" , "r" , stdin); using namespace std; #define eps 1e-8 #define zero(_) (abs(_)<=eps) const double pi=acos(-1.0); typedef long long LL; const int Max=200010; const LL INF=0x3FFFFFFF; int n; int num[Max]; int pre[Max]; map
              
                maps; struct node { int l,r; node* left,* right; int ma; } nodes[Max*3]; int tot=0; void build(node* p,int l,int r) { p->l=l; p->r=r; p->ma=INF; if(l==r) return ; int middle=(l+r)>>1; tot++; p->left=nodes+tot; build(p->left,l,middle); tot++; p->right=nodes+tot; build(p->right,middle+1,r); } void down(node* p) { p->ma=min(p->left->ma,p->right->ma); } void update(node* p,int index,int value) { if(p->l==p->r&&p->l==index) { p->ma=value; return ; } int middle=(p->l+p->r)>>1; if(index<=middle) update(p->left,index,value); else update(p->right,index,value); down(p); } int query(node* p,int l,int r) { if(p->l==l&&p->r==r) return p->ma; int middle=(p->r+p->l)>>1; if(r<=middle) return query(p->left,l,r); else if(l>middle) return query(p->right,l,r); else return min(query(p->left,l,middle),query(p->right,middle+1,r)); } int main() { int t; scanf("%d",&t); while(t--) { tot=0; maps.clear(); scanf("%d",&n); build(nodes,1,n); for(int i=1; i<=n; i++) scanf("%d",num+i); reverse(num+1,num+n+1); for(int i=1; i<=n; i++) pre[i]=maps[num[i]],maps[num[i]]=i; bool flag=0; for(int i=1; i<=n; i++) { if(pre[i]!=0) update(nodes,pre[i],pre[i]); int left=pre[i],right=i; while(left>0) { int pr; if(left+1<=right-1) pr=query(nodes,left+1,right-1); if(left+1>right-1||pr>=left) { flag=1; break; } right=left; left=pr; } if(flag) break; update(nodes,i,pre[i]); } if(flag) puts("boring"); else puts("non-boring"); } return 0; } /* ababababa */