题解：P11282 「GFOI Round 2」Colors

场上胡了一堆结论过了，证明一下这些结论。

下面我们只考虑 n>5 的情况，n\le 5 corner case 太多了直接跑暴力。

接下来认为删除后球会自动往前补位（即只考虑红球，蓝球不重要）。

这样一次操作必定为操作 i-1,i,i+1 这三个位置。

发现删除 i,i+1 和删除三个位置中任意两个没有区别，于是操作是对称的。

结论 1：5\le i\le n-4，i 为奇数，最后一定能剩下权值 p_i。

考虑 p_{i-1}>p_i 的情况，p_{i-1}<p_i 是对称的。

• 操作直到球 $i$ 到达 $3$ 的位置，也就是把 $1\sim i-2$ 的球合成一个最大值。 因为 $\exists j<i-1,p_j>p_i$，合出来的 $p'_1>p'_3=p_i$，又 $p'_2=p_{i-1}>p'_3=p_i$，此时操作 $1,2,3$ 这三个球，选择 $p'_1\gets\min(p_1,p_2,p_3)$，这样 $p'_1=p_i$。 
• 这样去掉了 $p_{i-1}$，$p_i$ 是前缀最大，直接不断选择 $\max$ 操作即可把 $i$ 移动至 $1$。 即不断操作 $1,2,3$，选择 $p'_1\gets\max(p_1,p_2,p_3)$。 

以上证明了可以删掉 1\sim i-1，对称，同理可以删掉 i+1\sim n。

结论 2：1\le i\le n，i 为偶数，最后不能剩下权值 p_i 当且仅当 p_i 两侧权值范围无交。

权值范围无交意思是 \max\limits_{j<i}p_j<p_i<\min\limits_{j>i}p_j 或者 \min\limits_{j<i}p_j>p_i>\max\limits_{j>i}p_j。

考虑 p_{i+1}>p_i 的情况，p_{i+1}<p_i 是对称的。

若 \exists j<i-1,p_j>p_i，那么不断操作 1,2,3 这三个位置，选择 p'_1\gets\max(p_1,p_2,p_3)。

操作直到球 i 到达 2 的位置，也就是把 1\sim i-2 的球合成一个最大值。

因为 \exists j<i-1,p_j>p_i，合出来的 p'_1>p'_2=p_i，又 p'_3=p_{i+1}>p'_2=p_i，此时操作 1,2,3 这三个球，选择 p'_1\gets\min(p_1,p_2,p_3)，这样 p'_1=p_i。

又根据结论 1，可以删掉 i+2\sim n，这样最终剩下 p_i。

对称地，还有可能 p_{i-1}>p_i，\exists j>i+1,p_j>p_i。

剩下的情况就是 \max\limits_{j<i}p_j<p_i<\min\limits_{j>i}p_j 或者 \min\limits_{j<i}p_j>p_i>\max\limits_{j>i}p_j。

这些情况无论怎么操作，必定会操作 i-1,i,i+1，这时 p_i 是中位数，不能保留。

接下来就只用考虑 p_3 和 p_{n-2} 能不能保留，两种情况对称，只考虑 p_3 行不行。

• 操作 $1,2,3$ 或者 $3,4,5$ 肯定无用，只有可能操作 $2,3,4$。 只有 $p_2<p_3,p_4<p_3$ 才能操作 $2,3,4$，于是需要一个 $<p_3$ 的 $p_4$。 找到第一个 $i>3,p_i<p_4$ 的 $i$，找不到无解。 - $i$ 是奇数，第一个 $j>i,p_j>p_3$ 的 $i$，找不到无解。 取 min 合成 $p_4\sim p_i$ 为 $p'_4<p_3$。 取 max 合成 $p_{i+1}\sim p_n$ 为 $p'_5>p_3$。 $p_2>p_3<p'_4$，取 min 删去 $p_2$ 和 $p'_4$。 $p_1>p_3<p'_5$，取 min 删去 $p_1$ 和 $p'_5$。 剩下 $p_3$，必定有解。  - $i$ 是偶数，第一个 $j+1>i,p_j>p_3$ 的 $i$，找不到无解。 取 min 合成 $p_4\sim p_{i+1}$ 为 $p'_4<p_3$。 取 max 合成 $p_{i+2}\sim p_n$ 为 $p'_5>p_3$。 同理，必定有解。 

