Codeforces Round 972 (Div. 2) E2. Subtangle Game (Hard Version)（博弈+双指针 sg函数思想）

题目

思路来源

稲葉廻代码

题解

这个题比easy version的数据范围大了比较多，

不能再直接dp[i][j][k]表示数组a的第i个做开始局面时，位置(j,k)为起点时的获胜情况了

当然你把第一维压到bitset里，然后前缀和优化一下，还是可以通过的，这里先不讨论这个方法

期望dp和博弈都类似dag，都可以考虑从终态局面往回推，

那么对于序列a的最后一个元素，考虑所有获胜位置，

就是每行的最靠右，且其右下方没有与之相同元素的位置

如果一行内出现了两个相同元素，选左边的那个肯定是不优的，

给对手的下一步留了更多的操作空间（选右边的那个时下一步的操作空间是选左边的真子集）

’

对于所有颜色v都处理出这样的位置集合，记为win[v]，表示v作为最后一步时的所有获胜位置

这个位置序列，是一个第一维增序，第二维降序的序列，形如(1,4)(2,3)(3,2)这种

然后考虑倒着遍历a数组，求出最后一步win[a[l]]了之后，

考虑求出倒数第二步win[a[l-1]]的所有获胜位置，

只要能走到win[a[l]]内任意一个元素的都是必败的，否则就是必胜的

这个用双指针维护，

一个指针控制第一维，找到下一个vector内第一维比当前位置(x,y)第一维大的最右右端点r，

另一个指针控制第二维，找到下一个vector内第一维比当前位置(x,y)第二维大的最小左端点l，

那么，如果l<=r且[l,r]内有下一个vector内必胜(sg=1)的元素，当前局面就必败(sg=0)

反过来，则必胜(sg=1)

逆推到第一个元素，然后判断第一个元素对应的vector内是否有必胜元素即可

这题主要时间花在读入上了，scanf 2s交c++20直接T了，交c++17少了一点时间AC了

c++20对关同步cin有特殊优化，导致关同步cin比scanf快，但是快读还是最快的，1s不到

代码

//#include <bits/stdc++.h>
#include<iostream>
#include<cstdio>
#include<vector>
#include<map>
#include<set>
#include<array>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
typedef long long ll;
typedef double db;
typedef pair<int,int> P;
#define fi first
#define se second
#define pb push_back
#define dbg(x) cerr<<(#x)<<":"<<x<<" ";
#define dbg2(x) cerr<<(#x)<<":"<<x<<endl;
#define SZ(a) (int)(a.size())
//#define sci(a) scanf("%d",&(a))
#define pt(a) printf("%d",a);
#define pte(a) printf("%d\n",a)
#define ptlle(a) printf("%lld\n",a)
#define debug(...) fprintf(stderr, __VA_ARGS__)
using namespace std;
namespace fastIO
{static char buf[100000],*h=buf,*d=buf;//缓存开大可减少读入时间，看题目给的空间#define gc h==d&&(d=(h=buf)+fread(buf,1,100000,stdin),h==d)?EOF:*h++//不能用fread则换成getchartemplate<typename T>inline void sci(T&x){int f = 1;x = 0;register char c(gc);while(c>'9'||c<'0'){if(c == '-') f = -1;c=gc;}while(c<='9'&&c>='0')x=(x<<1)+(x<<3)+(c^48),c=gc;x *= f;}template<typename T>void output(T x){if(x<0){putchar('-');x=~(x-1);}static int s[20],top=0;while(x){s[++top]=x%10;x/=10;}if(!top)s[++top]=0;while(top)putchar(s[top--]+'0');}
}
using namespace fastIO;
const int N=1505;
int t,l,n,m,a[N],b[N][N],sg[N],nsg[N],mn[N*N];
vector<P>win[N*N];
void sol(){sci(l);sci(n);sci(m);rep(i,1,l){sci(a[i]);}rep(i,1,n){rep(j,1,m){sci(b[i][j]);}}rep(i,1,n*m)win[i].clear(),mn[i]=0;per(i,n,1){per(j,m,1){int v=b[i][j];if(j>mn[v]){win[v].pb(P(i,j));mn[v]=j;}}}memset(sg,0,sizeof sg);memset(nsg,0,sizeof nsg);per(i,l,1){vector<P>&now=win[a[i]],&nex=win[a[i+1]];int p=SZ(now),q=(i==l?0:SZ(nex)),l=0,r=-1;rep(j,0,p-1){P v=now[j];while(r+1<q && nex[r+1].fi>v.fi)r++;//[0,r] >v.fiwhile(l<q && nex[l].se<=v.se)l++;//[l,q) >v.sensg[j+1]=(sg[r+1]-sg[l]<=0);//[l,r]}sg[0]=nsg[0],nsg[0]=0;rep(j,1,p)sg[j]=sg[j-1]+nsg[j],nsg[j]=0;if(i==1){printf("%c\n","NT"[sg[p]>0]);return;}}
}
int main(){sci(t);while(t--){sol();}return 0;
}