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

题解"/>

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

题目大意

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

   n , Q ≤ 1 0 6 , a i ≤ 1 0 9 n,Q \leq 10^6,~~a_i \leq 10^9 n,Q≤106,  ai​≤109
  3s

\\
\\
\\

题解

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

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

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

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

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

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

4. l e n < r − l − 1 len<r-l-1 len<r−l−1，此时 [ l , r − 2 ] [l,r-2] [l,r−2]、 [ l + 1 , r − 1 ] [l+1,r-1] [l+1,r−1]、 [ l + 2 , r ] [l+2,r] [l+2,r] 都是可操作的区间。展开那个暴力的 dp 转移式：
   f l , r = ¬ f l , r − 1 ∨ ¬ f l + 1 , r = ( f l , r − 2 ∧ f l + 1 , r − 1 ) ∨ ( f l + 1 , r − 1 ∧ f l + 2 , r ) \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} fl,r​​=¬fl,r−1​∨¬fl+1,r​=(fl,r−2​∧fl+1,r−1​)∨(fl+1,r−1​∧fl+2,r​)​观察发现，若 f l + 1 , r − 1 = 0 f_{l+1,r-1}=0 fl+1,r−1​=0，则直接 f l , r = 0 f_{l,r}=0 fl,r​=0；若 f l + 1 , r − 1 = 1 f_{l+1,r-1}=1 fl+1,r−1​=1，则必有 f l + 1 , r − 2 = 0 f_{l+1,r-2}=0 fl+1,r−2​=0 或 f l + 2 , r − 1 = 0 f_{l+2,r-1}=0 fl+2,r−1​=0，前者会导致 f l , r − 2 = 1 f_{l,r-2}=1 fl,r−2​=1，后者会导致 f l + 2 , r = 1 f_{l+2,r}=1 fl+2,r​=1，两者代入转移式都会使 f l , r = 1 f_{l,r}=1 fl,r​=1。
   因此 f l , r = f l + 1 , r − 1 f_{l,r}=f_{l+1,r-1} fl,r​=fl+1,r−1​。

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

  具体实现，预处理的时候，可以找出所有极长不降段、极长不升段，合并得到极长单调段覆盖。可以 O ( n log ⁡ n ) O(n \log n) O(nlogn) 也可以 O ( n ) O(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);}
}