从今以后

题目

题目描述

小果有一个数列
定义这个数列是合法的，指对于这个数列的每个子序列，都存在一个元素在在这个子序列中，只出现了一次
请帮小果判断这个数列是否合法

输入格式

第一行一个整数$T$，表示数据组数
接下来$T$组数据，每组数据第一行有一个整数$n$，表示该组数据的序列长度，之后一行有$n$个非负整数$a_i$，表示该序列中每个元素的值

输出格式

共$T$行，每行为yes或者no，表示这个序列合法或不合法

样例

样例输入

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

样例输出

yes
no
yes
no

数据范围与提示

对于$30%$的数据$\sum n \leqslant 5000$
对于$100%$的数据$\sum n \leqslant 2 \times 10^6,n \leqslant 2 \times 10^5$
所有的$a_i$满足$0 \leqslant a_i \leqslant 10^9$

题解

我的方法比较奇怪，如果你想看常规方法，可以看看这个神犇的博客
首先，先离散化，没啥好说的吧
接着，我们计算出$pre_i$和$nxt_i$分别表示前一个值为$a_i$的位置的下标和后一个值为$a_i$的位置的下标（也就是$a_{pre_i}=a_i$且$\forall j\in(pre_i,i),a_j\neq a_i$，$a_{nxt_i}=a_i$且$\forall j\in(i,nxt_i),a_j\neq a_i$）
所以，$\forall l\in (pre_i,i],r\in[i,nxt_i)$，区间$[l,r]$是合法的
所以，我们只需要找到这个区域内只出现一次的数，然后分别把数列从这个数劈成两半，分别考虑两个数列，如果都是合法的，那么这个数列就是合法的，进行递归即可
附上代码：

#include<algorithm>
#include<iostream>
using namespace std;
int n,a[200010],A[200010],pre[200010],nxt[200010],q[200010],h[200010];
int dg(int l,int r)
{
    if(l>=r) return 1;
    int mid=(r-l)/2;
    for(int i=0;i<=mid;i++){
        if(pre[l+i]<l&&nxt[l+i]>r) return (dg(l,l+i-1)&&dg(l+i+1,r));
        if(pre[r-i]<l&&nxt[r-i]>r) return (dg(l,r-i-1)&&dg(r-i+1,r));
    }
    return 0;
}
int main()
{
    int T;
    cin>>T;
    while(T--){
        cin>>n;
        for(int i=1;i<=n;i++) cin>>a[i],A[i]=a[i],pre[i]=nxt[i]=0;
        sort(A+1,A+n+1);
        int len=unique(A+1,A+n+1)-(A+1);
        for(int i=1;i<=n;i++) a[i]=lower_bound(A+1,A+len+1,a[i])-A;
        for(int i=1;i<=len;i++) q[i]=0,h[i]=n+1;
        for(int i=1;i<=n;i++) pre[i]=q[a[i]],q[a[i]]=i,nxt[n-i+1]=h[a[n-i+1]],h[a[n-i+1]]=n-i+1;
        cout<<(dg(1,n)?"yes":"no")<<endl;
    }
}

喜欢的话，给博主赏一杯冰阔乐吧~