uva1608(Non-boring sequences)
来源：程序员人生 发布时间：2014-12-22 08:34:57 阅读次数：3427次
题意：如果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
*/
生活不易，码农辛苦
如果您觉得本网站对您的学习有所帮助,可以手机扫描二维码进行捐赠
