uva1608(Non-boring sequences)
來源：程序員人生 發布時間：2014-12-22 08:34:57 閱讀次數：3597次
題意：如果1個序列的任意連續子序列中最少有1個只出現1次的元素，則稱這個序列是不無聊的。判斷1個長度為ｎ（ｎ＜＝２０００００）的序列是否是無聊的。
解法：弄個ｍａｐ記錄每一個數前1個數的位置，判斷以每一個數結尾的所有區間是不是合法，其中用到線段樹訪問區間最小值。
代碼：
/******************************************************
* @author:xiefubao
*******************************************************/
#pragma comment(linker, "/STACK:102400000,102400000")
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <cstdio>
#include <queue>
#include <vector>
#include <algorithm>
#include <cmath>
#include <map>
#include <set>
#include <stack>
#include <string.h>
//freopen ("in.txt" , "r" , stdin);
using namespace std;
#define eps 1e⑻
#define zero(_) (abs(_)<=eps)
const double pi=acos(⑴.0);
typedef long long LL;
const int Max=200010;
const LL INF=0x3FFFFFFF;
int n;
int num[Max];
int pre[Max];
map<int,int> 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⑴)
pr=query(nodes,left+1,right⑴);
if(left+1>right⑴||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
*/
生活不易，碼農辛苦
如果您覺得本網站對您的學習有所幫助,可以手機掃描二維碼進行捐贈
