【XVIII Open Cup E.V. Pankratiev. Grand Prix of Korea. J】Game of Sorting 题解

题目大意

  对于一个序列 $a_1,\cdots,a_n$，Alice 和 Bob 在上面博弈，Alice 先手，两人轮流操作，每人每次要么拿走第一个元素或者最后一个元素，谁先使得这个序列不增或不降就获胜（如果一开始就不增或不降那么 Bob 获胜）。
  现在给定一个序列 $a_1,\cdots,a_n$，有 $Q$ 个询问，每次询问给出 $l,r$，问 $a_l,a_{l+1},\cdots,a_r$ 的博弈结果。

  $n,Q \leq 10^6,\ \ a_i \leq 10^9$
  3s

$$\\$$ $$\\$$ $$\\$$

题解

  这官方题解写得。。。真的想让人大喊“出题人重修离散数学！”

  暴力一点想，可以先弄个区间 dp，设 $f_{l,r}$ 表示操作 $[l,r]$ 这个区间时是否是先手必胜。那么 $f_{l,r}=\lnot f_{l,r-1} \lor \lnot f_{l+1,r}$。

  怎么优化这个东西呢？题解的思路是观察发现大部分时候 $f_{l,r}=f_{l+1,r-1}$。

  具体的分类讨论是这样子的：
  设区间 $[l,r]$ 里面的最长单调段的长度为 $len$。

1. $len=r-l+1$，即 $[l,r]$ 本身是单调段，先手必败；
2. $len=r-l$，根据上条可得这种情况先手必胜；
3. $len=r-l-1$，这里又分为 $[l,r-2]$ 是单调段、$[l+1,r-1]$ 是单调段、$[l+2,r]$ 是单调段三种情况:
   3.1. 若 $[l,r-2]$ 是单调段，那么正常情况下大家都不会拿最后一个（不然对面再拿掉倒数第二个就 over 了），因此都是从左往右拿，直到剩下的是个单调段为止。那么就可以预处理 $L_i$ 表示以 $i$ 为右端点的最长单调段到哪，这样就可以算出步数，根据奇偶性算出先手的胜负；（注意一类特殊情况，例如 $1,2,3,4,4,4,2,3$，当拿剩 $4,4,4,2,3$ 的时候，先手直接拿掉最后一个，获胜）
   3.2. $[l+2,r]$ 是单调段的情况同理；
   3.3. 若 $[l+1,r-1]$ 是单调段，先手后手一前一后完事，先手必败。

  以上这三种情况可以称之为“终止态”，因为它们可以 $O(1)$ 计算答案了。

1. $len<r-l-1$，此时 $[l,r-2]$、$[l+1,r-1]$、$[l+2,r]$ 都是可操作的区间。展开那个暴力的 dp 转移式：

   $$\begin{aligned} f_{l,r}&=\lnot f_{l,r-1} \lor \lnot f_{l+1,r} \\ &=(f_{l,r-2} \land f_{l+1,r-1}) \lor (f_{l+1,r-1} \land f_{l+2,r}) \end{aligned}$$

   观察发现，若 $f_{l+1,r-1}=0$，则直接 $f_{l,r}=0$；若 $f_{l+1,r-1}=1$，则必有 $f_{l+1,r-2}=0$ 或 $f_{l+2,r-1}=0$，前者会导致 $f_{l,r-2}=1$，后者会导致 $f_{l+2,r}=1$，两者代入转移式都会使 $f_{l,r}=1$。
   因此 $f_{l,r}=f_{l+1,r-1}$。

  这样就讨论完了。最终做法的思路就是，将 $[l,r]$ 往里缩，缩到终止态为止。这个终止态是什么呢？可以根据 $[l,r]$ 的对称轴所在的极长单调段算出来。
  注意一个元素（或元素间的缝）可能同时属于两个极长单调段。

  具体实现，预处理的时候，可以找出所有极长不降段、极长不升段，合并得到极长单调段覆盖。可以 $O(n \log n)$ 也可以 $O(n)$。

代码

#include<bits/stdc++.h>
#define fo(i,a,b) for(int i=a;i<=b;i++)
using namespace std;

typedef pair<int,int> pr;

const int maxn=1e6+5;

int n,a[maxn];

pr v[2*maxn],seg[2*maxn];
int v0,seg0,sr[2*maxn],R[maxn],L[maxn];
bool cmpV(const pr &a,const pr &b)
{
    return a.first<b.first || a.first==b.first && a.second>b.second;
}
void Pre()
{
    int last=1;
    fo(i,2,n) if (a[i-1]>a[i])
    {
        v[++v0]=make_pair(last,i-1);
        last=i;
    }
    v[++v0]=make_pair(last,n);
    last=1;
    fo(i,2,n) if (a[i-1]<a[i])
    {
        v[++v0]=make_pair(last,i-1);
        last=i;
    }
    v[++v0]=make_pair(last,n);

    sort(v+1,v+1+v0,cmpV);
    last=1;
    fo(i,1,v0) if (v[i].second>seg[seg0].second)
    {
        fo(j,last,v[i].first-1) R[j]=seg[seg0].second;
        last=v[i].first;
        seg[++seg0]=v[i], sr[seg0]=v[i].second;
    }
    fo(j,last,n) R[j]=n;
    for(int i=n, j=seg0; i>=1; i--)
    {
        if (j && i==seg[j-1].second) j--;
        L[i]=seg[j].first;
    }
}

int T;
int main()
{
    scanf("%d",&n);
    fo(i,1,n) scanf("%d",&a[i]);

    Pre();

    scanf("%d",&T);
    while (T--)
    {
        int l,r,mid;
        scanf("%d %d",&l,&r);
        mid=(l+r)>>1;

        int ll, rr, x=lower_bound(sr+1,sr+1+seg0,(l+r+1)>>1)-sr, even=!((r-l+1)&1);
        int t=min(mid-seg[x].first+even,seg[x].second-mid);
        if (x+1<=seg0 && seg[x+1].first<=mid) t=max(t,min(mid-seg[x+1].first+even,seg[x+1].second-mid));
        t=min(t,min(mid-l+even,r-mid));
        ll=mid-t+even, rr=mid+t;
        while (l<ll && rr<r && (R[ll-1]>=rr-1 || R[ll+1]>=rr+1)) ll--, rr++;

        if (R[ll]>=rr) puts("Bob");
            else if (R[ll]==rr-1 || R[ll+1]>=rr) puts("Alice");
            else if (R[ll]==rr-2) puts(((rr-ll+1-(rr-L[rr-1])-(R[rr-2]>rr-1))&1) ?"Alice" :"Bob");
            else if (R[ll+2]>=rr) puts(((rr-ll+1-(R[ll+1]-ll)-(R[ll]>ll+1))&1) ?"Alice" :"Bob");
            else if (R[ll+1]==rr-1) puts("Bob");
            else assert(0);
    }
}