4059: [Cerc2012]Non-boring sequences
Time Limit: 10 Sec Memory Limit: 128 MBSubmit: 440 Solved: 160[][][]Description
我们害怕把这道题题面搞得太无聊了,所以我们决定让这题超短。一个序列被称为是不无聊的,仅当它的每个连续子序列存在一个独一无二的数字,即每个子序列里至少存在一个数字只出现一次。给定一个整数序列,请你判断它是不是不无聊的。
Input
第一行一个正整数T,表示有T组数据。每组数据第一行一个正整数n,表示序列的长度,1 <= n <= 200000。接下来一行n个不超过10^9的非负整数,表示这个序列。
Output
对于每组数据输出一行,输出"non-boring"表示这个序列不无聊,输出"boring"表示这个序列无聊。
Sample Input
4 5 1 2 3 4 5 5 1 1 1 1 1 5 1 2 3 2 1 5 1 1 2 1 1
Sample Output
non-boring boring non-boring boring
HINT
Source
Solution
不想多说什么
首先预处理出每个数字,上一次出现的位置$pre[i]$,下一次出现的位置$suf[i]$,显然,对于区间是满足独一无二的,当左端点在$[pre[i]+1,i]$右端点在$[i,suf[i]-1]$
然后我们把它们放到平面上,<l,r>表示一个点,那么满足的情况,显然是一个矩形
那么我们把这些所有的矩形都建出来,然后扫描线。
如果这些矩形的并覆盖所有合法点,那么就是non-boring,否则是boring
问题在于,这不是正解!!!!正解是神奇的爆搜,转别人的博客 :
Code
#include#include #include #include #include using 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;}#define MAXN 200010int T,N,A[MAXN];struct SegmentTreeNode{ int minn,tag,l,r;}tree[MAXN<<2];inline void Update(int now) {tree[now].minn=min(tree[now<<1].minn,tree[now<<1|1].minn);}inline void PushDown(int now){ if (!tree[now].tag || tree[now].l==tree[now].r) return; int tag=tree[now].tag; tree[now].tag=0; tree[now<<1].minn+=tag; tree[now<<1].tag+=tag; tree[now<<1|1].minn+=tag; tree[now<<1|1].tag+=tag;}void BuildTree(int now,int l,int r){ tree[now].l=l; tree[now].r=r; tree[now].minn=0; tree[now].tag=0; if (l==r) return; int mid=(l+r)>>1; BuildTree(now<<1,l,mid); BuildTree(now<<1|1,mid+1,r); Update(now);}void Change(int now,int L,int R,int D){ PushDown(now); int l=tree[now].l,r=tree[now].r; if (L<=l && R>=r) {tree[now].tag+=D; tree[now].minn+=D; return;} int mid=(l+r)>>1; if (L<=mid) Change(now<<1,L,R,D); if (R>mid) Change(now<<1|1,L,R,D); Update(now);}int Query(int now,int L,int R){ PushDown(now); int l=tree[now].l,r=tree[now].r; if (L<=l && R>=r) return tree[now].minn; int mid=(l+r)>>1,re=0x7fffffff; if (L<=mid) re=min(re,Query(now<<1,L,R)); if (R>mid) re=min(re,Query(now<<1|1,L,R)); return re;}struct LineNode{ int x,y1,y2,f;//y1>y2 LineNode (int x=0,int y1=0,int y2=0,int f=0) : x(x),y1(y1),y2(y2),f(f) {} bool operator < (const LineNode & A) const { return x==A.x? y1