P11282 题解

1. 题目分析

题目保证 n 为奇数，且 p 中数互不相同且都 \ge 1 且 \le n。
我们先把题目的一次操作简单化，一次操作我们可以看成选择相邻的三个数，保留其中的最大值或最小值，其余数删除。之后的每次操作都是在前一次操作所剩下的序列上进行的。
我们要求出每个数是否能被保留，因为数是三个一起操作，也就是一次操作会删除两个数，对于奇数位上的数和偶数位上的数，其所展现的最终形态必然不同，这个待会儿再解释，所以我们需要进行分类讨论。
接下来我们用大来表示比我们所指定位上的数要大的数，用小来表示比我们所指定位上的数要小的数。

偶数位

由于 n 为奇数，故偶数位的前后都有奇数个数，按照每次删除两个数，那么其所展现的最终形态便是其左右分别只剩下一个数。那么这便会出现以下四种情况。

可以看到只有出现最上面或最下面的情况，此位置上的数可以被保留。我们只需要知道在此位置前和后的最大值和最小值就行了。
因为其前后的最大值和最小值一定能被保留，如果其前后的最大值都大于它或其前后的最小值都小于它，那么这个数便可以被保留，否则不能被保留。

奇数位

也是由于 n 为奇数，故奇数位的前后都有偶数个数，按照每次删除两个数，除了位置 1 和位置 n 外，其它位置所展现的最终形态便是左右分别只剩下两个数。简单推一下，可以得到会出现以下八种情况。

图有点丑，将就着看吧。我们可以看到其只有最上面的六种情况此位置上的数才能被保留。
要判断情况是否成立，我们可以贪心找数，比如对于第一种情况，我们找到在此数左边和它距离最近且大于它的数，因为这样可以使后面的搜索范围最大，所以一定最优。然后因为一次要删两个数，若找到的数与此数之间的格子有奇数个，那么我们要把找到的数的后一个数也删掉才行（如果后一个数大于找到的数也没影响，因为这样保留后一个数对情况没有影响），若找到的数与此数之间的格子有偶数个，那么之间的格子刚好删完，不用做特殊处理。然后我们在左边剩下的数中找是否有比此数更大的数即可，右边也是同理。其他情况与此情况的判定方法一样。
位置 1 和位置 n 的处理：它们要么右边剩两个数，要么左边剩两个数，如果有两个数都大于或都小于此数，也就是出现单边的大大和小小的情况，那么此数便可以被保留。

2. 题目做法

偶数位

我们要维护的是 1 到 x - 1 和 x + 1 到 n 的最大值和最小值。

• 暴力维护，O(n^2)。
  对于每个下标，直接往左右暴力扫一遍，这里不过多阐述，反正过不了。
• 线段树或 st 表维护，O(n \log{n})。
  直接建一颗支持两种询问的线段树，预处理 O(n)，每次询问 O(\log{n})。
  st 表预处理 O(n \log{n})，每次询问 O(1)，应该都可过。
• 线性扫描预处理，O(n)。
  因为要维护的两个区间要么左端点不变，要么右端点不变，我们可以用莫队的左移右移思想来 O(n) 预处理出区间的最大值和最小值，可过。

  奇数位

  我们要维护的是在 x 左边或右边的离 x 最近的大于或小于 p_x 的数的位置。

• 暴力维护，O(n^2)。
  也是往前往后暴力扫，加些优化过了，并且跑的飞起，需要代码可以私信我。
• 权值线段树维护，O(n \log{n})。
  在值域上存下标的最大和最小值，很难写，且常数巨大，预估卡常大师才能过吧。
• 单调栈维护，O(n)。
  分别用栈从左到右，从右到左扫一遍，就可以做到边扫边记录了。但写出来跑的竟然没有暴力快，离谱。

  3. 代码

  这里放的是线性扫描预处理和单调栈的代码。