代码实现模拟上述过程即可，时间复杂度 O(n)。

#include<map>
#include<set>
#include<cmath>
#include<ctime>
#include<queue>
#include<stack>
#include<cstdio>
#include<vector>
#include<string>
#include<bitset>
#include<numeric>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
using namespace std;
const int MAXN=1e6+10;
const int N=1e6;
const int INF=0x3f3f3f3f;
const long long LINF=0x3f3f3f3f3f3f3f3f;
const int mod=998244353;
int n;
int a[MAXN];
bool ans[MAXN];
int suf_max[MAXN],suf_min[MAXN];
bool f[32];
void dfs(int s){
    if(f[s]){
        return ;
    }
    f[s]=true;
    if(s==(s&-s)){
        return;
    }
    for(int i=1;i<n-1;i++)
    {
        if(~s&(1<<i)){
            continue;
        }
        int j=i-1,k=i+1;
        while(~j&&~s&(1<<j))
        {
            j--;
        }
        while(k^n&&~s&(1<<k))
        {
            k++;
        }
        if(~j&&k^n){
            int p=a[i+1]+a[j+1]+a[k+1]-max({a[i+1],a[j+1],a[k+1]})-min({a[i+1],a[j+1],a[k+1]});
            if(a[i+1]==p){
                dfs(s^(1<<i)^(1<<j));
                dfs(s^(1<<i)^(1<<k));
            }
            if(a[j+1]==p){
                dfs(s^(1<<j)^(1<<i));
                dfs(s^(1<<j)^(1<<k));
            }
            if(a[k+1]==p){
                dfs(s^(1<<k)^(1<<i));
                dfs(s^(1<<k)^(1<<j));
            }
        }
    }
}
inline void work(){
    if(a[1]<a[3]&&a[2]>a[3]){
        ans[a[3]]=false;
        for(int i=4;i<=n;i++)
        {
            if(a[i]>a[3]){
                for(int j=i+1+(i&1);j<=n;j++)
                {
                    if(a[j]<a[3]){
                        ans[a[3]]=true;
                        break;
                    }
                }
                break;
            }
        }
    }
    if(a[1]>a[3]&&a[2]<a[3]){
        ans[a[3]]=false;
        for(int i=4;i<=n;i++)
        {
            if(a[i]<a[3]){
                for(int j=i+1+(i&1);j<=n;j++)
                {
                    if(a[j]>a[3]){
                        ans[a[3]]=true;
                        break;
                    }
                }
                break;
            }
        }
    }
}
inline void solve(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
    }
    if(n<=5){
        memset(f,false,sizeof(f));
        dfs((1<<n)-1);
        for(int i=1;i<=n;i++)
        {
            ans[a[i]]=f[1<<(i-1)];
        }
        for(int i=1;i<=n;i++)
        {
            putchar(ans[i]+'0');
        }
        putchar('\n');
        return ;
    }
    memset(ans,true,sizeof(bool)*(n+1));
    suf_max[n]=a[n];
    suf_min[n]=a[n];
    for(int i=n-1;i;i--)
    {
        suf_max[i]=max(suf_max[i+1],a[i]);
        suf_min[i]=min(suf_min[i+1],a[i]);
    }
    int pre_max=a[1],pre_min=a[1];
    for(int i=1;i<=n;i++)
    {
        if(~i&1&&(pre_max<a[i]&&a[i]<suf_min[i+1]||pre_min>a[i]&&a[i]>suf_max[i+1])){
            ans[a[i]]=false;
        }
        pre_max=max(pre_max,a[i]);
        pre_min=min(pre_min,a[i]);
    }
    work();
    reverse(a+1,a+1+n);
    work();
    for(int i=1;i<=n;i++)
    {
        putchar(ans[i]+'0');
    }
    putchar('\n');
}
signed main(){
    #ifdef LOCAL
    freopen("data.in","r",stdin);
    freopen("data.out","w",stdout);
    atexit([](){fprintf(stderr,"%.3lfs\n",(double)clock()/CLOCKS_PER_SEC);});
    #endif
    int t;
    scanf("%d",&t);
    while(t--)
    {
        solve();
    }
    return 0;
}