Non-boring sequences

如果序列的任意连续子序列都有至少一个元素仅出现一次，就认为这个序列 $\texttt{non-boring}$，否则认为这个序列 $\texttt{boring}$，判断给定的包含 $n$ 个非负整数的序列 $a$ 的类型。

多测，$1 \leq n \leq 2 \times 10^5$，$0 \leq a_i \leq 10^9$。

数据结构、扫描线、线段树

考虑把序列对应到平面上，连续子序列 $a_l \sim a_r$ 用格子 $(l,r)$ 表示。注意满足 $x>y$ 的格子 $(x,y)$ 没有意义。

对于 $a_i$ 求出左边和右边第一个等于 $a_i$ 的元素位置分别表示为 $l_i,r_i$（不存在这样的元素则为 $0$ 和 $n+1$），显然所有被 $[l_i+1,r_i-1]$ 包含且包含 $a_i$ 的连续子序列都符合条件。

改写条件，区间 $[l',r']$ 符合条件当且仅当 $l_i+1 \leq l' \leq i$ 且 $i \leq r' \leq r_i-1$，显而易见，满足这个条件的格子在平面上构成一个矩形，而且所有满足条件的格子都有意义，不用考虑无意义格子。

在平面上做矩形面积并，如果结果等于 $\sum_{i=1}^{n} i$ 则序列 $\texttt{non-boring}$，总体时间复杂度 $O(n \log n)$。

#include<bits/stdc++.h>
using namespace std;
struct Operation{int l,r,y,w;}c[400005];
struct Segment{int l,r,w,m;}s[800005];
int n,a[200005],al[200005],ar[200005];
bool cmp(const Operation &x,const Operation &y){return x.y<y.y;}
void build(int u,int l,int r){
    s[u].l=l,s[u].r=r,s[u].w=0,s[u].m=0;
    if(l==r) return;
    int mid=(l+r)>>1;
    build(u*2,l,mid),build(u*2+1,mid+1,r);
}
void update(int u,int l,int r,int k){
    if(s[u].l>r||s[u].r<l) return;
    if(s[u].l>=l&&s[u].r<=r) s[u].m+=k;
    else update(u*2,l,r,k),update(u*2+1,l,r,k);
    if(s[u].m) s[u].w=(s[u].r+1)-s[u].l;
    else s[u].w=s[u*2].w+s[u*2+1].w;
}
void solution(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    unordered_map<int,int> m;
    for(int i=1;i<=n;i++) al[i]=m[a[i]]+1,m[a[i]]=i;
    for(int i=1;i<=n;i++) m[a[i]]=n+1;
    for(int i=n;i>=1;i--) ar[i]=m[a[i]]-1,m[a[i]]=i;
    for(int i=1;i<=n;i++){
        c[i*2-1]=Operation{al[i],i,i,1};
        c[i*2]=Operation{al[i],i,ar[i]+1,-1};
    }
    sort(c+1,c+n*2+1,cmp);
    build(1,1,n+1);
    long long ans=0ll;
    for(int i=1;i<=n*2;i++){
        ans+=1ll*s[1].w*(c[i].y-c[i-1].y);
        update(1,c[i].l,c[i].r,c[i].w);
    }
    if(ans==1ll*(n+1)*n/2) puts("non-boring");
    else puts("boring");
}
int T;
int main(){
    scanf("%d",&T);
    while(T--) solution();
    return 0;
}