CF1434E A Convex Game

一个序列满足单调递增。一次合法的操作是选择一个数，要求这个数在上一个选择的数的后面，并且要求选的数形成的子序列满足相邻的差递增。

两个人轮流操作，有若干个序列，问先手必胜还是后手必胜。

\(n\le 10^5\)。

gmh77：这题不值得3500。

我一道题搞了一天。。。

普通的DP考虑：\(f_{i,j}\)表示计算以\(i\)开始的答案，要求差大于\(j\)的\(sg\)值。

显然\(sg\)值不超过\(\sqrt {2V} +1\)，\(V\)表示最大值。又可以发现，当\(i\)固定时，随着\(j\)的增加，\(sg\)单调不增。于是可以将普通的DP魔改一下，将\(sg\)值丢进状态中。变成：\(f_{i,sg}\)表示计算以\(i\)开始的答案，大于等于这个\(sg\)值的最大\(j\)。

转移考虑枚举\(sg’=0\dots sg-1\)，对于每个\(sg’\)找到最大的\(j\)满足\(f_{j,sg’}\ge v_j-v_i\)且\(f_{j,sg’+1}<v_j-v_i\)。将所有的\(j\)取\(min\)，就是我们需要求的。

用数据结构优化这个过程：对于每个\(sg’\)维护个数据结构，表示\(v_i\)为多少能得到多少的贡献。\(j\)可以对\([v_j-f_{j,sg’},v_j-f_{j,sg’+1})\)作出贡献。由于是从后往前做，所以\(j\)是递减的，那这个数据结构实际上支持的是：对一个区间中为空的位置进行覆盖。并查集就可以了。

首先离散化，数据结构的总大小为\(O(\sqrt Vn)\)。转移的时候需要将操作的区间对应到离散化后的区间，二分会TLE，可以对值域分块，将离散化后的值打到每个点上，时间是\(O(n\sqrt V)\)的；不过这题给出\(T\le 1000\)，所以直接暴力打也没有问题。转移的时间复杂度为\(O(\sqrt nV\lg n)\)，这个\(\lg\)来自并查集，常数极小所以可以忽略不计。

using namespace std;
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#define N 100005
#define V 500
#define INF 1000000000
int n;
int v[N];
int q[N],re[N],m;
int B;
int pd[N],pb[N],bel[N],L[N],R[N],nb;
bool cmpq(int a,int b){return v[a]<v[b];}
void change(int l,int r,int c){
	if (bel[l]==bel[r]){
		for (int i=l;i<=r;++i)
			pd[i]=c;
		return;
	}
	for (int i=l;i<=R[bel[l]];++i)
		pd[i]=c;
	for (int i=r;i>=L[bel[r]];--i)
		pd[i]=c;
	for (int i=bel[l]+1;i<=bel[r]-1;++i)
		pb[i]=c;
}
void init(){
	m=0;
	for (int i=1,last=-1;i<=n;++i){
		if (last!=v[q[i]]){
			re[last=v[q[i]]]=++m;
			q[m]=q[i];
		}
	}
	for (int i=1;i<=v[n];++i)
		q[i]=v[q[i]];
	q[m+1]=v[n]+1;
	for (int i=1;i<=nb;++i)	
		pb[i]=0;
	change(0,q[1]-1,0);
	for (int i=1;i<=m;++i)
		change(q[i],q[i+1]-1,i);
}
int query(int x){return pb[bel[x]]?pb[bel[x]]:pd[x];}
int f[V],g[V][N];
struct Node{
	Node *fa;
	Node *g(){
		return fa==this?this:fa=fa->g();
	}
} d[V][N];
void modify(Node d[],int g[],int l,int r,int c){
	l=max(l,0),r=min(r,v[n]+1),r--;
	if (l>r) return;
//	l=lower_bound(q,q+m+1,l)-q;
//	r=upper_bound(q,q+m+1,r)-q-1;
	l=(l==0?0:query(l-1)+1);
	r=query(r);
	if (l>r) return;
	Node *t=&d[l];
	while (1){
		t=t->g();
		if (t-d>r)
			break;
		g[t-d]=c;
		t->fa=(t+1)->g();
	}
}
int mex(int q[],int t){
	sort(q,q+t);
	int j=0;
	for (int i=0;i<t;++i){
		if (q[i]>j)
			return j;
		if (q[i]==j)
			j++;
	}
	return j;
}
int p[N],cnt;
int main(){
//	freopen("in.txt","r",stdin);
//	freopen("out.txt","w",stdout);
	for (int i=1;i<=v[n];++i)
		bel[i]=(i-1)/V+1,R[bel[i]]=i,nb=bel[i];
	for (int i=1;i<=nb;++i)
		L[i]=R[i-1]+1;
	int T;
	scanf("%d",&T);
	int xo=0;
	while (T--){
		scanf("%d",&n);
		for (int i=1;i<=n;++i)
			scanf("%d",&v[i]),q[i]=i;
		sort(q+1,q+n+1,cmpq);
		B=sqrt(v[n]*2)+1;
		init();
		for (int j=0;j<=B;++j)	
			for (int i=0;i<=m+1;++i){
				g[j][i]=-INF;
				d[j][i].fa=&d[j][i];
			}
		cnt=0;
		for (int i=n;i>=1;--i){
			static int t[N];
			for (int sg=0;sg<B;++sg)
				t[sg]=g[sg][re[v[i]]];
			f[0]=INF;
			for (int sg=1;sg<=B;++sg)
				f[sg]=min(f[sg-1],t[sg-1]);
			for (int sg=1;sg<=B;++sg)
				f[sg]=f[sg]-v[i]-1;
			for (int sg=B-1;sg>=0;--sg)
				if (f[sg]!=f[sg+1])
					modify(d[sg],g[sg],v[i]-f[sg],v[i]-f[sg+1],v[i]);
			int ans=0;
			for (ans=0;ans<=B;++ans)
				if (f[ans]<0)
					break;
			p[cnt++]=ans-1;	
		}
		int ans=mex(p,cnt);
//		printf("%d\n",ans);
		xo^=ans;
	}
	if (xo)
		printf("YES\n");
	else
		printf("NO\n");
	return 0;
}