#include<bits/stdc++.h>
#define getchar getchar_unlocked
#define putchar putchar_unlocked
using namespace std;
const int N=1000010,M=1001;
inline int read()
{
    int x=0;
    char c=getchar();
    while(c<'0'||c>'9')
        c=getchar();
    while(c>='0'&&c<='9')
        x=(x<<1)+(x<<3)+c-'0',c=getchar();
    return x;
}
int T,n;
int a[N],lmx[N],lmn[N],rmx[N],rmn[N];
int ls[N],lb[N],rs[N],rb[N];
bool p[N],vl[5],vr[5];//大大，大小，小大，小小
stack<int>ss,sb;
int main()
{
//  freopen("my.in","r",stdin);
//  freopen("my.out","w",stdout);
    T=read();
    lmn[0]=INT_MAX;
    while(T--)
    {
        n=read();
        for(int i=1;i<=n;i++)
            a[i]=read(),p[i]=0;
        lmx[1]=lmn[1]=a[1];
        for(int i=2;i<=n;i++)
            lmx[i]=max(lmx[i-1],a[i]),lmn[i]=min(lmn[i-1],a[i]);
        rmx[n+2]=rmx[n+1]=0,rmn[n+2]=rmn[n+1]=INT_MAX;
        rmx[n]=rmn[n]=a[n];
        for(int i=n-1;i;i--)
            rmx[i]=max(rmx[i+1],a[i]),rmn[i]=min(rmn[i+1],a[i]);
        for(int i=1;i<=n;i++)
        {
            while(!ss.empty()&&a[ss.top()]>a[i])
                rs[ss.top()]=i,ss.pop();
            while(!sb.empty()&&a[sb.top()]<a[i])
                rb[sb.top()]=i,sb.pop();
            ss.push(i),sb.push(i);
        }
        while(!ss.empty())
            rs[ss.top()]=0,ss.pop();
        while(!sb.empty())
            rb[sb.top()]=0,sb.pop();
        for(int i=n;i;i--)
        {
            while(!ss.empty()&&a[ss.top()]>a[i])
                ls[ss.top()]=i,ss.pop();
            while(!sb.empty()&&a[sb.top()]<a[i])
                lb[sb.top()]=i,sb.pop();
            ss.push(i),sb.push(i);
        }
        while(!ss.empty())
            ls[ss.top()]=0,ss.pop();
        while(!sb.empty())
            lb[sb.top()]=0,sb.pop();
        for(int i=1;i<=n;i++)
        {
            if(i&1)
            {
                int ls1=ls[i],lb1=lb[i],rs1=rs[i],rb1=rb[i],t;
                vl[1]=vl[2]=vl[3]=vl[4]=vr[1]=vr[2]=vr[3]=vr[4]=0;
                if(ls1>1)
                {
                    t=ls1-!((i-ls1)&1)-1;
                    vl[2]=lmx[t]>a[i],vl[4]=lmn[t]<a[i];
                }
                if(lb1>1)
                {
                    t=lb1-!((i-lb1)&1)-1;
                    vl[1]=lmx[t]>a[i],vl[3]=lmn[t]<a[i];
                }
                if(rs1)
                {
                    t=rs1+!((rs1-i)&1)+1;
                    vr[3]=rmx[t]>a[i],vr[4]=rmn[t]<a[i];
                }
                if(rb1)
                {
                    t=rb1+!((rb1-i)&1)+1;
                    vr[1]=rmx[t]>a[i],vr[2]=rmn[t]<a[i];
                }
                if(i==1)
                    p[a[i]]=(vr[1]||vr[4]);
                else if(i==n)
                    p[a[i]]=(vl[1]||vl[4]);
                else
                    p[a[i]]=((vl[1]&&(vr[1]||vr[4]))||(vl[2]&&vr[3])||(vl[3]&&vr[2])||(vl[4]&&(vr[1]||vr[4])));
            }
            else if((lmx[i-1]>a[i]&&rmx[i+1]>a[i])||(lmn[i-1]<a[i]&&rmn[i+1]<a[i]))
                p[a[i]]=1;
        }
        for(int i=1;i<=n;i++)
            putchar(p[i]+'0');
        putchar(10);
    }
    return 0;
}