暴力求SG，结论：每一个序列的SG上限为$\sqrt{2\max a_{i}}+1$
证明：将SG的转移看作一张DAG，归纳每一个点的SG值不超过其开始的最长路，显然成立
那么本题中最长路即在$a_{i}$中最多能选多少次，假设选择的权值依次为$v_{1},v_{2},...,v_{m}$，则$v_{i+1}-v_{i}\ge i$，累加即$v_{m}-v_{1}\ge \frac{m(m-1)}{2}$，放缩得$(m-1)^{2}<2v_{m}$，$m$也即SG的上限为$\sqrt{2\max a_{i}}+1$
考虑dp，令$f_{i,j}$表示最后两次分别选了$a_{i}$和$a_{j}$的SG值，转移为$f_{i,j}=mex(\{f_{k,i}|a_{k}-a_{i}>a_{i}-a_{j}\})$，利用$k$的单调性，倒序枚举$j$，可以做到$o(n^{2})$，最终答案即为$mex(\{f_{i,0}|1\le i\le n\})$
令$g_{i,j}=\min_{f_{i,k}>j}k$，根据上面的结论，$g$的总数量为$o(n\sqrt{n})$，考虑直接转移$g$
根据单调性，有$g_{i,j}\ge g_{i,j-1}$，这也就保证了$f_{i,g_{i,j}}$后面的集合包含了$[1,j)$，同时$j$也需要出现，因此即要求$\exists k,a_{g_{i,j}}>2a_{i}-a_{k}且f_{k,i}=j$，后者又等价于$g_{k,j-1}\le i<g_{k,j}$，贪心求出满足后者的$k$中最大值即可
考虑先枚举$j$，维护线段树，每一次先查询$i$上的值并判断，再令区间$[g_{i,j-1},g_{i,j})$的值对$i$取max，时间复杂度为$o(n\sqrt{n}\log_{2}n)$，略微卡常
进一步优化，由于插入的区间单调递增，因此可以看作对未被修改的部分修改，维护两个并查集，分别表示：1.上一个未被覆盖的点；2.同一种类型的上一个点，时间复杂度为$o(n\sqrt{n}\alpha(n))$
1 #include<bits/stdc++.h> 2 using namespace std; 3 #define N 100005 4 #define L (k<<1) 5 #define R (L+1) 6 #define mid (l+r>>1) 7 int t,n,ans,a[N],f[2][N],fa[N],ga[N],v[N]; 8 int find(int k){ 9 if (fa[k]==k)return k; 10 return fa[k]=find(fa[k]); 11 } 12 int find_las(int k){ 13 if (ga[k]==k)return k; 14 return ga[k]=find_las(ga[k]); 15 } 16 void update(int l,int r,int x){ 17 int rr=r; 18 r=find_las(r); 19 if (l>r)return; 20 while (l<=find_las(r-1)){ 21 int las=find_las(r-1); 22 fa[r]=r=las; 23 } 24 swap(r,rr); 25 while (l<=r){ 26 ga[r]=r-1; 27 if (!v[r-1])r--; 28 else r=find_las(r-1)+1; 29 } 30 v[rr]=x; 31 } 32 int query(int k){ 33 return v[find(k)]; 34 } 35 int main(){ 36 scanf("%d",&t); 37 while (t--){ 38 scanf("%d",&n); 39 for(int i=1;i<=n;i++)scanf("%d",&a[i]); 40 int s=0,p=0,flag=0; 41 for(int i=1;i<=n;i++)f[p][i]=1; 42 while (!flag){ 43 flag=1; 44 s++; 45 p^=1; 46 for(int i=1;i<=n;i++){ 47 fa[i]=ga[i]=i; 48 v[i]=0; 49 } 50 for(int i=n;i;i--){ 51 int k=query(i); 52 if(!k)f[p][i]=n+1; 53 else f[p][i]=upper_bound(a+1,a+n+1,2*a[i]-a[k])-a; 54 if (f[p^1][i]>=f[p][i])f[p][i]=f[p^1][i]; 55 else update(f[p^1][i],f[p][i]-1,i); 56 if (f[p][i]<=n)flag=0; 57 } 58 } 59 printf("%d\n",s); 60 ans^=s; 61 } 62 if (ans)printf("YES"); 63 else printf("NO"); 64 }
原文：https://www.cnblogs.com/PYWBKTDA/p/13900930.html
